[SCRÂȘIT] [FOȘTIT] [CLIC] MICHAEL SIPSER: Bine, de ce nu începem? Este ora 2:35, este timpul să începem. Deci toți, bine ați revenit... mă bucur să vă văd pe toți. Ei bine, măcar câțiva dintre voi... mă bucur că sunteți aici. Deci, să vedem. De ce nu primesc un aspect, așa cum fac de obicei, unde am fost, unde mergem astăzi. Voi vorbi puțin despre teme, pentru că am primit câteva întrebări despre asta. Și apoi vom interveni. Așa că am vorbit despre mașinile Turing, care va fi modelul nostru preferat pentru restul semestrului, deoarece mașinile Turing sunt modelul pe care îl folosim pentru a captura calcularea de uz general. Și ne-am uitat la mașinile Turing în diferite variante ale mașinilor Turing -- benzi multiple, nedeterministe și așa mai departe. Este puțin recapitulând istoria subiectului, când oamenii s-au uitat la o varietate de moduri diferite de a formaliza noțiunea de algoritm. Și au arătat că toate aceste formalizări diferite erau echivalente una cu cealaltă, ceea ce a condus la teza Church-Turing că toate aceste modele - fiecare dintre aceste modele surprinde într-adevăr ideea noastră intuitivă despre ceea ce înțelegem prin procedură sau algoritm pentru -- cel puțin pentru a aborda lucruri precum probleme matematice și probleme precise de acest fel. Așa că am vorbit despre teza Church-Turing. Am mai vorbit despre o notație pentru codificări și mașini Turing. Vom trece în revistă pe scurt. Așa că astăzi vom oferi o grămadă de exemple de algoritmi de mașină Turing pentru rezolvarea unei varietăți de probleme diferite. Ar trebui să spun doar algoritmi, nimic special despre mașinile Turing. Mașinile Turing vor fi doar omologul nostru oficial. Dar de acum încolo, vom folosi teza noastră Church-Turing într-un fel pentru a vorbi doar despre algoritmi în general, pentru că acesta este cu adevărat interesul nostru. Mașinile Turing sunt doar modul nostru de a raționa matematic despre ele , dar în cele din urmă suntem cu adevărat interesați de înțelegerea algoritmilor. În ceea ce privește formatul orei de astăzi, voi încerca un mic experiment. Vom avea mici pauze pe parcurs, precum și pauza mare de cafea la mijloc. Vom avea câteva mini pauze, pentru că uneori simt că într-adevăr nu este suficient timp pentru ca oamenii să scrie pe chat-- întrebări în chat, pentru că lucrurile pur și simplu continuă. Și așa vom avea o mică pauză după... cam după fiecare diapozitiv. Unele dintre ele vor fi puțin mai lungi decât altele. În cazul în care aveți întrebări, puteți să mi le puneți mie sau AT, iar noi vom încerca să vă răspundem cu privire la acestea. Trec mai departe atunci, așa că astăzi, doar ca o scurtă trecere în revistă, mașinile Turing, pe măsură ce le-am configurat, au... la orice intrare w, au trei rezultate posibile. Mașina Turing poate opri și accepta w, poate opri și respinge w sau poate merge pentru totdeauna pe w, care respinge prin bucla în limba noastră. O mașină Turing poate recunoaște un limbaj, colecția de șiruri vechi pe care le acceptă. Și dacă mașina Turing se oprește întotdeauna, spunem că ea decide limba și este un decident și, prin urmare, acea limbă este un limbaj hotărât, un decident Turing. Adesea spunem doar decidabil, pentru că nu prea avem o noțiune de a decide în alte modele, așa că vorbim adesea despre Turing-recunoscut sau doar decidabil. Sau vom spune uneori doar recunoscut, când înțelegem că vorbim despre mașinile Turing. Am vorbit pe scurt despre codificări. Când scrieți între paranteze, unele obiecte -- oricare ar fi ele -- ar putea fi șiruri, ar putea fi mașini, ar putea fi grafice, ar putea fi polinoame -- le reprezentăm ca șiruri și poate o colecție de obiecte împreună reprezentate ca un șir în ordine, astfel încât să putem prezenta acele informații ca o intrare către o mașină. Și vorbim despre... limbile noastre colecțiile noastre de șiruri. Și o notație pentru a scrie o mașină Turing va fi pur și simplu acea descriere în limba engleză pusă între ghilimele pentru a reprezenta modul nostru informal de a vorbi despre obiectul formal pe care l-am putea produce, dacă am dori. Dar nu o să-ți cerem niciodată să faci asta. OK, acum lasă-mă să văd. Să luăm o pauză rapidă, așa cum am promis. Dacă există întrebări rapide aici, puteți adresa. Să vedem... am o mulțime de întrebări aici. Bine, de ce nu mergem mai departe? Și unele dintre aceste lucruri sunt întrebări bune. Cineva a întrebat, poți... cum îți dai seama dacă mașina este în buclă sau dacă într-adevăr durează foarte mult? Nu poţi. Asta o să dovedim nu în prelegerea de astăzi, ci o să dovedim asta joi. Pur și simplu nu poți spune. Deci, dacă aceasta se referă la problema 5, va trebui să găsiți o altă modalitate de a face -- să rezolvați acea problemă fără a ști dacă mașina se va opri vreodată. Și cineva a întrebat, cum putem spune dacă o descriere în limba engleză este posibilă pentru o mașină Turing? Ei bine, puteți oricând să scrieți o descriere în limba engleză pentru orice mașină. Are-- ar putea avea un aspect foarte tehnic, dar dacă îl puteți scrie într-un mod formal ca stări și tranziții, atunci puteți pur și simplu să scrieți o descriere în limba engleză, care ar fi, urmați acele stări. OK, hai să mergem mai departe. OK, acesta va fi primul nostru exemplu de algoritm care va răspunde la o întrebare despre automate. Și este o problemă foarte simplă. Este o problemă foarte simplă de rezolvat, pentru că vrem să începem ușor. Numele problemei este problema de acceptare pentru automatele finite deterministe, problema de acceptare pentru DFA. Și o voi exprima, așa cum fac întotdeauna, ca o limbă. Deci, cu acest limbaj aici, îl numesc ADFA-- care reprezintă problema de acceptare pentru DFA-- este colecția de perechi. B și w-- B este un DFA. w este considerat a fi un alt șir, care va fi o intrare pentru B. O să ne gândim la el ca la o intrare pentru B. Le-am pus pe cele două între paranteze pentru a reprezenta perechea ca un singur șir. . Nu vom face explicit care este forma codificării . Singurul lucru important este că codarea ar trebui să fie ceva simplă, dar că mașina Turing poate decoda înapoi în DFA și acest șir de intrare în acel DFA. Deci orice lucru rezonabil va fi o codificare satisfăcătoare din partea noastră... pentru noi. Deci aceasta este o codificare a celor doi într-un șir, și unde B este un DFA și B acceptă w. Deci, acum, dacă doriți să testați dacă ceva este membru ADFA, atunci, în primul rând, doriți să vă asigurați că șirul în sine pe care îl obțineți codifică într-adevăr un DFA și un șir. Deci trebuie să fie forma potrivită. Și odată ce știi asta, atunci ai DFA, ai șirul w și apoi vei face lucrul evident, care ar fi să simulezi B pe w și să vezi dacă de fapt acceptă w. Deci, acesta este conținutul acestui slide. Am de gând să- l notez doar pentru tine. Așa că voi da o mașină Turing, pe care o voi numi-- numele acelei mașini Turing va fi D A DFA. Pentru a vă ajuta să vă amintiți funcția acestui aparat. Acesta este un factor decisiv pentru limba de mai jos, limba ADFA. Acesta este doar un nume, dar... deci nu se întâmplă nimic de lux aici, dar doar pentru a ne ajuta să ne amintim, pentru că mă voi referi la unele dintre aceste mașini Turing mai târziu. Deci acesta este hotărârea pentru ADFA. Și o să vă descriu acea mașină și acea mașină decide limbajul ADFA. Deci ce înseamnă asta? Așa că mașina... o descriu acum în engleză, așa cum am promis. Vom lua un șir de intrare s și, mai întâi, vom verifica dacă s are forma corectă, așa cum am menționat -- are forma care este codificarea unui DFA și a unui w. Dacă nu este de această formă, mașina Turing ar trebui să respingă acea intrare imediat. Acum, nu am de gând să trec prin detalii despre modul în care va funcționa acea mașină Turing, deși voi spune puțin mai multe de data aceasta doar pentru a vă oferi o idee despre cum ar putea realiza asta de fapt. Dacă nu credeți că o puteți face cu o mașină Turing, credeți că o puteți face cu limbajul dvs. de programare preferat . Este suficient de bun, pentru că asta va fi... echivalează cu o mașină Turing. Deci, mai întâi, verificați dacă intrarea are forma corectă. Apoi veți simula calculul lui B pe w. Și apoi, dacă B ajunge într-o stare de acceptare, atunci știm că B acceptă intrarea și ar trebui să acceptăm, și o facem. Dacă B nu ajunge într-o stare de acceptare la sfârșitul lui w, atunci ar trebui să respingem, deoarece B nu acceptă w. BINE? Aceasta este descrierea mea despre această mașină. Să ne întoarcem la câteva detalii doar pentru a ne asigura că ne simțim confortabil cu asta. Deci, iată mașina noastră Turing-- D, decident pentru ADFA. Intrarea către acea mașină Turing, așa cum am menționat, va fi B și w, cu condiția să aibă forma corectă. Deci, acesta este ceea ce acest șir S ar trebui să fie de acea formă. Și ce înseamnă asta? Este doar o codificare a mașinii w și a șirului -- a mașinii B și a șirului w. Lasă-mă să-l notez. Aici este B scris într-un mod complet explicit, în care doar enumerați stările lui B, alfabetul lui B, funcția de tranziție ca tabel, starea de început și setul de stări de acceptare - doar scrieți-l jos în mod explicit, așa cum ați putea face dacă ați dori doar să descrieți acea mașină într-un mod complet formal, iar apoi să scrieți cu șirul este... orice ar fi. Odată ce DADFA are asta ca intrare, poate merge mai departe și face acel calcul. Și doar pentru a încerca să o fac puțin mai explicită, voi surprinde asta aici spunând, să-i dăm mașinii Turing o bandă suplimentară, pentru că știm deja că modelul cu mai multe benzi este echivalent cu modelul cu o singură bandă. -- ne ușurează puțin viața. Și în timpul realizării acelei simulări, ce vrem să urmărim? Ei bine, care este starea actuală a lui B, DFA, în timp ce citim simbolurile lui w? Și unde suntem acum? Deci îl voi numi k, care este locația capului de intrare pe w. Câte simboluri ale lui w am citit? BINE? Și asta este tot ce voi spune despre cum arată această mașină Turing D. Oh, mai este un lucru pe care vreau să-l spun pentru... care urmează, pentru că aproape toate mașinile Turing despre care vom vorbi astăzi și despre care vom vorbi în viitor vor dori adesea să verifice dacă aportul lor este de forma corectă. Nu vreau să repet asta de fiecare dată, pentru că asta va fi presupus. Așadar, prescurtarea mea este să spun că intrarea mea este de forma pe care o caut și care a inclus în ea verificarea dacă șirul - șirul de intrare este de acea formă și vom respinge dacă acesta nu este. Așa că toate mașinile noastre Turing vor începe, la intrare, șirul are o anumită formă, apoi vor ieși și vor face ceva cu el. BINE? OK, așa că permiteți-mi să încerc să răspund la câteva dintre întrebările pe care le-am primit aici, pentru că cred că acest lucru este important ca o modalitate de a ne face pe toți să începem. Acum, cineva m-a întrebat, putem folosi argumente de această formă? Cineva întreabă, putem folosi... putem da descrierea noastră a unei proceduri, dacă înțeleg corect, ca folosind un alt limbaj de programare? Ei bine, de obicei, vrei doar să te asiguri că ești înțeles. Dacă doriți să faceți asta la o temă, nu aș susține să vă scrieți algoritmul în Java, pentru că va fi greu de citit. Dar notează-l într-un limbaj de pseudoprogramare, dacă vrei, doar pentru a te asigura că este clar că... ceea ce faci. Probabil că engleza va fi cea mai ușoară pentru tine -- chiar dacă această persoană spune -- crede că ar fi mai ușor să o faci în ceea ce privește o limbă formală. Ei bine, orice ar fi mai ușor... atâta timp cât putem înțelege. Aceasta este o întrebare bună aici pe care trebuie să o pun. Ce se întâmplă dacă B-- iată-l pe B-- intră într-o buclă pe w? Ei bine, asta nu se va întâmpla. B este un DFA. DFA-- se deplasează de la stat la stat de fiecare dată când citesc un simbol al lui w. Când ajung la sfârșitul lui w, este sfârșitul poveștii. Nu mai sunt calcule de făcut. Așa că știm exact în câți pași va face B vreodată -- va lua același număr de pași ca lungimea intrării. Atâte mișcări trebuie să facă. B ca DFA nu face niciodată bucle. Deci asta ar fi o problemă dacă s- ar face buclă, dar nu. Acea intrare nu face niciodată buclă. Deci am verificat că D este un decident? Ei bine, cred că tocmai am făcut-o. Din punctul meu de vedere, am spus destule pentru a fi siguri că D este un decident. Nu există niciodată niciun motiv ca D să fie... pentru ca mașina aia DADFA Turing să intre într-o buclă. Locația capului de intrare se referă la locul în care ne aflăm pe șirul w? Da. Și cineva mă întreabă, acesta este nivelul de detaliu pentru teme? Da. Asta e tot ce vreau. Este tot ce caut. BINE? Să mergem mai departe. Va trebui să... altfel nu vom ajunge niciodată nicăieri. Sunt o mulțime de întrebări aici. Sunt întrebări bune. Deci de ce nu mergem mai departe? Unele dintre acestea s-ar putea rezolva pe măsură ce vom analiza exemple suplimentare, pentru că toate cele de astăzi sunt cam exemple. Să vorbim despre problema similară, problema acceptării, dar acum pentru NFA-uri. Așa că acum, de fapt, NFA-urile se pot bucla, așa că trebuie să ne gândim la ce ar putea privi. Dar înainte de a ne avansa pe noi înșine, așa că acum problemele de acceptare pentru NFA păreau foarte asemănătoare, cu excepția faptului că B va fi un NFA. Va fi și un limbaj decizibil. Și acum avem Turing machine A-- DANFA, decident pentru ANFA care decide ANFA. BINE? Așa că acum, așa cum am promis, iată noua noastră formă pentru a scrie mașina noastră Turing. Pe intrarea B, w, presupunem că B-- pe baza contextului, uneori poate doriți să spuneți în acest moment, ce sunt B și w. Dar din context, știm care sunt acestea. Vor fi un NFA și o intrare w pentru acel NFA. Vreau să intru în soluție. În primul rând, înainte să ne uităm la soluția asta, noi... mașina Turing ar putea simula NFA pe intrarea w. Și trebuie să fii atent la acea simulare că nu ajungi să faci bucle, pentru că nu uita, un NFA ar putea avea mișcări epsilon și ar putea face bucle pe acele mișcări epsilon. Și asta ar fi o problemă, dacă nu ești atent la modul în care faci acea simulare. Acum, cred că, dacă ai simula un NFA, nu ai fi... nu ai urma buclele pentru totdeauna. Și cred că poți-- fără a ajunge-- pentru că nu așa voi rezolva problema-- ai putea găsi o modalitate de a evita să fii prins și să te blochezi în bucle pentru un NFA. Deci, deși pare că ar putea fi o problemă, în ceea ce privește bucla pentru totdeauna, se dovedește că nu va fi o problemă - nu ar fi o problemă dacă ești atent. Dar oricum nu o voi rezolva așa , pentru că voi ilustra o metodă diferită de rezolvare a acestei probleme. Și asta este că am prezentat înainte o modalitate de a converti NFA-uri în DFA. Deci, mașina mea Turing va rezolva problema ANFA prin conversia intrării sale, care este un NFA, într-un DFA echivalent. Sun NFA B și DFA pe care l-am primit... transformându- l în B prime. Și ceea ce este frumos este că, în primul rând, știm deja cum să facem acea conversie, pentru că, în esență, am trecut peste asta în prelegere cu câteva prelegeri în urmă și este descris în detaliu în manual. Deci aceasta este o conversie pe care știm să o facem -- vom presupune că știm cum să o facem. Și putem implementa acel Turing-- acea conversie pe o mașină Turing. Apoi, odată ce avem DFA echivalent, ce facem cu asta? În diapozitivul anterior, am arătat cum să rezolvăm problema pentru DFA. Deci, dacă putem converti NFA într-un DFA și atunci știm deja cum să rezolvăm problema pentru DFA, atunci am terminat. Așa am să spun. Vom converti NFA într-un DFA și apoi voi rula acea problemă DADFA pe noua mașină pe care am produs-o. Deci, amintiți-vă că... această mașină de aici decide problema ADFA. Și acum voi accepta, dacă acea nouă mașină... dacă acea mașină Turing anterioară acceptă problema DADFA, mașina o acceptă și, practic, voi face orice face. Dacă acceptă, voi accepta. Dacă respinge, atunci voi respinge. Așadar, cred că lucrul pe care acest lucru ilustrează este ideea de a folosi o construcție de conversie în interiorul unei mașini Turing și apoi o mașină Turing construită anterior, practic, ca subrutină. Toate acestea sunt perfect legale și este genul de lucruri pe care o să facem o mulțime de lucruri și pe care ar trebui să fii obișnuit să faci asta... pregătește-te să faci asta și la temele tale. Și, de fapt, vă dau un alt indiciu în plus că problema 6 poate fi rezolvată în acest fel. BINE. În regulă, deci aici, hai să facem o scurtă pauză. Bine, am niște întrebări interesante aici -- cineva m-a întrebat, trebuie să fim expliciți despre cum vom simula acel NFA sau DFA? Pentru că nu știm câte stări are. Știi câte stări are. Odată ce vi s-a prezentat la intrare, puteți vedea, oh, aceasta este o mașină care are 12 stări -- pentru că vi se dă mașina și apoi puteți face simularea. Să vedem. Și cineva mă întreabă despre limitele puterii de simulare a unei mașini Turing. Aceasta este o întrebare pe care o voi amâna mai târziu, pentru că vă întrebați dacă o mașină Turing se poate simula singură. Și vom vorbi despre astfel de lucruri, dar asta va fi peste câteva săptămâni, așa că o să renunț la asta. Limbi decidebile -- cineva îmi pune o întrebare bună despre proprietățile de închidere ale clasei de limbi decidabile. Sunt închise sub intersecție, unire și așa mai departe? Da. Și limbile decidabile sunt, de asemenea, închise sub complement. Ar trebui să fie ceva la care ar trebui să te gândești. Dar da, este adevărat. Limbile recognoscibile, totuși, sunt închise sub unire și intersecție, dar nu sunt închise sub complement. Așa că vom demonstra în prelegerea de joi. Deci, o altă întrebare este, am fi putut doar să rulăm B pe w în acest -- pentru a rezolva această problemă, în loc să folosim reduced -- convertind-o într-o nouă mașină Turing-- primul B? Ei bine, da, am fi putut să facem asta. BINE. Cred că mai bine mergem mai departe. Nu vreau să mă blochez prea mult aici... am o mulțime de întrebări acolo, așa că îmi pare rău dacă nu ajung la toate întrebările. BINE. Sau puteți scrie și AT-urilor, evident. Sunt sigur că ești. OK, deci haideți să vorbim despre o altă problemă: problemă de gol pentru DFA. Îți voi oferi acum un-- doar un DFA-- B-- și nicio intrare. Și o să întreb, limba acelui DFA este setul gol, limba goală? Înțelegi problema, în primul rând? Îți predau doar un DFA și vreau să știu dacă acest DFA acceptă vreun șir de caractere sau este doar un DFA prost -- este întotdeauna un DFA foarte negativ, pur și simplu respinge totul -- și are limba goală? Cum spui? Nu este foarte greu, dacă te gândești la cum ai scrie un program pentru a face asta sau cum ai face-o singur, așa că este din nou o limbă decidabilă. Așa că vom oferi acum o mașină de decizie Turing pentru limba respectivă. Deciderul spune, ei bine, dau acel DFA-- Vreau să știu dacă limba lui este goală. Și ideea este exact ceea ce ai crede. Am să văd, există o cale de la starea de pornire a acelui DFA până la... o stare de acceptare a DFA? Dacă există o astfel de cale, atunci acel DFA va avea o intrare care merge pe acea cale și va fi acceptată. Și astfel limba nu va fi goală. Dacă nu există o astfel de cale, atunci în mod clar, acest DFA nu poate accepta niciodată nimic și, prin urmare, acest limbaj va fi gol. BINE. Acum, există mulți algoritmi de cale diferiți. Cred că ar fi puțin rar din partea mea doar... unii dintre voi cunosc algoritmi. Unii dintre voi nu cunosc algoritmi de verificare a căilor. Mi-aș dori să... dacă ai da un astfel de răspuns la o temă, să-mi dai o idee despre cum va funcționa acel algoritm . Nu fi prea înalt în privința asta. Deci, cea pe care o am în minte este cercetarea în amploare, dacă ați auzit de asta. Dar este un algoritm foarte simplu. Ceea ce voi folosi este un fel de procedură de marcare. Așa că voi începe prin a colora... iată asta... Ar fi trebuit să spun... acesta este DFAB-ul meu. Acesta este B aici. Ar trebui să încerc să risc să scriu despre chestia asta... hopa. Acesta este B. Oh, grozav... asta nu a ajutat. Deci acesta este B aici. Și modul în care voi testa dacă are o cale - dacă acceptă o intrare este să văd dacă există o cale de la starea de pornire la oricare dintre stările de acceptare. Și o voi începe prin marcarea stării de început și apoi marcând toate stările la care pot ajunge din stările marcate anterior și continui să fac asta până nu pot ajunge la nimic nou. Vor fi o serie de iterații aici care marchează din ce în ce mai multe stări până când nu va fi nimic nou de marcat, iar apoi spun, am marcat vreo stare acceptată? OK, să vedem cum scriu asta în engleză. Așa că am început să marchez starea de start. Repet până nu se marchează nicio stare nouă. Voi spune, marcați fiecare stare care are o săgeată de intrare dintr- o stare marcată anterior. Acceptă-- apoi, odată ce am terminat , acea buclă de repetare-- acceptă dacă nu este marcată nicio stare de acceptare , pentru că asta înseamnă-- nu uita, este puțin inversat față de ceea ce ai putea crede. Voi accepta dacă nu există nicio stare de acceptare marcată, pentru că asta înseamnă că nu există nicio cale către o stare de acceptare din starea de început, ceea ce înseamnă că limba este goală. Și EDFA sunt DFA care au un limbaj gol, așa că ar trebui să le accept. Dacă nu există nicio modalitate de a ajunge la o stare de acceptare, nu este marcată starea de acceptare. Și respinge dacă unii acceptă alocarea statului, pentru că atunci limba nu este goală. OK, deci asta e tot ce am vrut să spun despre asta. Cineva te întreabă, poți să spui ceva de genul lățimea versus [AUDIO OUT]. Cu cât ești mai schițat , cu atât mai multe șanse să fii prins de către gradator, care nu merge... avem o armată de oameni care notează astea probleme, și doar pentru a rămâne pe... fii pe partea sigură a schiței și, să zicem, nu tăia prea multe colțuri, pentru că s-ar putea să ratezi ceva. Sunt șanse că ar fi în regulă doar să spun cercetare în amploare, dar aș prefera dacă... ai fi mai în siguranță dacă ai spune puțin mai mult decât atât. BINE. Oh, aceasta este o întrebare bună aici. Cineva a întrebat, putem rula DFA pe toate short-- pe toate șirurile? Ei bine, în primul rând, un lucru-- a spune ceva rău ar fi, ei bine, pur și simplu introduceți toate șirurile posibile în DFA și, dacă oricare dintre ele-- dacă acceptă pe oricare dintre ele, atunci îi cunoaștem limba Nu este gol. Ei bine, acesta nu este un algoritm bun, pentru că poate rula pentru totdeauna, pentru că există o mulțime de șiruri. Există o infinitate de șiruri care pot fi introduse în acel DFA. Așa că o mașină Turing, dacă încearcă să devină o decizie, ar fi bine să nu facă operațiuni infinite care ar putea să dureze pentru totdeauna. Pentru a fi corect cu cel care propune aici, cel care a întrebat aici -- nu a întrebat asta -- spune, ei bine, putem alimenta toate șirurile până la o legătură, care ar fi numărul de stări ale mașinii în acest caz? Și da, asta ar funcționa, dar atunci ar trebui să argumentezi că este suficient. Și da, este suficient, dar nu ar-- nu ar fi suficient pentru a răspunde la problemă doar pentru a spune, hrăniți-o în acel număr de ei și am terminat. Ar trebui să spui de ce. BINE. O mulțime de întrebări aici... Voi merge mai departe. Să vedem. Problemă de echivalență pentru DFA-- acum vom duce lucrurile la următorul nivel-- întrebați, sunt două-- Vă voi oferi două DFA. Și vreau să știu, descriu ei aceeași limbă - recunosc aceeași limbă? BINE? Deci cum vom face asta? Deci, acesta este un limbaj determinabil. Iată hotărârea. Intrarea mea acum va fi două DFA-- din nou, reprezentate ca un șir, pentru că asta se ocupă mașinile Turing ca intrări. Dar pot despacheta acel șir în două DFA. Și există mai multe moduri diferite de a rezolva această problemă și sunt sigur că voi primi sugestii cu alte căi de rezolvat. Un lucru pe care l-ai putea face este doar să hrănești șiruri până la o anumită lungime. La fel ca înainte, nu poți să introduci toate șirurile posibile și să vezi dacă mașinile se comportă vreodată diferit pe vreuna dintre ele, pentru că aceasta este o operație infinită și am decis deja că nu putem face asta. Acum, dacă vrei să vorbești despre faptul că acesta este un recunoaștere, în loc de un decident, atunci s-ar putea să poți face așa ceva doar pentru a te asigura că... trebuie să fii pur și simplu atent. Să nu spun mai multe despre asta chiar acum. Dar cu siguranță, pentru un decident, nu poți merge pentru totdeauna. Nu poți avea operații infinite. Deci ar trebui să ai o întrerupere. Deci, puteți introduce toate șirurile posibile până la o anumită lungime, să zicem, în A și B și să vedeți dacă există vreo diferență. Acum, de fapt, am avut o problemă în setul de probleme 1, care spunea, dacă două DFA au limbi inegale, atunci vor vedea o diferență. Apoi va fi un șir care acționează diferit asupra lor, care este de lungime, cel mult, produsul numărului de stări ale acelor două mașini. Deci, puteți fie să faceți referire la acea problemă - ar fi o soluție adecvată - sau să o reproșați sau orice altceva. Asta ar fi bine. De fapt, puteți face chiar mai bine decât atât, așa cum a arătat problema opțională. Trebuie doar să mergi până la suma numărului de stări, nu până la produs. Dar asta de fapt este foarte greu de arătat. Nu am de gând să dovedesc așa. O să demonstrez într-un mod cu totul diferit, care nu necesită deloc nicio analiză - nu dovedesc ceva despre echilibru. Voi profita de ceva ce am arătat deja, și anume voi face un nou automat finit, un nou DFAC construit din A și B, care acceptă toate șirurile pe care A și B nu sunt de acord. Și îți voi arăta cum să... e ușor de făcut. Deci, în primul rând, să... în termeni de imagine, să înțelegem ce este aceasta. Deci aici avem - acesta este limbajul lui A, acesta este limbajul lui B scris ca diagramă Venn. Și unde sunt acele locuri în care nu sunt de acord? Ei bine, sunt fie în A, dar nu în B, fie în B, dar nu în A. Vă arăt aici în ceea ce privește regiunea albastră. Acesta are de fapt un nume numit diferența simetrică a acestor două seturi. Aceștia sunt toți membrii care se află în exact unul din cei doi, dar nu ambii. Dacă puteți face o mașină C care ar accepta toate șirurile din regiunea albastră, atunci ce facem cu acea mașină? Testăm lungimea sa, limbajul este gol, ceea ce am arătat deja cum să facem-- deoarece regiunea albastră este goală, asta înseamnă că L din A este egal cu L din B. Așa că voi face o mașină , un DFAC în care limbajul lui C este exact acea diferență simetrică. Sunt toate șirurile din A intersectate cu șirurile care nu sunt în B-- deci în A și nu în B-- sau în B și nu-- atunci nu A-- luați unirea acelor două părți. Și de unde știm că putem face C? Ei bine, avem acele construcții de închidere, pe care le-am arătat mai multe prelegeri înapoi. Acele instrucțiuni de închidere pot fi implementate pe o mașină Turing. Deci, o mașină Turing poate construi DFAC și apoi să folosească acel test de la câteva diapozitive înapoi, golul-- ultimul diapozitiv-- testerul de gol pentru DFA-uri pe C pentru a vedea dacă limbajul său este gol. Și acum, dacă limbajul lui C este gol, atunci știm că putem accepta, pentru că asta înseamnă cele două - că L din A este egal cu L din B. În caz contrar, putem respinge. BINE? Așa că iată o notă... Am de gând să-ți cer un check-in. Puteți folosi acest timp și pentru a- mi trimite alte câteva întrebări, dacă doriți. OK, iată check-in-ul meu. OK, acum, în loc să testez echivalența finite-- a DFA-urilor, vreau să testez echivalența expresiilor regulate. Deci aici sunt R1, R2. Expresiile regulate sunt numite problema expresiilor regulate EQ-- echivalente ale expresiilor regulate. Putem concluziona acum că această problemă este, de asemenea, decidabilă, fie imediat din lucrurile pe care le-am arătat deja; sau da, dar ar fi nevoie de ceva muncă suplimentară semnificativă; sau nu, pentru că intersecția nu este o operațiune obișnuită? Deci, să vedem dacă pot scoate asta aici... lansează sondajul. Începem. OK, cred că am terminat. Încă cinci secunde... OK, gata, setați, terminați. În regulă. Da, răspunsul corect este A. Practic am arătat deja acest fapt, pentru că... de ce? Deoarece am arătat că putem converti -- dacă vi se oferă două expresii regulate și vrem să testăm dacă sunt echivalente, ele generează același limbaj, le putem converti pe amândouă pentru a afla automate. Le putem converti în NFA, iar apoi NFA în DFA. Și apoi putem aplica ceea ce tocmai am arătat despre testarea echivalenței DFA. Deci, da, chiar decurge imediat din lucrurile pe care le-am arătat deja -- conversia, numărul unu, și apoi testarea echivalenței pentru DFA. Așa că nu prea este de lucru aici. Și, de fapt, ceea ce încerc să ilustrez cu acest check-in-- că, odată ce ați arătat cum să faceți un fel de test pentru un model, acesta-- se va aplica pentru toate modelele echivalente care am demonstrat că suntem echivalenti, deoarece mașina Turing poate face construcțiile care arată echivalența. OK, deci hai să mergem mai departe. Cineva nu a primit sondajul. Majoritatea oamenilor nu au primit sondajul? Ei bine, cred că majoritatea dintre voi l-ați prins. Ai ? Nu văd prea multe plângeri. Deci, dacă nu ați primit sondajul, ceva nu este în regulă cu configurația dvs. și va trebui să faceți check-in-urile înregistrate care vor fi lansate imediat după terminarea acestei prelegeri. Îmi pare rău. Dar ar trebui să vă dați seama ce este în neregulă cu configurarea acolo, pentru că cred că majoritatea oamenilor le primesc. OK, și cu asta, vom face o mică pauză, apoi vom continua mai târziu. Spune-mi cum este asta... ar trebui să fiu puțin mai rapid în privința micilor pauze pe care le facem, sau este bine pentru tine? Feedback-ul este întotdeauna... Încerc să fac asta cât de bine pot pentru voi toți. OK, cred că există un amestec de oameni care spun că aceste pauze sunt bune. Cineva spune că sunt puțin prea lungi, așa că voi încerca să le strâng puțin. Unii oameni spun ce... mai mulți oameni ar trebui să întrebe AT. Nu știu cum se descurcă AT-urile, în ceea ce privește -- Voi verifica cu ei după -- cât de bine le merge asta, în ceea ce privește întrebările. Dar cred că o anumită pauză este bună ca să nu... așa că este timp să punem întrebări. Altfel, ce rost are să ținem o prelegere live? Așa că vom începe imediat când acest temporizator se va scurge. Așa că fii gata să pleci în 55 de secunde de acum încolo. Doar pentru a confirma, pentru a arăta determinabilitatea echivalenței a două expresii regulate, trebuie să arătăm că putem folosi mai întâi o mașină Turing pentru a le converti în două DFA-uri? Dacă doriți să testați dacă două expresii regulate sunt echivalente, puteți da orice procedură pentru a face asta decizia pe care o doriți. Ofer doar o modalitate simplă de a face asta, care profită de lucrurile pe care le-am arătat deja. Dar dacă vrei să afli și să analizezi acele expresii regulate pentru a arăta că descriu aceeași limbă, ele generează aceeași limbă, fii oaspetele meu. Cred că ar fi complicat să faci așa. OK, deci suntem aproape gata să mergem aici, așa că hai să continuăm. Și lasă-mă să iau acest cronometru de aici. În regulă. Acum, vom vorbi puțin despre gramaticile fără context. Așa că am vorbit despre problemele de decizie pentru automatele finite. Să vorbim despre unele pentru gramatică. OK, acum am să ne pun o problemă similară. Îți voi da o... O numesc problema acceptării, dar... doar pentru coerență cu orice altceva, dar este într-adevăr problema generatoare. Așa că vă ofer o gramatică -- gramatică G fără context și un șir care este într-un șir. Și vreau să știu, este în limba G? Deci G generează w? Eu numesc asta problema ACFG. Deci, asta va fi din nou o decizie. Acestea devin puțin mai grele pe măsură ce mergem mai departe, așa că vă ofer o gramatică și un șir și vreau să știu, gramatica generează acel șir? Ei bine, nu este total trivial să rezolvi asta. Un lucru pe care ați putea încerca să-l faceți este să vă uitați la toate lucrurile posibile, toate derivatele posibile din acea gramatică și să vedeți dacă vreuna dintre ele duce la w-- vă conduce să generați w. Ei bine, trebuie să fii atent, pentru că, după cum am-- așa cum am arătat în unele dintre exemplele noastre, ai putea avea-- pentru că ai voie să ai variabile care pot fi convertite în șir gol, s- ar putea să ai au șiruri intermediare foarte lungi care sunt generate dintr-o gramatică, care apoi vă oferă în cele din urmă un șir mic de terminale care sunt generate, un șir mic în limbajul care este produs. Cu siguranță nu doriți să încercați orice derivație posibilă, pentru că există infinit de multe derivări diferite -- cele mai multe dintre ele generând, desigur, lucruri care sunt irelevante pentru șirul w. Dar trebuie să știi cum să întrerupi lucrurile și nu este imediat evident cum faci asta, cu excepția cazului în care ai făcut problemele cu temele pe care ți-am cerut să le faci, ceea ce sunt sigur că mulți dintre voi nu le-ați făcut... problemele punctului zero X, pentru că sunt... asta va fi util chiar acum. Și așa te voi ajuta să treci cu asta. Amintiți-vă - ar trebui să vă amintiți, dar poate că nu v-ați uitat la asta - ceva numit formă normală Chomsky, care este pentru gramatici fără context, dar permite doar regulilor să fie de un tip special. Și trebuie să arate așa. Ele pot fi o variabilă care merge la două variabile, în partea dreaptă, sau o variabilă care merge la un terminal. Acestea sunt singurele tipuri de reguli care vi se permit. Acesta este un caz special pentru șirul gol, dar să ignorăm asta pentru -- variabila de pornire poate funcționa și pentru șirul gol, dacă doriți să aveți un - șirul gol într-o limbă. Dar acesta este un caz special. Să ignorăm asta. Acestea sunt singurele două tipuri de reguli pe care le puteți avea într-o gramatică a formei normale Chomsky. Odată ce ai o gramatică a formei normale Chomsky - ei bine, în primul rând, sunt două lucruri. În primul rând, puteți converti oricând orice gramatică fără context în forma normală Chomsky. Deci asta este dat în manual. Tu faci lucrul evident. Nu voi petrece timp cu asta. Și nu trebuie să știi asta. Este doar puțin plictisitor, dar este simplu și există, dacă ești curios. Dar a doua lemă este lucrul care este important pentru noi, și anume că, dacă aveți o gramatică care este în forma normală Chomsky și un șir care este generat, fiecare derivație a acelui șir are exact de 2 ori lungimea șirului minus 1 pas. Dacă vă gândiți bine, aceasta este o lemă - foarte ușor de demonstrat. Cred că problema temelor vă cere să demonstrați că în 0.2 sau orice a fost în setul de probleme 1-- sau setul de probleme 2-- nu-mi amintesc. Regulile de acest fel vă permit să faceți șirul unul mai lung, iar regulile de acest tip vă permit să produceți un nou simbol terminal. Dacă lungimea w este n, veți avea n minus 1 dintre acestea și n din. Aceștia de aceea primești 2n minus 1 pași. Dar ideea este că nu-mi pasă exact câți. Doar că avem o limită. Și odată ce ai această legătură, viața este bună din punctul de vedere al oferirii unei mașini Turing care va decide acest limbaj -- pentru că aici este mașina Turing. Ce va face -- primul lucru este că va transforma G în forma normală Chomsky. Asta presupunem că știm să facem. Acum, vom încerca toate derivările, dar numai cele de lungime 2-- de două ori lungimea șirului minus 1, pentru că dacă orice derivație va genera w, trebuie să fie atât de mulți pași, acum că știm gramatica este în forma normală Chomsky. OK, așa că am transformat această problemă într-una care ar putea fi o problemă nelimitat de lungă și într-una în care se va termina după un număr fix de pași. Prin urmare, putem accepta, dacă oricare dintre acestea generează w, și respingem dacă nu. BINE? Înainte de a trece mai departe, deci aceasta răspunde la problemă - arată că această limbă este decidabilă, limba ACFG. Deci asta e ceva care... asigură-te că înțelegi. În principiu, încercăm derivații vechi de până la-- de o anumită lungime, pentru că asta este tot ce este nevoie atunci când gramatica este în această formă. Acum vom folosi asta pentru a demonstra un corolar, care este important pentru înțelegerea modului în care totul se potrivește. Și acel corolar afirmă că orice limbă fără context este o limbă decidabilă. Fiecare limbă fără context este decibilă. Acum, de ce rezultă asta din asta? Ei bine, să presupunem că ai un limbaj fără context. Știm că limbajul este generat de o gramatică fără context G. Asta înseamnă. Deci, puteți lua acea gramatică G și o puteți construi într-o mașină Turing. Deci va exista o mașină de termen care este construită cu cunoștințele lui G. Și acea mașină Turing își va lua w și va rula algoritmul ACFG cu w combinat cu un G care este deja încorporat în ea. Așa că va pune acea gramatică G în fața lui w, iar acum rulăm determinatorul ACFG. Va spune, degenerat w? Ei bine, asta va fi da de fiecare dată când w este în A. Și așa că această mașină de aici acum va ajunge să accepte fiecare șir care este în A, pentru că este fiecare șir pe care G îl generează. Deci, cred că asta am vrut să spun despre asta. Acum, simt că acest corolar de aici aruncă un pic de curbă. Și ne putem opri aici pentru o clipă doar pentru a ne asigura că înțelegeți asta. Lucrul dificil la acest corolar este că primesc adesea o întrebare pe care o înțeleg adesea unde este atunci când începem cu un limbaj fără context, cine dă... cum obținem G? Pentru că avem nevoie de G pentru a construi o mașină Turing M sub G. Deci știm că A este un limbaj fără context, dar de unde știm ce este G? Ei bine, ideea este că s- ar putea să nu știm ce este G, dar știm că G există, pentru că aceasta este o definiție a lui A fiind un limbaj fără context. Trebuie să aibă o gramatică fără context , prin definiție. Și pentru că G există, acum știu că mașina mea Turing, M sub G, există. Și asta e suficient pentru a ști că A este decidabil, pentru că are un decident care există. Acum, dacă nu ai de gând să-mi spui gramatica pentru G, nu o să-ți spun mașina Turing care decide A. Dar ambele există. Deci, dacă îmi spui G, atunci îți pot spune mașina Turing. Deci este o problemă subtilă, complicată acolo. Un anumit element mic poate de... uneori oamenii îl numesc neconstructiv, pentru că doar, într-un fel, arătăm doar că ceva există. Ne face treaba , pentru că arată că A este o limbă decidabilă. OK, deci nu atât de multe întrebări aici, poate că AT le primește. Deci hai să mergem mai departe. Iată un alt check-in. Deci, acum, putem concluziona că A-- în loc de ACFG, APDA este decidabilă? Oamenii primesc asta destul de repede. Încă 10 secunde-- trei secunde-- OK, o să-l închid-- terminați sondajul, partajați rezultatele. Da. Deci această problemă aici este APDA este decidabilă. Aproape mă întrebam dacă să dau sau nu acest sondaj, pentru că are -- este adevărat din același motiv ca și sondajul numărul 1, pentru că știm cum să convertim PDA-uri -- sau am afirmat că putem converti PDA-uri în CFG-uri. Și această convertire a dat în carte. Nu am făcut-o la prelegere, dar am spus doar că trebuie să știi acest fapt, dar nu neapărat să știi cum să o faci. Asta e ok. Dar adevărul este adevărat. Conversia este în carte și ar putea fi implementată pe o mașină Turing. Deci, dacă doriți să știți dacă limba unui PDA este goală, îl convertiți într-o gramatică fără context și apoi utilizați această procedură aici pentru a testa dacă este o limbă-- oh, nu goală-- Îmi pare rău. Problema de acceptare... Vreau doar să știu, PDA-ul acceptă o intrare? Spun gresit. Așa că vreau să știu, PDA-ul acceptă unele intrări? Convert acel PDA într- o gramatică și apoi văd dacă gramatica generează acea intrare, pentru că este o gramatică echivalentă. Deci, din nou, se folosește faptul că gramaticile și PDA-urile sunt echivalente și convertibile de la una la alta, la fel ca expresiile regulate și DFA-urile din sondajul anterior. Așa că trebuie să te simți confortabil cu asta, pentru că nici măcar nu vom mai vorbi despre asta. Vom trata doar acele lucruri, mergem înainte și înapoi între ele, uneori fără nici un comentariu. BINE. Deci hai să mergem mai departe. Problemă de gol pentru CFG-- sper că vă simțiți confortabil cu terminologia pe care o folosesc. Așadar, acum, problema golului pentru gramaticile fără context... Am de gând să vă dau doar o gramatică și vreau să știu dacă limbajul său este gol. OK, așa că nu uitați, am făcut asta pentru automate finite testând o cale. Nu prea avem căi aici. S- ar putea să vă gândiți că testați căi și automate împinse. Asta nu va funcționa cu adevărat, pentru că stiva este acolo. Deci, cum vom face acest test? Ei bine, există ceva de genul testării unei căi, doar lucrând cu gramatica în sine, cum să lucrezi înapoi de la terminale acum. Voi ilustra asta aici. Iată o gramatică foarte simplă și vreau să știu dacă generează șir de caractere? Evident, vă pasă doar de șirurile de terminale, pentru că acestea sunt lucrurile care sunt în limbaj - deci generează această gramatică șiruri de terminale? Deci, modul în care vom răspunde la aceasta este printr-o procedură de marcare, dar într-un anumit sens, vom începe de la terminale și vom lucra înapoi pentru a vedea dacă putem ajunge la variabila de pornire. Deci, mai întâi, vom marca toate simbolurile terminale și apoi vom marca orice se încadrează într-un șir de simboluri complet marcate, fie terminale, fie variabile - pentru că orice este marcat, știm, poate deriva un șir de terminale. Asta înseamnă. Orice este albastru poate obține un șir de terminale. Și așa că acum, dacă aveți o colecție din cele care sunt toate marcate, împreună pot genera un șir de terminale împreună. Și astfel puteți marca variabila asociată. Deci T merge la a. Deci poate fi prea simplu, dar vom marca T aici peste tot în gramatică. Deci, toate aceste T vor fi marcate, pentru că știm că T poate genera un șir de terminale. Acum să aruncăm o privire la R. R merge la un șir de simboluri care sunt toate marcate și asta înseamnă că acele simboluri pot, la rândul lor, să genereze șiruri de terminale. Deci vom marca R2. Încă nu putem marca S, pentru că nu știm încă dacă S are ceva nemarcat la care merge. Deci nu știm încă dacă S poate genera un șir de terminale. Dar R știm chiar acum, așa că vom marca R. Dar acum asta ne face să marchem acest R și astfel putem merge înapoi și putem marca S. Și continuăm să facem asta până când nu este nimic nou pentru marcă. Și aici am marcat totul, așa că în mod clar nu mai poți marca nimic. Dar s-ar putea să te oprești înainte de a marca totul. Și apoi vezi dacă ai marcat variabila de start sau nu. Și dacă ai, știi că limba nu este goală. OK, așa că hai să parcurgem asta în text. Marcați toate aparițiile terminalelor în G, apoi repetați până când nu sunt marcate variabile noi. Marcam toate aparițiile variabilelor A, dacă A merge la un șir de simboluri și toate acele simboluri au fost deja marcate, deoarece acestea sunt lucrurile despre care s-a demonstrat deja că generează un șir de terminale. Și așa că acum vom respinge dacă data de început -- variabila de început este marcată -- pentru că asta înseamnă că limbajul nu este gol -- și vom accepta dacă nu este. BINE? Voi răspunde aici câteva întrebări rapide. OK, cineva a întrebat dacă-- dacă înțeleg-- sunt și limbile obișnuite decizibile? Ei bine, amintiți-vă, limbile obișnuite sunt limbi fără context, iar limbajele fără context sunt decidabile, deci da, limbile obișnuite sunt decidabile. Unele dintre acestea vor fi prea lungi pentru a răspunde și încearcă să vină cu soluții alternative. Deci cred că vom merge mai departe. În regulă. La fel cum am făcut pentru automatele finite, am vorbit despre acceptare, am vorbit despre vid, am vorbit despre echivalență. Deci, ce zici de problema echivalenței pentru gramaticile fără context ? Vă voi oferi acum două gramatici fără context și aș dori să știu, acele două gramatici fără context generează aceeași limbă? OK, deci cum te-ai putea gândi la asta? Ei bine, un lucru... urmând unele dintre ideile pe care le-am avut deja, ai putea încerca să introduci șiruri în acele gramaticale. Știți cum să testați dacă acele gramatici individuale pot genera acele șiruri, așa că puteți încerca pur și simplu să introduceți șiruri în G și în H și să vedeți dacă acele gramatici nu sunt vreodată de acord sau dacă generează un șir. Găsiți un șir care spune că G generează, dar H nu generează. Și putem testa acel șir cu șir. Din păcate, avem o mulțime de șiruri de testat. Ar trebui să dăm o anumită limită dacă vom folosi această procedură - nu este clar care este limita. O altă idee ar putea fi să folosim construcția de închidere pe care o aveam de înainte. Deci, să ne gândim la asta... dacă asta ar putea funcționa. Dar, de fapt, permiteți-mi să dau aici răspunsul. Acest limbaj nu este decizibil. Nu există niciun algoritm - nici o mașină Turing, dar, prin urmare, nici un algoritm - care poate lua două gramatici și poate testa dacă generează aceeași limbă sau nu - pare, la prima vedere, cam surprinzător. Lucruri atât de simple, cum ar fi gramaticile fără context, pot fi totuși atât de complicate încât nu există nicio procedură care să poată spune dacă cele două - acele două gramatici generează aceeași limbă. Vom arăta asta săptămâna viitoare. O problemă înrudită, care este legată de temele tale pentru acasă -- aceasta este programată joi -- este testarea dacă o gramatică este ambiguă. Deci, având în vedere o gramatică, aș dori să știu, este acea gramatică o gramatică ambiguă sau nu? Generează un șir în limba acelei gramatici în două moduri posibil diferite, două sau mai multe moduri diferite? Există deci un șir care poate fi generat cu două părți diferite. Deci, problema cu testarea dacă gramatica este ambiguă-- nu este decidabilă. Așa că vă cer să faceți ceva greu, când trebuie să produceți acea gramatică care nu este ambiguă pentru limba respectivă. În general, testarea dacă o gramatică este ambiguă sau nu este o problemă determinabilă. Acum, sperăm că gramatica pe care o veți produce pentru a arăta că... acea gramatică fără ambiguitate pentru acea limbă pe care vă cer să o produceți nu va cere elevilor noștri să rezolve o problemă determinabilă, dar va fi clar bazat pe construcția acelei gramatici de ce nu este ambiguă. Așa că, sperăm, va trebui să dai o explicație a gândirii tale acolo. BINE. Și vom demonstra că problema testării ambiguității nu este decidabilă. Aceasta va fi o problemă cu temele în setul de probleme 3. OK. Ultimul check-in aici, ceva la care am făcut aluzie , dar nu am vrut să renunț. De ce să nu folosim aceeași tehnică pe care o folosim pentru a arăta că echivalența DFA-urilor este decidabilă, pentru a arăta că echivalența gramaticilor fără context este de dorit? Evident, ceva nu merge bine pentru că EQCFG nu este decidabil. De ce nu funcționează aceeași tehnică? Ei bine, care este răspunsul? Am o cursă adevărată aici, încă 15 secunde, aceasta îți dă ceva de gândit. În regulă. Să punem capăt. OK, ești gata să pleci. Măcar dă clic pe ceva. Bine, terminând sondajele, partajarea rezultatelor... OK, mulți dintre voi v-ați gândit, ei bine, CFG-urile sunt generatoare și DFA-urile sunt recunoașteri și asta este problema. Ei bine, nu chiar, pentru că am putea testa echivalența expresiilor regulate, acestea sunt generatoare. Nu are nimic de-a face cu a fi un generator sau nu, pentru că putem converti expresiile regulate în DFA-uri și apoi testam echivalența pentru DFA-uri, astfel încât-- nu este chiar o chestiune de a fi generați. Nu asta e problema. Problema este că nu putem urma aceeași construcție pe care am făcut-o pentru a arăta că EQDFA este decidabilă, deoarece limbajele fără context nu sunt închise sub acele operațiuni de care aveam nevoie pentru a face acea mașină de diferență simetrică - dacă vă amintiți cum a funcționat. Deci nu sunt închise sub implementare și nu sunt închise sub intersecție. Aveam nevoie de ambele pentru a construi acea mașină C, care accepta toate șirurile care sunt în diferență. BINE? Deci hai să continuăm. Să trecem acum la mașinile Turing. Aici lucrurile vor începe cu adevărat să devină interesante - sper că au fost interesante tot timpul, dar poate chiar mai interesante. Deci haideți să vorbim despre problema de acceptare pentru aparatele Turing, ATM. Această limbă va deveni un vechi prieten, dar tocmai o cunoaștem. Deci aceasta este problema. Vi se oferă acum o mașină Turing și o intrare, și vreau să știu, acceptă M acea intrare? Își acceptă acea mașină Turing intrarea? OK, deci nici asta nu va fi o problemă decidabilă. Așa că am schimbat treptele de la o grămadă de lucruri decidabile la o grămadă de lucruri indecidabile. Deci, aceasta nu este o limbă decidabilă. Vom demonstra asta joi. Acesta va fi scopul prelegerii de joi să demonstreze că ATM-ul este decidabil. Și acesta va fi într-adevăr un punct de plecare pentru a arăta că alte probleme sunt decidabile. Deci aceasta va fi prima noastră dovadă de decidebilitate. Dar știm că ATM-ul este recunoscut și că merită înțeles - din mai multe motive, dar pentru un singur lucru, ne va oferi un exemplu de problemă despre care știm că este recognoscibilă, dar nu decidabilă, deoarece vom dovedi indecizia. . Dar cred că este, de asemenea, de importanță istorică, acest algoritm de arătare... de recunoscut. Deci, să trecem prin acel algoritm. Este foarte simplu, cumva face lucrul evident. Următoarea mașină Turing-- o voi numi U, dintr- un motiv pe care îl voi clarifica într-o secundă. Acesta va fi un instrument de recunoaștere pentru ATM. Deci ia ca intrare un M și un w, și doar va simula M pe w, cam așa cum funcționează algoritmul decisor pentru ADFA. Dar acum mașina... în loc să fie un DFA, este o mașină Turing, iar mașina Turing ar putea merge pentru totdeauna. Și astfel, simularea poate să nu se oprească. Și aceasta este diferența cheie, care o face de la un decident la un detector. Deci, veți simula, doar ținând evidența casetei lui M, starea curentă a lui M, unde-- și veți continua să modificați banda pe măsură ce M o modifică. Și apoi, dacă M intră într- o stare de acceptare, atunci știți că M și-a acceptat intrarea, așa că și U va intra într- o stare de acceptare. Deci mașina U intră în starea de acceptare dacă M observă în timpul simulării că M intră într-o stare de acceptare. În plus, dacă un M intră într-o stare de respingere, atunci U intră și într- o stare de respingere. BINE? Acum o să spun ceva dincolo de asta, la care vreau să fii atent, care este genul de lucruri pe care le văd uneori spunând oamenii. Vrem ca U să respingă dacă M nu se oprește niciodată. De asemenea, asta e ceea ce ne dorim, pentru că dacă nu se oprește niciodată, atunci M respinge prin loop, așa că ar trebui să respingi și tu. Dar asta nu-mi place. Nu-mi place acea linie de aici, pasul 4 al mașinii Turing, pentru că nu există nicio modalitate ca o mașină Turing să determine-- sau cel puțin ca noi-- nicio modalitate evidentă-- și de fapt, nu va exista nicio modalitate , dar cu siguranță, în acest moment, nu există nicio modalitate evidentă pentru M să spună chiar... pentru U tu să spui dacă M se oprește sau nu. Ei bine, cu siguranță poți spune că înseamnă că nu se oprește niciodată. Cum poți lua acea hotărâre? Dacă aș vedea asta la o soluție, fie la un examen, fie la o temă, te-aș marca. Acest lucru nu este bun. Nu este ilegal pentru acțiunea mașinii Turing. Dacă M nu ține pe w, atunci ar trebui să respingi. Este corect. Și puteți face acest raționament extern algoritmului lui U, dar U va sfârși prin a respinge, pentru că nici nu este valabil. Nu știe niciodată că M respinge w în acest caz, dacă M respinge prin buclă. Doar merge orbește și face simularea lui M pe w-- și va sfârși prin a opri-- respinge prin buclă, dacă M respinge prin buclă. Dar asta este ceva pe care îl puteți argumenta dacă trebuie să faceți o dovadă sau să faceți un fel de raționament despre mașină, dar nu face parte din algoritmul mașinii. BINE. Acum, ce este, cred, din punct de vedere istoric, care este interesant despre această mașină U și de ce o numesc U este pentru că aceasta a apărut - această mașină U a apărut în lucrarea originală a lui Turing, unde a prezentat mașinile Turing. Apropo, nu le-a numit mașini Turing. Le-a numit mașini de calcul. Oamenii le-au numit apoi mașini Turing. Dar Turing a numit aceasta mașină de calcul universală. Asta e limba lui. De fapt, m-am uitat la ziar ieri doar pentru a- mi reîmprospăta amintirea. Și el oferă descrierea funcționării lui U în detaliu sângeros, cu toate tranzițiile și stările. El pune în cuie toată treaba -- ia pagini, și pagini, și pagini. Deci el o dă acolo. Deci aceasta este mașina de calcul universală originală, mașina universală Turing. Este mai mult decât o simplă curiozitate că acest lucru a apărut în lucrarea lui Turing, pentru că acest lucru sa dovedit a fi de fapt profund influent în informatică, pentru că a fost într-adevăr primul exemplu de mașină care a funcționat pe baza unui program stocat. Chiar a fost o idee revoluționară. În acele vremuri, dacă voiai să faci o mașină care să facă ceva diferit, trebuia să cablați... să recablați mașina. Dar iată o mașină care a funcționat pe baza instrucțiunilor. Iar instrucțiunile, într-un fel, nu diferă cu nimic de datele. Așa că acesta este ceea ce a fost... a devenit cunoscut sub numele de arhitectura von Neumann, dar von Neumann însuși a acordat credit mașinii Turing pentru că l-a inspirat să se gândească la asta. Și unii oameni susțin că într-adevăr -- numindu-l von Neumann -- o mulțime de oameni au venit cu acest concept cam în același timp, poate și alți oameni. Există Babbage și așa mai departe, și alții care-- Ada Lovelace-- de asemenea, care au venit cu noțiuni de programare, dar cred că este puțin diferit de acesta, în concept. Dar oricum, aceasta a jucat totuși un rol important în istoria subiectului. Deci, cu asta, cred că nu mai avem timp. Am de gând să revizuiesc rapid unde am fost. Așa că am arătat doar determinabilitatea diferitelor probleme. Acestea sunt toate limbile despre care am arătat că sunt decidabile. Am arătat că ATM-ul este recunoscut de Turing și cred că asta a fost tot ce aveam pentru astăzi. Așa că mă voi opri chiar aici. Voi rămâne și voi răspunde la câteva întrebări, iar AT pot răspunde la câteva întrebări, dacă doriți, prin chat. Și apoi am și orele mele de birou, care vor începe în aproximativ cinci minute și ceva, odată ce am pus totul la punct. OK, cineva a vrut să trec în revistă acest punct aici, ceea ce sunt bucuros să fac. Acest cod aici pe care îl descriu în engleză trebuie să fie ceva pe care îl puteți implementa pe o mașină Turing. Nu vom trece niciodată prin efortul de a construi funcțiile de tranziție, și stările și așa mai departe, dar trebuie să fim siguri că am putea, dacă ar trebui. Și cum ai putea face o mașină Turing să facă testul că M nu oprește? E ceva ce nu știm să facem. Pot să văd dacă M se oprește. În timpul simulării, pot vedea că M a intrat în starea de respingere Q sau în starea de acceptare Q, așa că pot spune în timp ce simulez că s-a oprit. Dar cum ar face mașina, sau cum ai ști că M este acum... cineva spune, ei bine, fă x dacă M nu ține niciodată. Ei bine, de unde îl știi pe M... cum poți să faci testul că M nu se oprește? Nu există o modalitate evidentă de a face asta. De fapt, nu există nicio modalitate de a face asta. Dar așa cum stau lucrurile acum, dovada ar fi pe tine să arăți cum să implementezi asta pe o mașină și pur și simplu nu există o modalitate evidentă de a face asta. Deci, cred că de aceea ar trebui să puneți aici doar lucruri pe care sunteți sigur că le puteți implementa, chiar dacă ar putea dura mult timp. Deci nu trebuie să vă faceți griji în legătură cu cât timp ar dura, dar trebuie să lăsați jos lucruri pe care sunteți sigur că le puteți, măcar, să le implementați în principiu. OK, deci cineva m-a întrebat despre problema echivalenței pentru gramaticile fără context, care nu sunt rezolvabile. De ce nu ar putea mașina să fie un sistem de logică la nivel uman, astfel încât computerul să poată deduce în mod logic dacă este sau nu decidabil? Facem o întorsătură în subiectul logicii matematice, care ar trebui să formalizeze într-un fel raționamentul. În cele din urmă, la ce s-a ajuns cu adevărat - că există anumite gramatici care sunt echivalente una cu cealaltă, dar nu va exista nicio modalitate de a demonstra că sunt echivalente într-un sistem rezonabil. Inechivalența pe care o poți dovedi oricând. Puteți arăta un șir acela -- puteți arăta că această gramatică o generează, această gramatică nu o generează. Celălalt nu este. Deci inechivalența pe care o poți dovedi întotdeauna, dar echivalența-- vor exista anumite perechi de gramatici care vor depăși capacitatea oricărui sistem formal rezonabil de a putea demonstra că sunt echivalente, pentru că poți chiar converti... - transformă acele gramatici în ceva care vorbește despre sistemul în sine, în cele din urmă. Veți ajunge cu un fel de paradox al lui Russell. Poate că asta depășește mai mult decât vrei să știi și sunt bucuros să vorbesc despre asta offline. Dar pur și simplu nu există nicio modalitate de a face o mașină Turing care să implementeze raționamentul uman și apoi să obțină răspunsul corect la toate perechile de gramatici - pur și simplu nu se poate face. La revedere. O să închid întâlnirea acum.