[SCRÂȘIT] [FOȘTIT] [CLIC] PROFESORUL: OK, de ce nu încep? Deci OK, ce am făcut? Deci data trecută, am luat în considerare o grămadă de proceduri pentru testarea proprietăților diferitelor automate și gramatici, problema acceptării pentru DFA, pentru NFA, problema acceptării, care este într-adevăr o problemă de degenerare pentru gramaticile fără context și problemele de golire pentru DFA și context. -gramatici libere. Și, de asemenea, am arătat că A,TM este recunoscut de Turing. Există deja o întrebare aici în chat despre asta. Da, am arătat asta. Aceasta a fost mașina Turing universală pe care am prezentat-o ​​la sfârșit. Acesta este ceea ce arată că A,TM este recunoscut de Turing. Am menționat că A,TM nu este decidabilă, ceea ce am promis că vom demonstra astăzi. Și așa vom face. Bine, deci acesta este planul - să demonstrezi că A,TM este indecidabil. Și vom introduce metoda pentru a face asta numită metoda de diagonalizare. De asemenea, voi arăta că complementul lui A,TM este Turing-nerecunoscut. Chiar dacă A,TM în sine este recunoscut, complementul nu este. Și apoi vom introduce o altă metodă numită metoda reductibilității pentru a arăta că alte probleme nu sunt decidabile și vom da un exemplu de altă problemă, care nu este decidabilă, presupunând că avem timp să ajungem la ea. Dacă nu, vom amâna acea parte până la prelegerea de marți viitoare. Bine, problemă de acceptare pentru Mașinile Turing. Așadar, așa cum am menționat, am arătat că A,TM, care este limbajul mașinilor Turing și al intrărilor în care mașina acceptă intrarea. Am arătat că era de recunoscut. Am susținut că este decizibil. Astăzi, vom demonstra că nu este decidabil. În regulă, acum metoda pe care o vom folosi, care este într-adevăr singura metodă disponibilă pentru a demonstra că o problemă este indecidabilă, se numește metoda de diagonalizare. Adică, în cele din urmă, vom arăta și metoda reductibilității . Dar depinde într-adevăr de faptul că am arătat deja o altă problemă indecidabilă prin metoda diagonalizării. Deci, în cele din urmă, totul depinde de metoda de diagonalizare, care este cu adevărat ceea ce avem. Și astfel, pentru a introduce metoda diagonalizării, voi face o mică digresiune într-o ramură a matematicii numită teoria mulțimilor sau este o parte a logicii matematice, unde metoda diagonalizării a fost concepută pentru prima dată la sfârșitul secolului al XIX-lea. de un matematician numit Georg Cantor. Și Cantor se gândea la problema cum comparați dimensiunile relative ale mulțimilor infinite? Pentru seturi finite, problema comparării... cineva a spus că Cantor a luat-o razna. Asta e adevarat. Și poate că nu știu de ce a luat-o razna. Dar a plecat... a avut niște probleme mentale, din păcate. Și deci cum comparăm dimensiunile seturi în general? Dacă sunt seturi finite, le putem număra. Putem spune, whoa, acest set are 11 elemente, iar celălalt set are 10 elemente. Deci cel cu 11 este mai mare. Sau dacă amândoi au 11, au aceeași dimensiune. Ei bine, asta nu va funcționa pentru seturi infinite pentru că nu le poți număra. Și așa a avut... Cantor a avut următoarea idee pentru a compara dimensiunile seturi infinite. Și asta a fost, practic, pentru a vedea dacă puteți avea o funcție care să mapați de la un set la celălalt set cu anumite proprietăți. Și acele proprietăți sunt numite, în mod tradițional, ei bine, vreau să spun, în trecut, au fost numite proprietăți one-to-one și on pentru funcție. Îți voi spune ce înseamnă asta. Dar conceptul este foarte simplu. Deci, o funcție unu-la-unu este o funcție care se mapează de la A la B. Acestea sunt cele două seturi ale căror dimensiuni încercăm să le comparăm. Și funcția fiind unu-la-unu înseamnă doar că nu există coliziuni. Dacă aveți două elemente diferite ale lui A, nu se vor mapa niciodată pe același element al lui B. Deci două elemente diferite ale lui A se mapează întotdeauna pe două elemente diferite ale lui B. Deci aceasta este proprietatea unu-la-unu. Se mai numește și injectiv. Iar cealaltă proprietate este numită pe sau surjectivă, și anume că intervalul lui f trebuie să fie tot din B. Deci nu aveți voie să pierdeți niciun element, dar trebuie să loviți totul. Și când aveți ambele proprietăți, funcția se numește corespondență unu-la-unu sau, de asemenea, o bijecție, OK? Acum, un alt mod de a-l privi... Nu vreau să fac asta mai complicat decât trebuie. Înseamnă pur și simplu că două seturi sunt considerate a fi de aceeași dimensiune dacă putem potrivi elementele cu un set cu elementele celuilalt set. Doar le împerechezi. De exemplu, ei bine, dacă aveți seturi finite, acea idee, acea idee informală funcționează exact așa cum v-ați aștepta. De exemplu, dacă avem două seturi... iată un set de căței. Iată un set de pisoi. Acum vrem să arătăm că cele două seturi au aceeași dimensiune. Am putea să le numărăm, așa cum am menționat, și să vedem că există șase elemente în ambele. Dar numărarea nu funcționează pentru seturi infinite. Așa că putem pur și simplu să potrivim elementele cățeilor cu pisoii și apoi știm că avem același număr de căței ca și pisoi. OK, acum asta are avantajul că are sens atunci când ai seturi infinite. Așa că vom extinde această idee și o vom aplica și la seturi infinite. Și apoi vom avea o noțiune despre ce înseamnă ca două seturi infinite să aibă aceeași dimensiune. Și s-ar putea să vă întrebați, ce obțineți? Sunt toate seturile infinite de aceeași dimensiune atunci când utilizați această noțiune sau nu? Ce se întâmplă? Ei bine, unele lucruri ciudate se întâmplă. Dar, de fapt, există o structură destul de interesantă care apare acolo. Deci, oricum, nu vreau să mă grăbesc. Întrebări despre oricare dintre acestea? Dacă vrei să... întrebare rapidă. Acest lucru, sperăm, nu a fost prea greu, dar vreau să mă asigur că toată lumea este împreună cu mine, ca să putem intra... Voi acorda câteva secunde pentru o conversație dacă aveți întrebări. Gama setului este toate elementele pe care le lovești în timp ce te uiți la diferitele elemente posibile ale lui A. Deci, toate lucrurile pe care f le lovește, noțiunea standard de gamă a unei funcții. Deci intervalul lui f trebuie să fie egal cu B. Trebuie să loviți totul. În regulă, te poți gândi la o corespondență unu-la-unu ca la o reetichetare? Da, nu sunt sigur că e de ajutor. Dar, da, te poți gândi la o reetichetare a elementelor într-un anumit sens, dar da. Mă gândesc doar la asta ca la o potrivire. Bine, deci să mergem mai departe. Deci, ieșind din această noțiune de mulțimi care sunt de aceeași dimensiune cu această noțiune de mulțimi numărabile, așa cum vom vedea într-un minut, deci să facem un exemplu. Să luăm mulțimea numerelor naturale -- 1, 2, 3, 4, punct, punct, punct, punct și mulțimea numerelor întregi, care include numerele naturale, dar și numerele negative și zero. Deci numerele naturale sunt de obicei denumite N. Numerele întregi sunt de obicei denumite Z. Și ce părere avem despre dimensiunile relative ale lui N și Z? Ei bine, N este un subset al lui Z. Este un subset propriu al lui Z. Deci, la prima vedere, s-ar putea să credeți că Z este mai mare și că nu vor fi cu adevărat de aceeași dimensiune. Dar, de fapt, se dovedește că există o modalitate foarte simplă - aritmetica și proprietățile mulțimilor infinite pot fi puțin surprinzătoare. Și există o modalitate de a potrivi toate elementele lui Z cu propriile elemente ale lui N. Și astfel puteți arăta că, urmând această definiție, aceste două mulțimi sunt, de fapt, de aceeași dimensiune. Deci hai să mergem repede să ne asigurăm că vedeți asta. Deci, aici este N. Aici este Z. Voi scrie un tabel care arată cum se potrivesc. Iată funcția f a lui n pe care o voi descrie. Aceasta este corespondența unu-la-unu . Și aici sunt numerele naturale -- punct, punct, punct, de la 1 la 7, punct, punct, punct. Și iată elementele lui Z pe care le voi potrivi. Așa funcționează funcția. Deci, unul, o să-- f din 1 va fi 0. F din 2 va fi minus 1. F din 3 va fi 1. Și vă ofer doar o modalitate de a potrivi fiecare dintre numerele naturale cu numere întregi, astfel încât fiecare număr întreg are propriul său număr natural și invers. Deci 4 merge la minus 2. 5 merge la 2. 6 trece la minus 3. 7 trece la 3, apoi minus 4, apoi 4, și minus 5, apoi 5 și așa mai departe. În mod clar, veți acoperi toate numerele întregi în acest fel. Și fiecare dintre numerele naturale va avea propriul său întreg. Și nu vor fi niciodată ciocniri. Nu vor fi niciodată două numere naturale atribuite aceluiași număr întreg. Deci, aceasta îndeplinește condițiile unei corespondențe unu-la-unu și arată că numerele naturale și numerele întregi au aceeași dimensiune după această definiție. OK, haideți să facem unul puțin mai complicat și, poate, puțin mai surprinzător, și anume că, dacă luați în considerare toate numerele raționale, apoi au aceleași, aceasta este o colecție. Chiar dacă numerele raționale par a fi mult mai bogate și mai numeroase decât numerele întregi, din această perspectivă, ele au aceeași dimensiune. Și pentru simplitatea prezentării mele, voi lua în considerare numai numerele raționale pozitive, pe care le voi scrie ca Q+. Deci, acestea sunt toate numerele raționale pozitive care pot fi exprimate ca raport dintre două numere naturale. Și voi arăta că există o corespondență unu-la-unu între aceste numere raționale pozitive și numerele naturale. Bine, deci aici, voi face , din nou, un tabel, la fel cum am făcut mai sus, deci comparând numerele naturale și numerele raționale pozitive. Și pentru a face asta, voi scrie aici pe margine, doar pentru a vă ajuta să vedeți cum obțin acest tabel, un tabel separat care are toate numerele raționale pozitive care apar într-un mod frumos organizat. Iată toate numerele raționale de aici care au 1 ca numărător, care au 2 ca numărător și așa mai departe și trecând prin coloane, diferiții numitori. Deci numerele din interior reprezintă toate numerele raționale diferite. Și deci, indiferent de numărul rațional pe care îl aveți, m peste n, acesta va apărea pe al n-lea rând din a n-a coloană. Acel număr va apărea. Deci vor apărea cu toții. Și voi folosi acest tabel aici pentru a completa această funcție. Deci, aici sunt toate numerele naturale. Și modul în care voi aloca numerele raționale care să apară aici este că o să mă străduiesc de la colț. Și voi face asta făcând straturi. Deci, mai întâi, voi lua 1 din acest număr aici, în acest colț. Apoi, îi voi face pe cei trei care l-au înconjurat, apoi pe acești tipi care îl înconjoară, iar acești tipi cam în cochilii ocolesc pe cei anteriori pe care le-am acoperit deja. OK, așa că permiteți-mi să ilustrez asta. Deci iată 1 peste 1, primul meu număr rațional pe care îl voi introduce în tabel, care apare chiar acolo. Deci, în continuare, voi trece 2 peste 1. Va apărea în tabelul de acolo. Acum, avem 2 peste 2. Acum, asta este de fapt puțin problematic, deoarece 2 peste 2 a fost deja făcut. Și dacă punem asta în-- pentru că 2 peste 2 este egal cu 1 peste 1. Ambele sunt egale cu numărul rațional 1. Deci, dacă am pune 2 peste 2 în acest tabel de aici, atunci nu l-am mai avea pe cel -to-one proprietate deoarece ambele 1 și 3 ar fi mapate la același punct. Deci, pur și simplu vom sări peste 2 peste 2. Voi arăta asta ca un fel de gri. Deci nu îl vom adăuga pe acesta pe tabel în funcția mea. Dar deci vom trece peste asta. Vom trece la 1 peste 2, care nu a fost văzut până acum. Și apoi vom continua să facem același lucru, acum mergând la următoarea carcasă de aici. 3 peste 1, 3 peste 2, 3 peste 3-- același lucru, vom trece peste asta-- 2 peste 3, 1 peste 3. Sper că ați înțeles ideea. Deci nu voi completa acest tabel. Am rămas fără spațiu pentru a mai completa acest tabel. Dar doar pentru a vedea cum va continua procesul aici, obținem 4 peste 1. Acum 4 peste 2, din nou, este un număr pe care l-am văzut anterior, deoarece acesta este numărul rațional 2. Am văzut asta aici, când aveam 2 peste. 1, așa că va trebui să o omitem pe aceea. 4 peste 3, 4 peste 4... asta avea să sară peste. 3 peste 4 și așa mai departe. BINE? Deci, urmând această procedură, voi putea defini această funcție. Acum această funcție nu este deosebit de plăcută în ceea ce privește o formă elegantă, închisă. Dar este o funcție total legitimă în sensul de a fi o mapare de la numerele naturale la numerele raționale pozitive. Și are proprietatea de corespondență unu-la-unu . Deci, împerechează fiecare dintre numerele naturale cu fiecare dintre numerele raționale pozitive. Fiecare își are partenerul, într-un fel. Și asta arată că numerele raționale, în ciuda faptului că sunt dense și au tot felul de mult mai mari părând, ele într-adevăr, din această perspectivă a dimensiunilor setului, au aceeași dimensiune ca și numerele naturale fac. Și, cu asta, sugerează că următoarea definiție că o mulțime este numărabilă dacă are aceeași dimensiune ca numerele naturale sau este finită. Din această perspectivă, ne vom concentra pe seturi infinite. Dar da, numărabil sau numărabil infinit, spun oamenii uneori, dacă are aceeași dimensiune ca și numerele naturale. Sau altfel, trebuie să includeți și seturile finite . Și numărabil înseamnă că puteți trece prin elementele setului ca o listă. Așa că le poți număra-- primul, al doilea, al treilea, al patrulea , punct, punct, punct. Și odată ce poți face asta, și acea numărare va afecta totul, atunci știi că le poți potrivi -- le poți asocia cu numerele naturale. Prin urmare, aveți un set numărabil. BINE. Deci, așa cum am arătat, atât Z, cât și numerele întregi și numerele raționale pozitive sunt mulțimi numărabile. BINE? Acum ați putea crede că, ei bine, din moment ce ne permitem să facem ceva la fel de arbitrar, într-un fel, ca acest tip de funcție pentru a potrivi numerele naturale cu orice mulțime pe care încercați să o măsurați, că fiecare mulțime este va fi numărabil, dacă te gândești la asta pentru că se pare că permiți prea multe posibilități. Și apoi toate mulțimile infinite vor ajunge să aibă aceeași dimensiune cu numerele naturale. Ei bine, asta este, de fapt, nu este adevărat. Și nu știu. Cantor, este cel care a descoperit asta. Nu știu dacă a fost surprinzător sau nu. Dar este interesant, cred, că există diferite dimensiuni de infinitate. Și acum vom arunca o privire și vom vedea asta. Dar vreau, din nou, vreau să mă opresc și să mă asigur că suntem cu toții împreună. Putem găsi întotdeauna o formulă închisă pentru f, mă întreabă cineva. Nu știu. Pentru acest f special, probabil că ați putea, dar probabil ar fi foarte dezordonat. Dar, în general, aceasta nu este o cerință, având o formă închisă pentru funcția de mapare. Orice funcție este permisă atâta timp cât o corespondență unu-la-unu. Suntem toți împreună la asta? Ne simțim confortabil cu noțiunea unor mulțimi infinite care au aceeași dimensiune ca numerele naturale și, prin urmare, le vom numi mulțimi numărabile? Și vom arăta că alte seturi vor avea mai multe elemente. Vor fi de nenumărat. Vor fi dincolo de -- strict vorbind, seturi strict mai mari, în sensul că nu le vom putea pune într-o corespondență unu-la-unu cu numerele întregi. Deci N este cel mai mic infinit? Da, N este cel mai mic. Deci orice infinit va avea-- veți avea întotdeauna-- Cred că nici măcar nu aveți nevoie de el-- aveți nevoie de un special-- oricând aveți o colecție infinită, puteți găsi întotdeauna un subset care va merge să fie un subset numărabil și va fi cel mai mic dintre infinitate, dar există și altele mai mari. Bine, de ce nu mergem mai departe? OK, deci exemplul unui set pe care îl vom arăta nu este numărabil -- un set nenumărabil, așa cum îl numim noi -- este un set de numere reale, despre care știm cu toții care sunt acestea, sper. Acestea sunt toate numerele pe care le puteți exprima prin reprezentări zecimale posibil infinite, cum ar fi pi, sau E pătrat de 2 sau oricare dintre celelalte familiare. Numerele raționale sunt, de asemenea, membre ale sau contează și ca numere reale și numere întregi. Și așa, dar există aceste numere suplimentare pe care le puteți obține prin expansiuni zecimale care ar putea să nu fie raționale. Și acea colecție, chiar dacă, în anumite privințe, arată oarecum asemănătoare cu numerele raționale, cu numerele reale... sper că am spus bine. Numerele reale, care este mulțimea pe care o iau în considerare aici, cele cu expansiuni zecimale infinite , de fapt sunt mult mai mari. Deci teorema este -- și asta a fost descoperit de Cantor -- că R este o mulțime nenumărabilă. Și motivul pentru care introduc acest lucru este, în afară de faptul că cred că este interesant și are o oarecare legătură cu felul de lucruri pe care le facem, dar este într-adevăr pentru scopurile în acest moment, este de a introduce această metodă numită diagonalizare. OK, asta o să folosim din nou mai târziu. Dar aceasta este prima dată când apare. Deci vom folosi o demonstrație prin contradicție pentru a arăta că R, colecția de numere reale, este nenumărabilă. Și vom presupune, pentru contradicție, că R numărabil. BINE? Deci, dacă presupunem că R este numărabil, înseamnă că avem, prin definiție, o corespondență unu-la-unu dintre numerele naturale și numerele reale. OK, așa că putem potrivi toate numerele naturale cu numerele reale într-un mod unu-la-unu și la modă. Deci putem împerechea numerele naturale cu numerele reale. Și vom acoperi toate numerele reale făcând asta. Și putem face o masă, așa cum am făcut înainte. Iată-l. Și puteți completa acest lucru cu toate numerele reale. Și asta înseamnă presupunerea. Și o să-ți arăt că asta e imposibil. Ceva o să meargă îngrozitor de rău dacă faci asta. Acum s-ar putea să nu fii de acord. S- ar putea să fii surprins. S- ar putea să credeți, ei bine, profesorul Sipser se înșeală, că voi lucra la asta peste noapte și voi uita restul cursurilor și voi veni cu o listă cu toate numerele reale. O să le completez aici și o să arăt că este imposibil. Deci, să spunem, ipotetic, doar de dragul exemplului meu, iată lista cu care ați venit. Deci trebuie să potriviți ceva cu 1. Să spunem, E. Acesta a fost un caz special, așa că o să rămâneți cu 1. Și apoi pi a ieșit a fi numărul cu care ați conectat 2 . intelegi ce caut aici? Fac o listă. Încerc să fac corespondența mea - potrivirea mea între numerele naturale și numerele mele reale despre care presupun că există pentru o contradicție. Deci 3, nu știu, 3 se conectează la 0. Inventez asta, evident... nu pe loc. Am scris diapozitivul, știi, ieri. Dar aici este rădăcina pătrată a lui 2 care apare din orice motiv. Aici este 1/7. Iată un alt număr, care, voi fi interesat dacă îl recunoașteți. Este unul subtil. Acesta este 1.234-- da, o secvență familiară aici. Și orice ar fi... orice ar fi, asta ai venit. Pretindeți că asta va funcționa ca... foarte bine. Cineva a înțeles. Sunt eu pentru a i-a putere. Dar să nu ne agățăm de asta, te rog. I la a i-a putere, destul de ciudat, pot fi văzut ca un număr real sub... dacă definiți exponentiația imaginară, ceea ce este ciudat. Dar oricum, să nu ne distram prea mult. Deci, iată lista mea de numere, numerele mele reale pe care le-am asortat în tabelul meu de aici cu numerele naturale. Acum susțin că ceva nu merge bine. Ce merge prost? Îți voi arăta că de fapt nu ai făcut așa cum ai pretins, că de fapt există cel puțin un număr care lipsește din această listă. Și voi expune acel număr. Îți voi arăta care este acel număr. O să vin în mod explicit cu un număr și să vă arăt că există acel număr care lipsește din listă. Deci aici, va fi un număr x. X este cel care lipsește. Deci, cum voi obține x? Deci x, bine, voi începe cu 0 punct, apoi voi completa restul locurilor. Și cum voi obține acele locuri? O să mă uit la masa de aici. Așa că vreau să mă uit la -- pentru a obține prima mea cifră după virgulă zecimală a lui x, mă voi uita la prima cifră după virgulă zecimală a primului număr. Așa că iau primul număr, mă uit la prima cifră după virgulă, care se întâmplă să fie un 7. Și numărul pe care îl voi pune pentru x Nu va fi 7. Va fi orice, în afară de 7 . Să zicem, 8. Pentru următoarea mea cifră a lui x, mă voi uita la... deci a doua mea cifră a lui x, voi... totul va fi până la virgulă zecimală acum, așa că am nu o sa continui sa spun asta. Mă voi uita la a doua cifră a celui de-al doilea număr, care este un 4 după virgulă zecimală. Iata. Și pentru a doua cifră a lui x, voi folosi ceva care este orice în afară de 4-- 5. Am o oarecare flexibilitate aici. Așa că aș fi putut folosi 6. Aș fi putut folosi 7. Pentru aceia dintre voi care ați văzut asta înainte, care mă vor înșela, voi sta departe de 9 și 0 doar pentru că există niște mici cazuri marginale care apar acolo, în care nu vreau să intru pentru că nu cred că este interesant pentru acest argument. Dar, din moment ce am o oarecare flexibilitate, voi evita zerouri și nouă -- probabil doar nouă este tot ce am nevoie. Și atunci argumentul va funcționa bine, bine? Deci următoarea cifră este 0. A treia cifră sau al treilea număr este 0. A treia cifră a lui x va fi orice, cu excepția 0. Ar putea fi un 1. Atunci am un 2 aici. Orice cu excepția unui 2, 6. Apoi un 5-- orice, cu excepția unui 5, a 1. A 9-- orice, în afară de un 9, un 8 și așa mai departe. Există un 8. Există un 2 și punct, punct, punct. O să continui să fac asta. Și o să spun că ai ratat acel număr, oricare ar fi acesta. Dar acel număr, este un număr. După ce termin totul, va fi reprezentarea zecimală a ceva. Iar acest număr, susțin, lipsește de pe tabel. Și ați putea spune, ei bine, chiar există. Este doar pe al 23-lea rând. Pur și simplu nu ai ajuns la el și la toboganul tău. Dar este acolo. Ei bine, o să spun că știu că nu este în al 23-lea rând pentru că diferă de numărul din al 23-lea rând la a 23-a cifră pentru că l-am construit așa. Acest număr este conceput în mod explicit pentru a fi diferit de fiecare dintre numerele de pe listă. Deci nu poate fi pe listă, deoarece a fost construit pentru a fi diferit de fiecare dintre ele în cel puțin un loc. Așa că cred că acesta este un argument frumos și arată că, indiferent cum ai încerca să găsești o corespondență unu-la-unu, vei eșua. Ai putea spune, oh, ca, doar un număr? Am muncit atât de mult. Îmi lipsește doar un număr. Nu pot obține credit parțial și îl pun pe acesta pe listă acum l-am reparat? Nu. Evident, există multe, multe numere care lipsesc. Dacă îl puneți pe acesta pe listă, aveam de gând să construiesc un alt număr care lipsea. Deci nu există nicio posibilitate de a remedia acest lucru. Și, de fapt, numerele reale sunt de nenumărat - nu pot fi asociate cu numerele naturale. Și nu e nimic. Nici măcar nu se apropie. Deci, aici, un rezumat a ceea ce tocmai am spus. F nu este o corespondență unu-la-unu indiferent de ceea ce încercați să faceți. Nu poți veni cu o corespondență unu-la-unu. Asta e contradicția. Deci asta demonstrează că R este nenumărabil. Și de aceea, apropo, numim asta o diagonalizare pentru că mergem în jos pe această diagonală aici, de aici provine termenul - de aici provine numele. OK, deci sunt fericit să-- [Chicotește] Bine, asta e... cineva mă întreabă... [ Chicotește] De fapt sunt... Am o... E aici? Nu-mi amintesc dacă este aici. Am un check-in în legătură cu asta. Și cineva anticipează asta punând întrebarea destul de faimoasă despre existența unei posibile infinitate între numerele naturale și numerele reale. Știm că numerele reale acum sunt mai mari decât numerele naturale. Dar există ceva care să fie un mijloc? Adică, aceasta este o problemă foarte, foarte faimoasă, despre care voi vorbi când ajungem la check-in, care urmează. Cineva se opune la felul în care am definit x folosind această procedură care într-adevăr nu poate, într-un fel, să afirme, știi, dar x este un număr. X este rezultatul a ceea ce este această procedură. Urmând această procedură, convergem către o anumită valoare. Și asta este o valoare. Dacă doriți, putem face o modalitate mai precisă de determinare. Nu avem flexibilitatea de a alege modul în care am făcut-o în exemplul meu. Putem face o procedură precisă pentru a găsi aceste cifre. Dar nu cred că cineva crede că există ceva care să... există vreo deficiență în acest argument în ceea ce privește modul în care definim x. Cred că merită să înțelegem acest lucru, deoarece va pune bazele dovezii noastre că A,TM este indecidabil, ceea ce este puțin, cred, poate, puțin mai abstract într-un fel în felul în care apare. O să încerc să le conectez pe cele două. Dar cred că este util să înțelegem cel puțin acest argument, deoarece acest argument este diagonalizarea în forma sa cea mai brută. Bine, cred că suntem buni. Atunci de ce nu continuăm? Deci, există o serie de corolare care decurg din afirmația că numerele reale sunt de nenumărat. În primul rând , dacă lăsați scriptul L să fie colecția tuturor limbilor, dacă doriți să o luați în considerare pe un anumit alfabet, este bine. Dar asta nu va fi cu adevărat important pentru acest punct pe care îl voi face. Deci scriptul L este colecția tuturor limbilor. Deci fiecare subset de stele sigma - fiecare subset de stele sigma este un limbaj. Deci, uită-te la toate acele subseturi posibile. Deci, asta include 0 la k, 1 la k, plus orice altă limbă la care te poți gândi vreodată și mai mult - toate limbile posibile. Deci colecția tuturor limbilor este de nenumărat. Există nenumărate multe limbi diferite acolo. Nu vreau să insist în acest punct. Poți să iei asta dacă nu urmezi pe deplin argumentul rapid pe care îl voi face aici. Dar puteți face o corespondență unu-la-unu din toate limbile cu cele reale, astfel încât fiecare limbă să primească propriul său număr real. Și felul în care o să mă gândesc la asta-- să punem numerele reale în formă binară. Și dacă vă imaginați că aici este stea sigma, toate șirurile posibile de stea sigma sunt scrise în ordinea lor standard. Și acum, dacă aveți o limbă aici, A, este doar un limbaj arbitrar. Așa că vor apărea unele dintre șirurile stelei sigma . Ca și cum 0 apare, dar 1 nu apare. Apare 00 și 01, dar nu aceștia trei. Și voi asocia cu A, limba mea, un număr real în binar, punând un 0 în reprezentarea zecimală - ei bine, reprezentarea binară, ar trebui să spun -- pentru acel șir dacă nu este acolo și un 1 dacă este acolo. Așadar, un număr real - pentru că există infinit de multe opțiuni da/nu în reprezentarea binară poate reprezenta o limbă, deoarece fiecare dintre opțiunile da/nu ale unui șir este prezentă sau nu. Voi pune un 1 pentru când șirul este prezent, un 0 când nu este prezent. Deci, fiecare limbă are propriul său număr real și fiecare număr real va fi asociat propriului său limbaj. Aici, mă limitez la numere reale între 0 și 1. Acesta nu va fi un punct esențial. Așa că să nu ne agățăm de asta. Deci, faptul că limbile o pot pune într-o corespondență unu-la-unu cu numerele reale arată că colecția tuturor limbilor este, de asemenea, de nenumărat. Acum, o altă observație aici -- un alt punct demn de remarcat este că dacă te uiți la stea sigma în sine, șirurile, toate șirurile posibile, acesta este un set numărabil. Colecția tuturor limbilor posibile este de nenumărat. Dar colecția tuturor șirurilor finite posibile este numărabilă pentru că le pot enumera. Iată lista mea cu toate șirurile posibile, pe care le puteți pune într-un tabel dacă doriți să vă gândiți că se potrivește cu numerele naturale în acest fel. Acum încerc să subliniez un punct aici, și anume că dacă luați M, care sunt toate mașinile Turing posibile -- scriptul M este toate mașinile Turing posibile -- colecția tuturor mașinilor Turing posibile este numărabilă. Există doar numeroase mașini Turing diferite. Și poți argumenta asta în tot felul de moduri diferite. Dar cred că cel mai simplu mod de a vedea asta este să te gândești la fiecare mașină Turing ca având o descriere, care este un șir. Deci, colecția tuturor descrierilor mașinilor Turing este doar un subset de stele sigma, despre care știm deja că este numărabilă. Și submulțimea oricărui set numărabil va fi numărabil. Deci, oricum, cred că merită să ne amintim că colecția de vechi mașini Turing este numărabilă. În timp ce colecția tuturor limbilor este de nenumărat. Și asta vă spune chiar acolo că un anumit limbaj nu este decis pentru că există mai multe limbi decât mașinile Turing. Avem nespus de multe limbi, doar un număr număr mare de mașini Turing, deci sunt mai puține mașini Turing decât limbi. Nu există nicio modalitate de a mapa toate limbile pe mașinile Turing. Așa că vor exista întotdeauna unele limbi care nu au fost mapate. Și astfel, în special, vor exista unele limbi care sunt indecidabile. Vor fi câteva limbi care nu sunt recunoscute de Turing. Și orice se bazează pe un tip de proces de definire automată va fi niște limbi pe care nu vor fi definite. OK, acum, ceea ce vă arată acest corolar că există un limbaj acolo, care nu este decidabil. Ceea ce vom arăta în continuare este că există un limbaj specific -- A,TM -- care nu este decidabil. Și, mai întâi, cred că avem un check-in. Și permiteți-mi să vă ofer un pic de context aici, deoarece acest lucru este relevant pentru această întrebare pe care am primit-o despre seturile de dimensiuni intermediare. Deci întrebarea dacă există un set de mărime între numerele naturale și numerele reale strict între ele - atât de mai mare decât numerele naturale, nu de aceeași dimensiune ca numerele naturale, dar nici de aceeași dimensiune cu numerele reale. , dar între ele ca mărime. Aceasta a fost întrebarea numărul 1 a lui Hilbert din lista sa de 23 despre care am vorbit cu câteva prelegeri în urmă. Este interesant că l-a pus pe numărul 1 în acel loc special privilegiat, pentru că știu că Hilbert era foarte... el a simțit că înțelegerea infinitului era o problemă cu adevărat centrală în matematică. Și că dacă nu putem răspunde la o astfel de întrebare, nu înțelegem cu adevărat infinitul. Vrei să înțelegi ce fel de dimensiuni de infinitate există. Știm că numărul real este mai mare decât numerele naturale. E ceva la mijloc? Atât de fundamental, într-adevăr. Dar s-a demonstrat pe parcursul secolului al XX-lea, într-adevăr, în două etape separate -- unul în anii 1930 de către Godel, unul la începutul anilor 1970 de către Cohen -- că nu putem răspunde la această întrebare folosind axiomele standard ale matematică. Răspunsul poate merge în orice direcție. Și ambele sunt în concordanță cu axele matematice. Deci nu veți putea dovedi niciodată că există un set a cărui dimensiune este între ele sau că nu există un astfel de set. Este pur și simplu imposibil să demonstrezi în orice mod folosind axioma standard a matematicii, care, de fapt, este oarecum remarcabilă. Și deci întrebarea mea pentru tine este... și aceasta este într-adevăr o întrebare filozofică, nu una care trebuie să știi în mod direct despre materialul din curs. Cred că este doar o chestiune de interes propriu. Sper să găsești interesant. Dacă nu, poți să răspunzi la întâmplare. Dar ce se întâmplă aici că nu putem răspunde la întrebarea dacă există un set de dimensiuni intermediare? Oare pentru că axiomele noastre pentru matematică sunt inadecvate? Sau poate că nu există o realitate matematică. Poți vorbi despre ce este real aici? Care este realitatea? Fie există un set între ele, fie nu. Dacă vă puteți imagina, toate aceste lucruri au propria lor realitate pentru ele, ei bine, atunci va exista un răspuns. Și atunci te-ai aștepta, ei bine, poate că putem găsi axiome mai bune, care de fapt ne vor da acel răspuns. Sau poți spune, ei bine, nu există realitate. Și seturile infinite sunt un fel de construcții umane oricum, așa că le putem face să se joace cum ne place. Matematicienii discută despre asta până astăzi. Și este, așa cum spun, într-adevăr, este o întrebare filozofică. Dar doar din curiozitate, hai să vedem cum ajungeți voi, băieți, prin a vă decide în privința asta. Deci iată sondajul. Mai sunt 5 secunde. Va rog sa votati. Și vom încheia sondajul, 1, 2, 3, acum. Bine, aici mergem. Deci nu există un răspuns corect. Cred că dacă majoritatea matematicienilor ar urma, cred, instinctul majorității logicienilor, în special, nu sunt sigur dacă matematicienilor generali chiar le pasă de această întrebare, dar logicienii ar avea probabil un instinct că, probabil, există seturi între ele. . Nu există niciun motiv pentru care să nu existe. Pare ciudat că ar trebui să existe un astfel de salt de la numerele naturale la numerele reale și de ce nimic între ele? Dar nu cred că această întrebare este cu adevărat rezolvată. Bine, hai să continuăm. Cred că suntem... Bine, așa că vom... Urmează pauza noastră de cafea, în caz că vă întrebați. Deci acesta este ultimul meu slide înainte de atunci. Dar acesta este un diapozitiv important, așa că vă rugăm să așteptați. Deci, iată teorema noastră promisă a zilei. O să arăt că A,TM nu este decidabilă, problema de acceptare pentru mașinile Turing. Și totul va fi conținut pe acest diapozitiv. Vom da o demonstrație prin contradicție folosind diagonalizarea. Și vom presupune că o mașină Turing, H, decide A,TM. Și vom avea o contradicție. Așa că, în primul rând, să ne asigurăm că înțelegem ce face H. Deci H primește o intrare - o mașină Turing și o intrare. Și H va fi un decident, așa că se oprește întotdeauna cu o acceptare sau un respingere. Ar trebui să accepte dacă M acceptă w și să respingă dacă nu. Deci, cu alte cuvinte, va fi respins dacă M respinge w fie prin oprire, fie prin buclă. Asta e treaba lui H. Și presupunem că putem face asta. Dar vom vedea că apare o contradicție. Deci modul în care vom face asta este într-adevăr doar un pas aici într-un fel. Și vom folosi H pentru a construi o altă mașină Turing D. H va fi o subrutină pentru D. Ne-am văzut deja făcând asta în trecut. D va face ceva un pic ciudat, doar pentru a te avertiza. Intrarea lui D este doar o mașină Turing... nu w. Și ce va face D folosind subrutina sa H va simula H pe intrarea M, virgulă, descrierea lui M. Acum ce este asta? Ei bine, descrierea lui M este doar un șir. Deci, ceea ce încearcă H - ceea ce îi cere lui H să spună, să răspundă este, acceptă M șirul care reprezintă propria descriere a lui M? Este ca și cum am hrăni M-ul în sine, ceea ce pare a fi un lucru total întortocheat, ați putea spune. De ce ai alimenta vreodată un program în sine? Cineva a scris canibalism aici... da, cam. Aș spune că e mai rău [râde] pentru că nu mănâncă pe altcineva. Te mănâncă pe tine însuți. OK, dar susțin că există cazuri reale în practică în care facem asta. Introducem programele în sine. Și exemplul pe care îl știu despre unde se face acest lucru este atunci când faci un compilator. S- ar putea să doriți să creați un compilator și apoi să scrieți în aceeași limbă pe care o compilează. Și apoi alimentați compilatorul în sine. Puteți spune, de ce să vă deranjați pentru că este deja, evident, dacă, odată ce rulează, nu trebuie să îl compilați din nou. Dar, de fapt, un exemplu în care acest lucru a fost folosit cu adevărat a fost atunci când a existat un compilator de optimizare, cred, pentru C scris pe mașinile Unix timpurii. Și compilatorul de optimizare pentru C a fost scris în C. Așa că ați alimenta compilatorul de optimizare în compilatorul obișnuit, în primul rând. Acum, aveați compilatorul în funcțiune, dar era optimizat. Deci, dar acum că se execută compilatorul de optimizare, puteți alimenta compilatorul de optimizare în acesta, care este el însuși. Acum aveți un compilator optimizat de optimizare. Așa că într-adevăr face unele-- există cel puțin un caz în care acest lucru a fost de fapt făcut în practică. Nu că ne pasă cu adevărat. Aceasta este o clasă de teorie, dar doar pentru a vă distra. Deci, aici, H încearcă să spună, ei bine, într-un M ajunge să accepte atunci când este alimentat descrierea lui însuși? Știi, cel puțin, matematic vorbind, este un lucru rezonabil de întrebat. Și apoi ce va face D când primește răspunsul înapoi de la H-- H este un decident, nu uita-- D va face opusul a ceea ce face H. Va accepta dacă H respinge și va respinge dacă H acceptă. Așa că, în rezumat, să reunim asta, ca să fie ușor de înțeles, până la urmă, ce face D? D va accepta. Apropo, D va fi decisiv. Deci D va accepta sau respinge mereu... Doar. Opusul a ceea ce îi spune H să facă. Deci D va accepta M exact atunci când M nu acceptă M pentru că atunci când M nu acceptă M, H va respinge, și atunci D va accepta. Deci D acceptă M dacă și numai dacă M nu acceptă M. Aceasta este exact condiția în care D acceptă M. Cred că este important să faceți un pas înapoi și să vă asigurați că înțelegeți această linie, deoarece mai avem o singură linie pentru a obține contradicţie. Dreapta? Suntem împreună? D acceptă M dacă și numai dacă M nu acceptă M. Acesta este doar prin modul în care am definit configurația D. Acum ceea ce vom face este să introducem, în loc de M la D, și nu un flux arbitrar, vom folosi feed în D în D. Și aceasta va fi contradicția noastră, deoarece D acum va accepta D dacă și numai dacă D nu acceptă D și asta este cu siguranță imposibil. Aceasta este contradicția noastră care demonstrează că H nu poate exista. Și, prin urmare, A,TM este indecidabil. OK, deci am terminat, cu excepția unui singur punct, care este de ce aceasta este o diagonalizare? Și cred că puteți obține asta din imaginea următoare. Dacă îți imaginezi aici notând toate orele posibile... O să fac un tabel aici. Iată lista tuturor mașinilor Turing, inclusiv D, care este o mașină pe care am construit-o presupunând că H există. Deci D apare undeva aici. Dar aici sunt toate celelalte mașini Turing. Și aici sunt toate aceste descrieri ale mașinilor Turing de-a lungul etichetării tuturor coloanelor. OK, deci acestea sunt rândurile etichetate. Acestea sunt etichetele coloanelor. Și în interior, am să vă spun răspunsul dacă o anumită mașină acceptă o anumită intrare. Deci, de exemplu, M1 acceptă propria sa descriere, dar respinge descrierea lui M2, dar acceptă descrierea lui M3. nu stiu. Evident că inventez asta. Nu știu ce este M1. Dar doar ipotetic, asta face mașina M1. Așa că doar completez acest tabel. H ar putea obține răspunsul la oricare dintre elementele din acest tabel, deoarece poate testa dacă M4 acceptă descrierea lui M3. Deci H ar putea completa acest tabel. Deci poate M2 este o mașină care respinge întotdeauna. Este o mașină foarte neprietenoasă, care respinge. M3 este o mașină foarte prietenoasă. Acceptă toate intrările. M4 respinge unele și acceptă altele, punct, punct, punct. Acum, vreau să mă uit și să văd, ce face D? Acum, pe baza informațiilor pe care ți le-am oferit deja, putem înțelege ce face D. Deci, de exemplu, ce face D când îi introduc descrierea lui M1? Ce face D? Ei bine, ne putem uita aici. D acceptă M dacă și numai dacă M nu acceptă M. Deci D va accepta M1 dacă și numai dacă M1 nu acceptă M1. Ei bine, M1 acceptă M1. Deci D face invers. D respinge. Deci OK, evidențiez aici. D respinge deoarece D va face opusul a ceea ce face mașina singură la intrare. Deci D pe M2, trebuie să te uiți ce face M2 pe M2. Respinge, deci D face opusul. Acceptă. Și, în mod similar, fiecare dintre aceste lucruri -- răspunsul lui D va fi opusul a ceea ce face mașina în propria sa descriere, doar în virtutea definiției lui D. OK și așa mai departe -- până acum , foarte bine. Dar problema este, ce se întâmplă când D este alimentat singur? Pentru că, după cum puteți vedea, ne îndreptăm spre necazuri, deoarece aici este o diagonală. D este doar unul dintre rânduri. Acea diagonală va intersecta acel rând în acest moment. Și D este definit ca va face opusul a ceea ce este acel element, dar nu poate fi opusul lui însuși. Și asta e contradicția. Așa că cred că... O să ne sun, să ne las o mică pauză aici. Și apoi îmi poți trimite mesaje între timp. Voi fi bucuros să răspund la câteva întrebări în acest timp. Mai sunt puțin peste 4 minute... deci să vedem. Lasă-mă să văd dacă pot să-ți răspund la întrebări. OK, ce este atât de special la A,TM care ne permite să facem asta? De ce nu putem face asta pe ADFA, de exemplu? Asta e o intrebare buna. Și răspunsul este că, într-un fel, putem face asta pe DFA. Adică, cred că asta este, poate, un pic cam exagerat. Dar DFA nu au putut răspunde ADFA. Adică, am putea dovedi că și în alte moduri doar... am putea folosi lucruri precum lema de pompare și nu este clar, nici măcar cum ai formula ADFA. Dar ceea ce este important aici este că într-adevăr modelul care vorbește despre el însuși este locul în care apare problema. Deci, dacă încercați să împingeți acest argument pentru a arăta că ADFA nu este decidabil de către mașinile Turing, veți eșua pentru că începem cu o mașină Turing. Și cred că o să mă confund dacă încerc să o repet. Dar nu veți obține o contradicție pentru că mașina Turing nu este un automat finit. BINE. Va ajunge acest argument în bucle proprii? Nu văd de ce ar... poate că există o oarecare auto-referință . Vom vorbi despre asta puțin mai târziu. Așa că vom reveni și vom revedea acest argument într-o săptămână și ceva când vorbim despre teorema recursiei care vorbește despre mașini care se pot referi la ele însele. Dar acesta este un pic de cap... să ne devansăm pe noi înșine. Așa că cineva comentează asta, amintindu-le de paradoxul frizerului, dacă vă amintiți asta, care are o oarecare asemănare. Există un oraș în care era un frizer care rade pe fiecare bărbat care nu se rade singur. Se pare că e un frizer foarte bun. Deci sunt unii oameni care se rad. Și restul, frizerul se rade. Întrebarea este, frizerul se rade singur? Pentru că se rade doar pe acei bărbați care nu se rad. Deci ai același tip de contradicție. Există o relație acolo. Deci cineva vrea să știe, unde am folosit decizia? Deci am folosit determinabilitatea pentru a veni cu H. Odată ce știm că A,TM este decidabil, atunci avem acea funcție H și apoi putem construi D. Așa că acesta este lanțul rațiunii. Deci presupui că A,TM este decidabilă. Apoi aveți hotarul numit H și apoi puteți construi D. Cineva vrea să vadă diapozitivul anterior. Ce parte din slide vrei? Așa că o voi lăsa acolo sus. De ce putem aplica dovada că toate mașinile Turing sunt responsabile față de toate limbile? Ei bine, pentru că mașinile Turing au descrieri. Limbile generale nu au descrieri. Și de aceea. OK, lumânarea s-a ars până la fund și este timpul să trecem mai departe. Deci, acum, să ne uităm la problema de acceptare pentru automatele de coadă. Îți voi da un automat de coadă la intrare și vreau să știu, acceptă intrarea? Asta va fi decidabil? Și ai alegerile tale. Este fie da, este decidabil pentru că acestea sunt similare cu automatele pushdown și APDA este decidabilă, fie nu pentru că da contrazice rezultatele pe care le cunoaștem în acest moment, fie nu avem suficiente informații pentru a răspunde la întrebare. OK, hai să punem asta. O secundă-- [RÂDE] în regulă, asta este. Gata, plec, plec. Deci da, răspunsul este, ei bine, nu. [RÂDE] Răspunsul este, într-adevăr, răspunsul este B. Adevărat, că automatele de coadă sunt similare cu automatele pushdown, dar toate aceste automate sunt similare între ele și asta nu va fi suficient de bun. Ceea ce ți-a cerut temele este să arăți că poți simula mașinile Turing cu automate de coadă. Deci, dacă puteți răspunde la întrebarea dacă automatele de coadă vor accepta intrarea lor, asta vă va permite să puteți răspunde la întrebări despre dacă mașinile Turing acceptă intrarea lor. Și tocmai am demonstrat că nu este posibil. Deci ar fi o contradicție dacă am putea răspunde... dacă am putea decide A, coada, A. Acum, avem un exemplu de limbaj indecidibil. Să ne uităm la un exemplu de limbaj de nerecunoscut. Acum, A,TM nu va servi acestui scop, deoarece A,TM este recunoscut de Turing, așa cum am subliniat de către mașina universală Turing. Deci, A,TM este însă indecidabil. Ce zici de o limbă de nerecunoscut? Pentru asta, vom vedea că va servi complementul lui A,TM. Deci complementul lui A,TM nu este nici decidabil, nici măcar de recunoscut. Acum nu este de recunoscut de Turing. Și asta va decurge dintr- o teoremă destul de de bază care conectează recunoașterea și determinabilitatea pe care am pus-o aici pe ecran, și anume că, dacă aveți o limbă în care atât ea, cât și complementul său sunt recunoscute, atunci prezența la vot se dovedește a fi fi decidabil. De fapt, o limbă și complementul ei sunt determinabile. Dar a fi decidabil este închis sub complement, așa că ar trebui să fii conștient de asta. Dar fiind... OK. Vom ajunge la asta într-un minut. Dar dacă... așa oricum, deci dacă ai o limbă și ea este un complement ușor de recunoscut, de unde știm că limba este decidabilă? Deci, în primul rând, să luăm cele două mașini Turing, M1 și M2, care recunoaște A și A-complementul. Și le vom pune împreună pentru a obține o decizie pentru A. Și asta va funcționa așa. Se va numi T. Deci T spune, la intrarea w, ce va face, va alimenta w în M1 și M2 ambele. A este limba, apropo, da. A este... când spun că este Turing-recunoscut, știi, Turing-recognizable se aplică doar limbilor. Deci da, A este adesea acest simbol pe care îl voi folosi pentru limbi, uneori pentru un automat. Dar A va fi de obicei o limbă. Deci, acum, încerc să fac T să fie un decident pentru A din recunoașterea pentru A și A-complement. Așa că voi lua o intrare în T și o voi introduce în ambele dispozitive de recunoaștere, M1 și M2. OK, o să le rulez în paralel. Ceea ce este frumos este că, deoarece M2 recunoaște complementul a ceea ce recunoaște M1, fiecare șir va fi acceptat fie de M1, fie de M2, deoarece fiecare șir este fie un A sau un A-complement. Deci, dacă rulez M1 și M2 pe w până când una dintre opriri sau una dintre ele acceptă, știu că nu voi alerga pentru totdeauna pentru că, în cele din urmă, unul sau celălalt trebuie să accepte. Și apoi am primit răspunsul meu pentru că dacă M1 acceptă, atunci știu că sunt în limba. Dar dacă M2 acceptă, știu că sunt în complementul limbii, așa că sunt în afara limbii. Deci, dacă M1 acceptă, atunci T ar trebui să accepte. Dar dacă M2 acceptă, atunci T ar trebui să respingă. , Deci asta dovedește acea mică teoremă drăguță scrisă în partea de sus cu albastru. Așa că mi-am luat decizia pentru A construit din recunoașterea pentru A și complementul A. Acum, imediat, rezultă că complementul lui A,TM nu este Turing-recognoscibil pentru că știm că A,TM în sine este recognoscibil, dar este indecidabil. Dacă și complementul ar fi de recunoscut, atunci A,TM ar fi decidabil, dar nu este. Deci, atunci când ceva este decidabil, fie el, fie complementul său trebuie să fie de nerecunoscut. Și în cazul A,TM, trebuie să fie complement, deoarece am arătat deja că este în sine este recunoscut. Deci asta este dovada asta. Deci, iată o mică imagine a felului în care arată lumea acum, dacă aveți aici, în mijloc sunt limbile decidabile - deci toate acestea sunt limbi, această diagramă Venn a limbilor. Am arătat mai devreme, obișnuitul, lipsit de context, decidabil, de recunoscut. Aici, am ceea ce recunosc și ceea ce numesc co-Turing recognoscibil. Aceasta este colecția tuturor complementelor de limbi recunoscute. Deci A,TM bar, A,TM complement este complementul unui limbaj recunoscut. Această regiune aici sunt toate complementele limbilor recunoscute sau așa-numitele limbi recognoscibile co-Turing -- complement de. Deci A,TM este de această parte. Complementul A,TM este de partea aceea. Dar dacă ceva este în ambele, în virtutea acestei teoreme de aici, atunci este decidabil. OK, ultimul check-in pentru ziua respectivă. Din ceea ce am învățat până acum, ce proprietăți de închidere putem dovedi pentru clasa de descurajare a limbilor recunoscute? Alegeți tot ce se aplică. Ei bine, după cum am spus, nu trebuie să înțelegi bine. Să nu petrecem prea mult timp pe asta pentru că vom vorbi puțin despre asta. Aproape toate... sunt închise sub aproape toate, dar nu toate. Pentru că... am terminat aici? Cred că am terminat... 5 secunde. OK, iată-ne, terminând sondajul. Nu sunt sigur care este sensul ștergerii [râdelor] răspunsului tău aici. Tuturor le place unirea, cred. Sunt închise sub toate aceste operațiuni, cu excepția complementului. Dar tocmai am dovedit că nu este închis sub complement, așa că sunt puțin nedumerit de ce avem atâtea voturi pentru închidere sub complement. Avem aici, A,TM este Turing-recunoscut, dar A,TM-complement nu este Turing-recunoscut. este chiar aici pe diapozitiv. Nu încerc să te fac să te simți rău, dar încerc doar să subliniez că gândești, te rog. Așa că acum închidere sub unire și intersecție, adică, ai putea obține acele răspunsuri doar rulând lucrurile în paralel, așa cum am făcut noi dovezile aici. Pur și simplu rulați ambele mașini. Și dacă amândoi dau... Adică, e puțin complicat, presupun. Dacă oricare dintre ei acceptă, atunci poți accepta. Sau dacă amândoi acceptă, doar așteptați până când amândoi acceptă. Altfel, continui să alergi. Deci primele două sunt destul de simple. Închidere sub concatenare-- și asta va fi similar. Încercați doar toate modurile posibile de a tăia sfoara în două bucăți și de a rula în paralel. Și dacă găsești vreodată o modalitate de a-l tăia, și le conduci pe cele două și le pui acele două părți în paralel și dacă amândoi acceptă, atunci poți accepta. Și steaua este, din nou, foarte asemănătoare. Deci astea nu sunt prea rele. Dar recunosc, știi, nu este prea mult timp să te confrunți cu ceva cu care tocmai te obișnuiești. Deci haideți să vorbim despre ultimul subiect al zilei, care chiar ne va pregăti pentru prelegerea de marți săptămâna viitoare. Și așa vom arăta că alte limbi sunt indecidabile, ceea ce mă aștept să fiți capabili să faceți. Aceasta este procedura standard pentru a arăta că limbile sunt indecidabile folosind ceea ce se numește metoda reductibilității. Și ceea ce face este că este nevoie, ca punct de plecare, de un limbaj despre care știm deja că este indecidibil -- de obicei, A,TM -- sau ar putea fi altul despre care ați demonstrat anterior că este indecidabil -- și se folosește de asta. informațiile care să arate că alte limbi sunt indecidabile. Și folosește ceea ce se numește reductibilitate. Vom aborda asta cu mai multă atenție data viitoare. Dar, practic, reductibilitatea este o modalitate de a folosi o problemă pentru a rezolva o altă problemă. Și așa vom arăta, de exemplu, să aruncăm o privire la problema numită problema opririi, care este ca și celebra problemă pentru mașinile Turing. Vrei doar să știi dacă se oprește, nu neapărat dacă acceptă. Deci este foarte asemănător, dar nu exact la fel. Și vom arăta că această problemă de oprire este la fel de indecidabilă. Acum am putea să ne întoarcem și să facem toată diagonalizarea, dar asta pare că... ei bine, asta e mai multă muncă decât este necesar acum că știm deja că A,TM este indecidabil, pentru că vom arăta că putem reduce problema A,TM la problema opririi. Și vom explica din nou ce înseamnă asta mai târziu. Dar ideea este -- și așa cum vom arăta într-o ilustrație în scurt timp -- că, demonstrând prin contradicție dacă HALT,TM ar fi decidabilă, atunci A,TM ar fi decis. Și știm că A,TM nu este decizibil. Și asta este contradicția noastră. Acum, modul în care vom arăta că, dacă HALT,TM este decidabil, atunci A,TM este decidabil este să folosim un decident pentru HALT,TM pentru a decide A,TM cu o modificare adecvată. Deci, practic, vrem să transformăm un decident HALT,TM într-un decident A,TM . Și așa vom reduce problema rezolvării A,TM la problema rezolvării HALT,TM. Să facem doar un exemplu. Dacă ai mai văzut-o înainte, evident, nu va fi greu. Dar pentru mulți dintre voi care nu l-ați văzut până acum, o fac parțial de data aceasta doar ca să o putem face din nou data viitoare. Și poate că se va afunda în virtutea repetării. Deci, din nou, așa cum tocmai am spus, vom presupune că problema HALT,TM este decidabilă și vom folosi asta pentru a arăta că A,TM este decidabilă, ceea ce știm că este fals. Am arătat mai devreme că nu este. Deci, să presupunem că avem un decident pentru HALT,TM. Îl vom numi R. Și vom construi din R un decident pentru A,TM, vom numi S. OK? Deci suntem, din nou, o dovadă tipică prin contradicție. Presupunem opusul a ceea ce încercăm să dovedim. Și atunci vom obține ceva nebunesc. OK, deci aici, treaba mea acum, este să presupun că am R, care este un decident HALT,TM. Deci acum, presupun că știu cum să decid dacă o mașină Turing și o intrare se oprește în cele din urmă... Nu. Neapărat ar accepta, doar dacă se oprește. Este de imaginat. Trebuie să mă îndurați aici. Este de imaginat că ați putea găsi o modalitate de a testa dacă mașinile Turing se opresc la intrarea lor, chiar dacă acum știm că testarea dacă acceptă intrarea lor nu este decidabilă. Așa că trebuie să fii deschis la posibilitatea ca problema HALT să fie decidabilă și vom arăta că asta nu se poate. Deci vom arăta că, dacă am putea decide problema opririi, atunci o putem folosi pentru a decide problema acceptării. OK, deci cum vom face asta? Așa că imaginați-vă cum putem rezolva problema opririi. Deci, să rezolv A,TM, ceea ce este treaba mea, așa că S ar trebui să rezolve A,TM. Construiesc o mașină Turing așa cum decide A,TM. Voi folosi primul... Îi dau M și W. O să-l introduc în R, deoarece asta e tot ce am. Vezi dacă R îmi spune ce se întâmplă. M on w măcar se oprește? Ei bine, dacă R spune, nu, nu se oprește, ei bine, atunci am terminat pentru că dacă M nici măcar nu se oprește pe w, atunci nu ar putea accepta w. Deci, în acel moment, știu că M nu acceptă w și pot respinge imediat. Deci R, puteți vedea cum ar putea fi de ajutor. Dar va fi util în orice fel, deoarece dacă R spune că M ține, ei bine, atunci, sunt și eu bun pentru că nu știu încă răspunsul, dar ceea ce știu este că acum pot simula M pe w până când se oprește pentru că R mi-a spus că se oprește. Deci nu trebuie să-mi fac griji că intru într-o buclă. Așa că S poate fi încrezător în a fi un decident pentru orice ar face, deoarece acum rulez M pe w cu garanția că se oprește. Și acum, asta o să- mi spună-- acum, în cele din urmă, simularea lui M pe w va ajunge la o acceptare sau respingere. Și acesta va fi răspunsul de care am nevoie. Deci, dacă M este acceptat, atunci acceptă. Și dacă M este respins, atunci respingeți. Și așa rezolvă S A,TM folosind R, care rezolvă HALT,TM. Dar S nu poate exista. Prin urmare, R nu poate exista. Și, prin urmare, HALT,TM nu poate fi decidabilă. BINE? Deci repede... OK, nu sunt sigur ce diagramă ai vrut să arăt. Dar oricum, poate putem face asta. Practic suntem la sfârșitul orei sau la sfârșitul celor 90 de minute. Deci haideți să facem o scurtă recenzie. Și dacă rămâi, mă bucur să mă întorc și să mă uit la oricare dintre celelalte diapozitive despre care s- ar putea să fi omis ceva . OK, deci doar pentru a recapitula, am arătat că numerele naturale și numerele reale nu au aceeași dimensiune folosind acea definiție a corespondenței unu-la-unu pentru a introduce metoda diagonalizării. Am folosit metoda diagonalizării pentru a arăta că A,TM este indecidabil. De asemenea, am arătat acea mică teoremă că, dacă limba și complementul ei sunt recunoscute, atunci limba este decidabilă. Și din asta, am concluzionat că complementul A,TM nu este de recunoscut. Și apoi am arătat, cel puțin în virtutea unei introduceri în metodă, metoda reductibilității pentru a arăta că HALT,TM este indecidabil. Și asta a fost prelegerea de astăzi. Și suntem și suntem la sfârșitul orei. Deci de ce nu... am terminat. Vă puteți deconecta. Și dacă vrei, voi rămâne. OK, OK, aceasta este o întrebare bună aici. Așa că primesc o întrebare despre complementul A,TM, care este... deoarece avem un dispozitiv de recunoaștere pentru A,TM, dacă fac dreptate acestei întrebări, avem un recunoaștetor pentru A,TM, deci de ce nu putem inversa răspunsul? Întoarceți răspunsul și acum, avem un dispozitiv de recunoaștere pentru complementul A,TM, A,TM-complement. Deci de ce nu funcționează? Ei bine, motivul care nu funcționează este că dispozitivul de recunoaștere pentru A,TM ar putea respinge unele lucruri prin loop. Și acum, dacă răsturnați doar acceptarea și respingerea, când atinge una dintre acele stări de oprire, va da răspunsul invers. Dar când respinge prin looping, va continua să respingă prin looping. Deci nu vei primi limbajul complementar . Deci, dacă ar fi de ajutor, pot reveni la acel slide aici, care demonstrează că complementul A,TM este de nerecunoscut pentru că poate ar trebui să începem cu partea de jos. Știm că A,TM este recognoscibilă și indecidabilă, nu? Am demonstrat deja aceste două fapte. A,TM este recunoscută din mașina universală Turing și este indecidabilă prin argumentul diagonalizării. Cele două lucruri împreună ne spun că complementul trebuie să fie de nerecunoscut, deoarece dacă o limbă și complementul ei sunt ambele recognoscibile - și știm deja că limba în sine este recognoscibilă. Așa că acum, dacă complementul este de asemenea recognoscibil, limbajul va fi decidabil prin teorema superioară. Deci trebuie să fie cazul în care fie limba în sine este de nerecunoscut, fie complementul său este de nerecunoscut. Știm că limba este recunoscută. Așa ne-a spus mașina universală Turing. Deci, singurul lucru rămas este ca complementul să fie de nerecunoscut. Ar trebui să revizuiți asta dacă nu ați înțeles, deoarece acesta este genul de raționament pe care îl vom construi pe astfel de lucruri. Așa că cred că este bine să te asigur că înțelegi. BINE. OK, diagrama din dreapta, deci aici este doar o diagramă Venn. Am aruncat asta în ultimul moment aici. Eram îngrijorat că ar fi confuz. Acea parte este -- încerc să arăt că cele trei clase despre care am vorbit deja -- limbile care sunt decidabile, limbile care sunt recunoscute la Turing și limbile ale căror complemente sunt recunoscute la Turing. Acestea sunt trei clase separate de limbi. Și aceia vin aici în acele trei regiuni. Acestea sunt cele decidabile. Iată-le pe cele recunoscute. Și iată-le pe cele ale căror complemente sunt recunoscute. Acum, dacă o limbă este atât în ​​ceea ce este recognoscibil, iar complementul său este recognoscibil -- deci este în ambele regiuni mai mari aici -- atunci această teoremă vă spune că este decidabilă. Deci, de aceea intersecția acestor două regiuni este marcată ca fiind decidabilă, deoarece asta înseamnă că ești în ambele. BINE? Dar știm că A,TM se află aici ca fiind recunoscut, dar nu determinabil. Deci A,TM este în partea de recunoaștere, dar nu este în complementul de A,TM în sine. Complementul lui A,TM este complementul unui recognoscibil, dar în sine nu este recognoscibil și nu este decidabil. Deci ai această latură a frumosului, știi... Sper că crezi că este frumos, dar este un fel de încercare de a rezuma lucrurile în această mică diagramă Venn. Așa că cred că mă voi închide. Și ne vedem pe toți marți. Și să aveți un weekend bun. Pa! Pa.