[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Bună, tuturor. Mă puteţi auzi? Da. Bun. Bine ai revenit la curs. Și așa suntem acum la prelegerea 10 și să vedem. Ce am făcut? Am tot vorbit despre indecidibilitate. Așa că am introdus, data trecută, reducbilitățile și reducbilitățile de cartografiere pentru a demonstra diferite probleme sunt indecidabile. Și de data aceasta, vom-- și astăzi, vom introduce o metodă mai sofisticată pentru a demonstra indezirabilitatea folosind reducbilitățile. Și asta se numește metoda istoriei calculelor. Și cam asta se folosește în toate cazurile mai grave în care oamenii s-au dovedit că problemele sunt indecidabile. Este aproape o metodă răspândită. În special, nu este un domeniu activ de cercetare în zilele noastre, dar în momente în care oamenii dovedeau că problemele nu sunt decifrabile, aceasta a fost frecvent o metodă care a fost folosită. Așa că vom trece peste asta astăzi și vom demonstra câteva exemple de probleme indecidabile folosind această metodă. În regulă. Deci de ce nu începem. Deci, în primul rând, cel mai important, ar trebui să vă amintiți cum dovedim că problemele sunt indecidabile în primul rând. Și asta arătând o altă problemă indecidabilă despre care știm deja că este indecidabilă și se poate reduce la problema de interes. Deci, de obicei, s- ar putea să reduceți ATM-ul, care este o problemă cu care am început și ne-am dovedit a fi indecidabilă prin metoda diagonalizării. Sau ar putea fi o altă problemă pe care ulterior am arătat-o ​​a fi indecidabilă, iar tu iei acea problemă și o reduci la problema pe care încerci să o arăți indecidabilă. BINE? Hopa. Lasă-mă să repar asta. BINE. Așa că acesta este lucrul de reținut. Pentru a dovedi că o limbă este indecidabilă, arătați că ATM-ul sau un alt limbaj cunoscut indecidabil se poate reduce la problema B pe care o aveți la îndemână și pe care încercați să o arătați indecidabilă. În regulă. Așa că acum vom-- în primul rând, voi începe prin a-mi aminti cea de-a zecea problemă a lui Hilbert, despre care am discutat pe scurt cu câteva prelegeri în urmă, după cum vă amintiți. Deci, aceasta este o problemă în care ți s-a dat, să zicem, un polinom peste mai multe variabile, cum ar fi 3x pătrat y minus 15z plus 2xz este egal cu 5. Și vrei să rezolvi problema. Vrei să găsești o soluție care să rezolve acea ecuație, dar ai nevoie ca soluția să implice numai numere întregi. Deci, acestea sunt așa-numitele probleme diofantine, deoarece cerința este ca soluția să fie în numere întregi. Și problema lui Hilbert a fost să ceară un algoritm. Nu limba pe care a folosit-o, dar nu contează. În esență, el a cerut un algoritm pentru a testa dacă un polinom are o soluție în numere întregi, dacă ecuația polinomială are o soluție în numere întregi. Și după cum știm acum, acea problemă a fost pusă în 1900, a fost nevoie de 71 de ani pentru a găsi soluția, dar răspunsul este nu. Nu există... nu există un astfel de algoritm. Am vorbit despre asta când discutam teza Church-Turing. Și metoda care arată că nu există un algoritm este prin reducerea de la ATM la acea problemă. Așadar, se poate folosi exact metoda pe care o folosim astăzi pentru a demonstra că problema este indecidibilă cu privire la polinoame. Singurul lucru este că reducerea, acea reducere unică, ar dura întregul semestru. Și știu că este de fapt corect pentru că atunci când eram student absolvent, era o femeie la departamentul de matematică din Berkeley, unde am studiat, și tot cursul urma să treacă prin demonstrarea celei de-a zecea probleme a lui Hilbert, a soluției la problema lui Hilbert. a zecea problemă, dovada indecidibilității soluției, a indecidibilității testării dacă un polinom are o soluție integrală. Deci, chestia este că implică o teorie a numerelor destul de păroasă pentru a veni cu polinoamele potrivite pentru a simula practic mașina Turing. Așa că asta înseamnă să ne depășim pe noi înșine. Asta vom face astăzi. Dar vom... în loc să ne uităm la acea problemă pentru că nu avem un semestru întreg de cheltuit pe ea, ne vom uita la o problemă cu jucăriile în care nu există teoria numerelor, dar încă are aceeași idee de bază care a fost folosită în soluția celei de- a zecea probleme a lui Hilbert. Deci problema jucăriilor se numește problema de corespondență post . Și va avea o altă utilitate pentru noi. Ei bine, principalul motiv pentru care îl studiem este doar pentru a ilustra metoda. Deci și metoda va fi, așa cum am spus, este această metodă a istoriei calculelor. OK, așa că de ce nu... vom vorbi mai întâi despre această problemă de corespondență, deoarece este foarte ușor de înțeles, apoi vom petrece puțin timp prezentând această metodă. În regulă. Deci problema de corespondență post este următoarea. Vi se dau o grămadă de perechi de șiruri. Deci aici este o pereche, t1 și b1. Și le scriu ca pe piese de domino. Le numesc domino pentru că scriu unul dintre șiruri deasupra celuilalt șir. De fapt, folosesc t și b pentru sus și jos aici. Deci, acesta este t1 este șirul de sus, b1 este șirul de jos din primul domino. Și apoi, în al doilea domino, avem alte două șiruri, un vârf și unul de jos și așa mai departe. Așa că le avem aici, această colecție de piese de domino, ca un fel de piese de domino legale. Și care este scopul, să găsești o secvență a acelor piese de domino. Deci vrei să alegi dintre aceste piese de domino de aici. Aveți voie să repetați jocul de domino. Deci doriți să alegeți o secvență a acelor piese de domino, să le aliniați una lângă alta și astfel încât șirul pe care îl obțineți citind în partea de sus, toate ts-urile împreună, va fi exact același cu șirul pe care îl obțineți. trece prin citirea de-a lungul tuturor fundului. Vă voi da un exemplu. Așa că aici, pentru a scrie ceva mai formal, deci ceea ce eu numesc un meci este o secvență a acestor piese de domino, deci este ti1, ti2. Ei bine, i1 este primul domino, i2 este al doilea domino și așa mai departe. Și apoi, ceea ce vei avea este că toate șirurile de sus concatenate împreună sunt exact la fel cu ceea ce obții prin concatenarea împreună a tuturor șirurilor de jos. Deci, iată un exemplu, și cred că va deveni clar dacă nu l-ați înțeles până acum, dar va fi complet clar din exemplu, sper. Deci iată o grămadă de piese de domino, patru. Și ceea ce vreau să știu este, există o selecție a acestor piese de domino... din nou, puteți repeta piese de domino. Altfel, nu ar fi o problemă interesantă. Așa că le puteți repeta de câte ori doriți. Și vreau să aleg aceste piese de domino și să le aliniez, astfel încât ceea ce obțineți citind în partea de sus să fie același cu ceea ce obțineți citind în partea de jos. Deci, în primul rând, dacă te uiți la asta și încerci să faci o potrivire, vei vedea că există o singură modalitate posibilă de a începe asta. De exemplu, dacă ați începe cu al treilea domino aici, ba peste aa, ar eșua imediat pentru că b și a sunt diferite. Și dacă folosiți cel de-al doilea domino ca punct de plecare, și acesta nu se va potrivi, deoarece aa ar trebui să fie - șirul de sus ar începe cu aa, șirul de jos ar începe cu ab și nu ar putea fi niciodată egale. Deci, uitându-vă la asta, puteți vedea că singura alegere posibilă pe care o aveți este să începeți cu primul domino. Așa că voi începe să construiesc un domino pentru tine doar ca să-l poți vedea. Deci, iată meciul, astfel încât să puteți vedea procesul. Deci meciul începe cu primul domino. Și felul în care o voi scrie este că voi lua piesele de domino și le voi cam înclina, astfel încât să puteți vedea cum se aliniază șirurile de sus și de jos . Dar sunt aceleași piese de domino, tocmai au fost... Am schimbat forma. Deci acesta este primul domino, ab peste aba. Acum, al doilea domino din meciul meu, trebuie să înceapă cu un a ca simbol cel mai din stânga pe șirul de sus. Deci, asta ar exclude-o pe aceasta, de exemplu. Dar ar putea exista mai multe opțiuni și, prin urmare, nu este chiar evident pe care ar trebui să o luați. Ceea ce o să sugerez este să o luăm pe aceasta aici. Deci luăm aa peste aba. Il vezi. aa peste aba. Este doar scris-- O oblig doar ca să pot alinia a peste a, b peste b, a peste a și așa mai departe. Așa că încep să construiesc această concatenare a vârfului fiind egală cu concatenarea de jos. Mă urmăresc până acum, sper? Deci acum, ce urmează? Deci trebuie să am ceva în care șirul de sus va începe cu un ba. De fapt, există o singură alegere pentru asta, așa că va trebui clar că acest domino va fi următorul. Deci va pune un ba aici sus, dar apoi va forța un aa jos, pentru că asta face acest domino. Deci acest ba se potrivește cu asta. Acum avem de-a face cu aa. Deci vom reutiliza acest domino pentru că acesta este singurul care începe cu un aa. Așa că îl vom reutiliza pe acela. Acum avem aa și aba. Acum avem nevoie de ceva care să înceapă cu aba. Văd două variante. Ar putea fi acesta pentru că este în concordanță cu... cel puțin captează ab. Am putea încerca să-l punem pe acesta aici, dar o alegere mai bună ar fi să îl folosim pe acesta pentru că dacă îl folosim pe acesta , terminăm meciul. Și prin urmare, am găsit ceea ce căutăm. Și această colecție de piese de domino de aici are o potrivire. Acum, nu este întotdeauna evident. Este posibil ca unele colecții de piese de domino să nu aibă o potrivire. Și deci problema de calcul este, există o potrivire? Și teorema pe care o vom demonstra astăzi este că această problemă este indecidabilă. Oricât de simplu este, o mică problemă combinatorie simplă de încercare de a pune împreună diferite piese astfel încât să formeze o potrivire, nu există un algoritm pentru rezolvarea acestei probleme. Și cred că acesta este un fel de interesant, deoarece este primul exemplu de problemă pe care o avem în care întrebarea de bază nu pare să aibă nicio legătură cu calculul. Ați putea argumenta că ATM-ul ca fiind indecidibil este poate puțin surprinzător după fapt, deoarece este o problemă legată de mașinile Turing, așa că vă puteți imagina că aparatele Turing vor avea un timp dificil să răspundă. Dar aici este o problemă doar legată de șiruri. Și vom arăta că este indecidabil. Deci, doar pentru a formula acest limbaj, voi numi limbajul PCP, este colecția acestor probleme PCP, instanțe PCP, care sunt doar ele însele, fiecare este o colecție de piese de domino. Deci este limba tuturor colecțiilor acestor piese de domino unde există o potrivire. Deci, toate problemele PCP le puteți rezolva cu o potrivire. Și vom demonstra că este indecidibil, arătând că ATM-ul este reductibil la acel limbaj PCP. Acum, înainte de a face asta, va trebui să-- Am să vă explic care este metoda istoricului de calcul în primul rând-- pe care o vom folosi. Deci, înainte de a face asta, iată primul nostru check-in pentru acea zi. Doar pentru a fi sigur că mă urmărești despre ce este această problemă PCP , o să-ți pun o întrebare de testat, există o potrivire cu aceste trei piese de domino? Așa că vreau să te gândești la asta. Adică, principalul lucru pe care vreau să mă asigur că înțelegi este, în primul rând, ce este un meci . Aceasta nu este o problemă foarte dificilă de spus dacă există sau nu o potrivire. BINE. Cinci secunde. Totul gata? BINE. Închizând-o. BINE. Deci, pentru aceia dintre voi care au spus că există un meci, vreau să prezentați meciul pentru că, de fapt, nu există un astfel de-- nu există nici un meci. Și vreau să spun, ai putea obține... jucându-te cu el, cred că dacă încerci să găsești o potrivire, vei vedea destul de repede că vei ajunge... Cred că ceea ce se întâmplă este să intri într-un fel -- dacă încercați să construiți o potrivire cu această configurație specială, veți rămâne blocat să vă repetați. Și un punct aici pe care poate l-ați ratat este că o potrivire trebuie să fie o secvență finită. Deci, dacă te-ai gândit la... există un fel de potrivire infinită pe care o poți construi cu acest set de domino, dar asta nu este permis. Permitem doar potriviri finite. Și asta înseamnă că s-ar putea să-ți schimbi răspunsul ca rezultat, dar prea târziu. Deci, și o modalitate de a vedea că nu puteți avea o potrivire în această problemă este că va trebui să începeți -- niciunul dintre aceste două nu este posibile puncte de plecare, așa că acesta va fi în mod clar singura șansă ca vei avea ca meci, primul domino aici. Dar apoi, odată ce l-ați pus pe acesta jos, cel de jos, șirul de jos, bs-ul de jos pe care îl veți obține, șirul de jos va fi mai lung decât șirul de sus. Și apoi celelalte două vor avea aceeași lungime. Deci nu veți avea niciodată ca partea superioară să aibă aceeași lungime cu cea inferioară. Fundul va fi întotdeauna mai lung, indiferent câte piese de domino mai așezați. Deci nu există nicio șansă să existe un meci aici. BINE. Așa că acum vom merge până la introducerea acestei metode de istorie a calculelor. Și mai întâi, permiteți-mi să definesc ceva pentru o mașină Turing pe care o voi numi o configurație. Configurația este doar un instantaneu al mașinii Turing în mijlocul calculului său. Deci, dacă rulați mașina Turing și doar o opriți la un moment dat, va fi într-o anumită stare, capul va fi într-o anumită poziție, iar banda va avea un anumit conținut. Și cu aceste informații, puteți continua apoi calculul mașinii Turing. Acesta este un set complet de informații de care aveți nevoie despre mașina Turing, care vă spune totul despre calculul său în acel moment. Starea, poziția capului și conținutul benzii. Și astfel, numim acele informații împreună, stare, poziția capului, conținutul benzii, numim asta o configurație. Noțiune destul de de bază. Adică, dacă programul dvs. - dacă aveți ceva - dacă aveți stările tuturor variabilelor și unde este execuția curentă a programului la un moment dat, aceeași idee. BINE. Deci, în ceea ce privește o imagine aici, iată mașina Turing. Imaginați-vă că este în starea q3. Poziția capului este în poziția a șasea pe bandă, deci p ar fi 6 pentru că se află în poziția a șasea, iar conținutul benzii va fi acest grup de urmat de acest grup de bs. Așa că l-aș scrie așa. Starea este în q3, poziția capului numărul 6, acesta este conținutul benzii. Acum, ceea ce vom face adesea pentru comoditate în utilizarea acestei noțiuni în dovezi este că vom dori să reprezentăm o configurație ca un șir într-un mod special care va fi -- asta va fi -- acest concept va apărea din nou și din nou în timpul cursului. Și așa va fi la îndemână să existe un mod special de a nota configurațiile pentru a face dovezi despre ele. Și așa că modul în care le vom scrie este... Cred că este doar poate... Pot să-l pun aici, așa. Vom nota simbolurile casetei. Dar ceea ce vom face este să lipim în mijlocul acelor simboluri starea mașinii imediat la stânga poziției pe care mașina o citește în prezent. Deci vă puteți imagina capul aici, care vine. Imaginați-vă că statul este oarecum acolo unde este capul. Indică simbolul imediat din dreapta lui. Deci acesta este doar un alt mod de a scrie o configurație. Iată conținutul casetei, pe care îl scriu în mod oficial aici. Împărțim conținutul benzii în două părți, pe care le numesc t1 și t2. Aceasta este partea t1, partea t2. Și pun starea între t1 și t2 în care am în vedere că poziția capului mașinii este chiar la începutul lui t2. Dar poate că această imagine spune totul și este suficient de clară. Așa că rețineți că atunci când vom scrie configurațiile mașinilor, de obicei le vom nota în acest fel. Bine, deci cred că acesta este un moment bun pentru a-- pentru a lua un moment pentru întrebări. Oh. Văd că sunt deja multe întrebări. Deci, o întrebare este, cum se diferențiază codarea între șir și stare? Dacă vă înțeleg corect, voi presupune că simbolurile care reprezintă stări și simbolurile care apar pe bandă sunt distincte unele de altele. Așa că puteți spune întotdeauna la fel ca de obicei modul în care scriem lucrurile atunci când aveți un simbol de stat sau dacă aveți un simbol pe bandă. Și astfel, într-o configurație, veți avea o grămadă de simboluri de bandă și un singur simbol de stare reprezentați în poziția în care se află capul. Cineva spune-- 6 aici este doar 1, 2, 3, 4, 5, 6. Suntem în cap p-- capul este în poziţia şase. Atât am avut în minte pentru 6 și de aceea apare acel 6 acolo pentru că asta e poziția capului. Bun. În regulă. Deci de ce să nu continuăm. Acum, suntem cu toții pregătiți să începem să definim istoriile de calcul, care în sine nu sunt un concept foarte dificil. Istoricul de calcul pentru o mașină Turing M pe o intrare w este doar secvența de configurații prin care treceți. Când porniți mașina la început cu M pe bandă-- cu w pe bandă, îmi pare rău, iar capul la început în poziția unu și starea în 20 sau oricare ar fi starea de pornire a mașinii. Deci asta va fi configurația de pornire aici. Și acestea sunt secvența de configurare prin care trec mașinile - prin care mașina parcurge pas cu pas. Fiecare pas al mașinii este reprezentat aici până când ajunge la o acceptare. Aceasta este ceea ce înțelegem prin istoric de calcul sau, uneori, vom sublinia asta numind-o istorie de calcul acceptabilă. Reprezintă sensul că mașina și-a acceptat intrarea și acestea sunt secvența de configurații prin care trece mașina. Asta vreau să spun prin istoric de calcul. Știi, sunt sigur că... adică, cred că terminologia se schimbă de-a lungul anilor, dar există o noțiune similară cu aceea pentru orice fel de... dacă rulezi un program și vrei doar să ții evidența cum se schimbă variabilele pe măsură ce vă aflați în această rulare specială a mașinii și le scrieți pe toate, este ca un jurnal al istoricului setărilor stărilor interne ale mașinii și variabilelor și așa mai departe. Așadar, acestea sunt doar toate configurațiile prin care trece mașina în drumul spre a-și accepta intrarea. Dacă mașina nu acceptă intrarea sa, nu există istoric de calcul. BINE? Deci, nu există o istorie de calcul acceptabilă, cel puțin, pentru a sublinia acest punct. Pentru că acest lucru se poate întâmpla în mod evident doar dacă mașina și-a acceptat intrarea. BINE. Deci, așa cum am făcut cu configurațiile, vom dori să putem scrie istoriile de calcul ca șiruri. Și va fi convenabil să aveți și un anumit format pentru a face asta. Și este ceva cam evident. Vom lua doar secvența configurațiilor din istoricul de calcul și le vom scrie ca un șir în care fiecare configurație va fi șirul pentru configurația respectivă. Îți voi arăta un mic exemplu într-o secundă. Dar doar pentru a ne concentra asupra conceptului de aici, vom scrie șirul pentru această configurație, configurația de pornire și apoi configurația următoare și așa mai departe până când ajungeți la configurația de acceptare și separați fiecare dintre acele șiruri cu câteva kilograme. scrisoare semnată. BINE? Deci, aici este un istoric de calcul pentru M pe w unde w este șirul w1, w2, punct, punct, wn. Așadar, aici este... aici este prima configurație. Deci, această parte aici este istoricul de calcul codificat ca șir. Vă ofer aceste informații secundare suplimentare doar pentru a fi mai clar ce se întâmplă acolo. Deci aceasta este prima configurație, aceasta este a doua configurație și așa mai departe. Și încerc să vă ofer un pic mai multe detalii despre cum ar putea arăta, făcând exemplul puțin mai concret. Deci, să presupunem că mașina Turing, când se află în starea de pornire q0, uitându-se la primul simbol al benzii de intrare din această intrare particulară, să zicem w1, trece de la q0 la q7 și scrie un a pe bandă și își mută indreptati-va spre dreapta. Deci, de aceea, a doua configurație reflectă asta. Vezi aici, a trecut de la q0 la q7. Acum capul se află în a doua poziție, așa că de aceea acel simbol de stare este mutat peste unul. Și prima poziție acum a devenit un a deoarece aparatul a schimbat orice era pe acea bandă de intrare acolo în prima poziție într-un a. Și apoi următorul pas, trece de la q7 citind un w2, care este locul în care se află capul acum, uitându-se la w2, și trece la q8, scriind un c și din nou se mișcă la dreapta. BINE? Așa că de aceea le-am desenat așa cum am făcut-o. Și astfel treceți printr-o secvență a acestora, ajungeți la q accept, și aceasta este forma codificată a istoriei de calcul. În regulă? Cred că asta e tot ce am vrut să spun? Da. Așa că te poți simți liber să pui o altă întrebare dacă vrei. Am de gând să relansez asta. Da. Bun. Deci, dacă suntem cu toții împreună în ceea ce privește configurațiile, istoriile de calcul și modul în care le vom scrie sub formă de șiruri, asta am făcut până acum. Fără întrebări, așa că voi merge mai departe. În regulă. Așa că permiteți-mi să definesc un nou automat pe care îl vom folosi în principal pentru a ne oferi un exemplu astăzi. Voi numi asta un automat delimitat liniar. Și tot ce este este o mașină Turing în care mașina Turing va fi restricționată acolo unde poate - banda nu va mai fi infinită. Banda va fi suficient de mare pentru a reține intrarea. Deci mașina nu mai are capacitatea de a se muta în porțiunea de bandă din dreapta intrării, deoarece nu există nicio bandă acolo. Are doar banda așezată aici, care conține intrarea, pe care banda în sine poate varia în dimensiune. Oricât de mare este intrarea, atât de mare este banda. Deci banda se adaptează la lungimea intrării. Dar odată ce ați pornit aparatul cu o anumită intrare, aceasta este la fel de mare ca banda. Nu mai există. Motivul pentru care se numește mărginit liniar este că cantitatea de memorie este o funcție liniară a mărimii intrării, deoarece puteți obține efectiv ceva mai multă memorie prin mărirea alfabetului benzii, dar asta va fi remediat pentru orice mașină dată, deci asta este de unde vine liniarul, dacă este de ajutor. Dar dacă nu înțelegi asta, este un fel de observație secundară. Dar ceea ce este important pentru mine este că înțelegeți ce vreau să spun prin un automat delimitat liniar sau un LBA. Este exact ca o mașină Turing, dar acea porțiune a benzii care avea inițial spații libere pur și simplu nu este acolo. Pe măsură ce aparatul încearcă să-și mute capul de la capătul din dreapta al intrării, pur și simplu rămâne acolo, ca și cum ar fi încercat să-și mute capul de la capătul din stânga al intrării. Nu merge nicăieri. Așa că acum, vom pune aceleași tipuri de întrebări despre LBA pe care le punem pentru alte automate. Deci problema acceptării. Dacă vă ofer o intrare și o anumită LBA și vreau să știu, acceptă LBA acea intrare? Ei bine, și acum întrebarea este, acesta este decidabil sau nu? Deci, la prima vedere, ați putea crede, ei bine, un LBA este ca o mașină Turing, iar problema ATM-ului este indecidabilă, așa că ar putea fi o primă presupunere bună. Și, de asemenea, dacă încercați să le simulați, dacă încercați să vă dați seama cum ați proceda pentru a simula mașina, dacă vi se oferă b și w, dacă de fapt ați încercat să simulați mașina pentru a obține răspunsul, deci rulați b pe w , bine, bineînțeles, dacă îl rulezi pentru o vreme și în cele din urmă se oprește, fie acceptând, fie respingând, atunci știi răspunsul și ai terminat. Dar această mașină ar putea intra într-o buclă. Știi, nimic care să împiedice mașina să circule pe acea cantitate finită de... pe acea cantitate limitată de bandă pe care o are. Și atunci s-ar putea să ai probleme. Dar, de fapt, nu este cazul, deoarece atunci când începi cu o cantitate limitată de bandă, dacă porți mașina mult timp și nu se oprește, merge și merge și merge, inevitabil, va trebui să se repete, intrați în exact aceeași configurație ca înainte, deoarece există doar un număr limitat de configurații pe care le are mașina. Și odată ce repetă o configurație, va repeta acea configurație pentru totdeauna și va fi într-o buclă. Deci această problemă, de fapt, este decidabilă, deoarece ideea este că dacă b on w rulează foarte mult timp și o sumă pe care o poți calcula, atunci știi că trebuie să fie ciclism. Mai mult decât o simplă buclă. Trebuie să se repete. Și așadar, odată ce începe să se repete, va dura pentru totdeauna. Așadar, și aici este calculul real, care este ceva ce sunt sigur că ați putea face singur, dar doar pentru a-l explica. Deci, dacă aveți o intrare de lungime n pe care o furnizați lui b, deci dacă w are lungimea n, LBA poate merge doar pentru acest număr de diferite -- poate avea doar acest număr de configurații diferite. Numărul de stări înmulțit cu numărul de poziții ale capului, care este n, numărul de poziții ale capului de pe bandă, înmulțit cu numărul de conținut diferit de bandă. Dacă banda avea o singură lungime, aceasta este... aceasta este dimensiunea alfabetului benzii. Deci, dacă banda avea două lungimi, banda avea două celule pe ea, numărul de conținut posibil al benzii ar fi pătratul alfabetului. Și dacă banda va avea n simboluri lungi, va fi dimensiunea alfabetului benzii la a n-a putere. Prin urmare, dacă o mașină Turing rulează mai mult timp, trebuie să repete o anumită configurație și nu va rezista niciodată. Deci decidentul va fi, sperăm, clar în acest moment. Vi se da b și w, deci acesta este hotărârea pentru un LBA. Va rula b pe w pentru acest număr de pași. Dacă este acceptat până atunci, atunci accepți, iar dacă nu, dacă este respins sau încă rulează, atunci poți respinge. Și știi, dacă încă funcționează în acest moment, nu va accepta niciodată. În regulă. Aveți întrebări despre asta? OK, hai să mergem mai departe. În regulă. Deci, acum, dar ceea ce este diferit acum, sau ceea ce este probabil interesant acum este că, deși problema acceptării pentru LBA-uri este decidabilă, problema vidului este indecidabilă. Și aici va interveni metoda istoricului de calcul. Deci, aici vom începe să facem ceva nou în ceea ce privește o tehnică de demonstrare. Deci vom reduce ATM-ul la ELBA, problema golului pentru LBA. Deci, având în vedere un LBA, acceptă ceva sau nu? Și aceasta va folosi metoda istoricului de calcul. Deci aceasta va fi o șansă de a ilustra acea metodă pentru prima dată. Deci, configurarea este inițial la fel ca înainte. Vom presupune că avem o mașină Turing care decide această problemă ELBA care este de interes. Și vom folosi asta pentru a construi ATM -ul Turing pentru contradicția noastră. Bine, deci iată-l pe S, care se presupune că decide ATM-ul și ce va face -- și asta va fi partea dificilă. S va folosi M și w pentru a proiecta un LBA. Acel LBA va fi construit cu cunoștințele lui M și w. De fapt, va avea M și w încorporate în el. Deci, de aceea îl numesc LBA B al Mw pentru că depinde de Mw, așa cum voi descrie. Și ceea ce face acel LBA, își ia intrarea, să-i numim x, intrarea în LBA și examinează acea intrare pentru a vedea dacă acea intrare este un istoric de calcul acceptabil pentru M pe w. Aceasta va fi doar căutarea istoricelor de calcul pentru M pe w. Și acesta este singurul lucru pe care îl va accepta vreodată. Dacă îl alimentați cu ceva care nu este un istoric de calcul, acea secvență de configurații pentru M on w care duce la o acceptare, dacă îl alimentați cu altceva, LBA-ul o va respinge. Acceptă doar istoricul de calcul de acceptare pentru M pe w. Și acum, dacă poți construi așa ceva, atunci poți folosi acea mașină în testerul tău de gol pentru a vedea dacă acceptă vreun șir. Pentru că singurul lucru pe care ar putea fi acceptat este un istoric de calcul acceptabil. Nici măcar nu știi dacă există unul pentru că nu știi dacă M acceptă w. Deci, veți construi acest LBA, care caută să accepte istoriile de calcul, apoi veți vedea dacă limbajul său este gol sau nu. Dacă limbajul său nu este gol, singurul lucru pe care l- ar putea accepta este acest istoric de calcul, așa că știți că M acceptă w. În timp ce dacă limbajul este gol, știți că nu există un istoric de calcul pentru M pe w și, prin urmare, M nu acceptă w. Deci asta e toată ideea. Trucul este cum construiești acest LBA? Deci, mai întâi, veți face acest LBA care își testează intrarea pentru a vedea dacă este un istoric de calcul acceptabil pentru M pe w. Și trebuie să construiți acest LBA fără să știți dacă există un istoric de calcul. Nu este ca și cum ai putea lua acel șir și doar să construiești un șir în LBA pentru că nici măcar nu știi dacă acel șir există. Dar ceea ce puteți face este să faceți ca LBA să urmeze regulile lui M. El cunoaște w și știe M, astfel încât să-și ia intrarea și, folosind w și regulile lui M, să vedeți dacă acea intrare este un istoric de calcul pentru M pe w. Și asta va face. Deci iată această mașină pe care o voi construi. Îți voi da în scris și cu puțin mai multe detalii despre procedura ei. Dar doar pentru a o ilustra, așa că iată o intrare propusă pentru B din Mw. Acesta ar fi x-ul aici. Acesta ar fi un x care ar fi acceptat. Dar orice altceva care ar fi furnizat nu ar fi acceptat. Deci aceasta este secvența configurațiilor scrise ca șir. Acesta ar fi x-ul pe care îl ofer lui B de Mw. Și ar trebui să verifice acest lucru pentru a se asigura că este legal. Deci, la intrarea x, modul în care va merge -- modul în care va continua, va verifica mai întâi dacă x începe în modul corect, deoarece acest LBA, cunoaște M și știe w. Deci, primul lucru este că aruncă o privire la prima parte a șirului până la semnul lire sterline. Dacă nu există niciun semn de lire sterline, dacă veți alimenta doar junk-uri, va fi ușor de identificat ca junk. Deci, dacă ai de gând să hrănești ceva-- așa că va-- LBA va prelua totul până la primul semn de lire sterline și va confirma doar că acel lucru este prima configurație, configurația de pornire a lui M pe w, care înseamnă că trebuie să înceapă cu starea de pornire, apoi aici este w. Așa că verifică asta. Apoi se va verifica dacă fiecare dintre acești băieți urmează legal de la precedentul conform regulilor lui M. Se va verifica mai întâi dacă acesta este corect și apoi acesta duce la cel anterior, conform regulilor lui M. , apoi acesta duce la acela, conform regulilor lui M. Toate acestea-- cunoștințele lui M și w sunt încorporate astfel încât să poată face asta. Și apoi urmează pur și simplu, verificând acest calcul. Este ușor să verificați dacă un calcul este corect. Asta e tot ce se întâmplă cu adevărat aici. Va verifica dacă calculul este corect până când ajunge la sfârșit și apoi se va asigura că ultima configurație care a fost dată ca intrare este o configurație de acceptare, că există o stare de acceptare în ea. Și dacă tot ce trece acceptă, în caz contrar, respinge. BINE? Și ideea este că acesta este un LBA. Tu nu... oh, stai. Pur și simplu am sărit înaintea mea. Nu aveți nevoie de informații suplimentare. Deci, cum face de fapt asta? Deci, cum faci asta de fapt pe bandă? Așa că am susținut că LBA nu are nevoie de spațiu suplimentar pentru a face asta... pentru a face această verificare. Va fi doar zigzag înainte și înapoi aici pe intrare, verificând dacă simbolurile corespunzătoare se potrivesc, cu excepția poziției capului, unde este actualizat corect. Și poate fi nevoie să marcheze... va trebui să marcheze pe bandă, este permis să scrie pe bandă, doar pentru a se asigura că ține evidența unde se află. Dar acesta este un lucru foarte simplu, adică, nu încerc să... dacă nu o urmărești, nu încerc să te alarmez, dar încerc doar să te ajut să înțelegi că asta nu este o procedură complicată aici pentru a verifica dacă calculul real care este scris al mașinii Turing este valid. Dar ne putem ocupa de întrebarea aici. Oh bine. Acum avem câteva întrebări. Hopa! Te poți gândi la... în timp ce eu mă gândesc la asta, te poți gândi la check-in-ul de acolo. Deci iată o întrebare bună. Trecând de la fiecare configurație la următoarea configurație, este un pas următor unic? Ei bine, presupun că mașina Turing cu care începem este deterministă, așa că ar trebui să existe o singură cale de urmat. Deci răspunsul la această întrebare este da. Acesta va fi un șir unic aici. Chiar va fi un singur istoric de calcul. Nu că ar conta într-adevăr într-un sens, răspunsul la acea întrebare, atâta timp cât acel istoric de calcul de acceptare corespunde mașinii care acceptă efectiv. O, băiete, suntem peste tot... suntem peste tot aici. OK, ești gata să închei acest sondaj? În regulă. Ei bine, aici suntem. Toți cei care au spus că ar prefera să fie în 6.046, știu cine ești. Veți fi expulzați cu toții. Nu, glumesc. Nu știu cine ești. Deci da. Bun. Așa că suntem aici la pauză și am făcut acest sondaj intenționat în acest moment, ca să putem petrece puțin timp. Dați-mi voie să pornesc ceasul și pot încerca să vă ajut pe voi, cei care ați răspuns C, că sunteți nedumeriți. Pot să încerc să te ajut să înțelegi ce se întâmplă. Ah. Deci, aceasta este o întrebare bună aici. Bine, bine, bine. Mai multe întrebări bune aici. Deci cineva întreabă, de ce nu testăm toate șirurile posibile pentru B? Amintiți-vă, dacă încercăm să testăm golul pentru limbajul lui B, aceasta este problema ELBA. Acum, de ce nu încercăm toate șirurile posibile? Și asta ar funcționa dacă am avea suficient timp, dar există infinit de multe șiruri și nu va fi bine dacă încercăm să fim decidenți. De aceea nu încercăm doar toate corzile. Dar iată această altă întrebare aici. Acesta este un... OK. Deci întrebarea este, cum găsim intrarea x? Deci aceasta este o întrebare importantă pentru că nu găsim intrarea x. Nu există-- intrarea x, cel puțin intrarea acceptată x, ar fi istoricul de calcul acceptat pentru M pe w. Nu vom găsi niciodată un-- nu vom găsi niciodată un x. Construim acest LBA. Nu vom conduce niciodată acel LBA. Proiectăm acel LBA nu în scopul de a-l rula. Construim acel LBA numai în scopul de a folosi testerul de golire a limbajului LBA. Vom construi acel LBA și îl vom introduce în mașina Turing R, care ne va spune dacă limbajul acelui LBA este gol. Noi înșine nu vom rula niciodată acea mașină. Nu vom veni niciodată cu un x. Doar avem... proiectăm un verificator de calcul. Și apoi testerul de goluri pentru care presupunem că există pentru ELBA va spune, da, există un calcul pe care această mașină le acceptă, sau nu, nu există niciun calcul pe care această mașină le acceptă și acesta va fi un calcul pentru M pe w. Și asta ne va spune dacă M acceptă sau nu w. Deci nu vom găsi niciodată un x. Nu vom conduce niciodată acel LBA. Doar ne hrănim, folosind acel LBA ca intrare în R. Metoda istoricului de calcul folosește întotdeauna LBA-uri? Nu, așa cum veți vedea imediat după pauză. Deoarece LBA-urile este doar un loc ușor de început, dar vom folosi metoda istoricului de calcul și istoriile de calcul în continuare în problema corespondenței post . Da. Istoricile de calcul și intrarea x vor fi întotdeauna finite. Deci, acesta a fost un răspuns la o întrebare despre dacă aceste istorii sau intrările vor fi finite sau nu. Deci acele șiruri vor fi întotdeauna finite, iar istoricul de calcul va fi finit. Așa că suntem la sfârșitul celor cinci minute. Lasă-mă să văd dacă mai este o întrebare la care voiam să răspund. Sa trecem peste. OK, acum revenind la indecizia acestei probleme de corespondență post. Așa că ține minte postarea care corespunde... această problemă, ți se dau acele piese de domino. Vrei să știi dacă există o potrivire. Iată o mică versiune mini a diagramei, dacă asta vă ajută să vă amintiți. Și vom demonstra că acest limbaj este indecidibil. Și deci este de nedecidat să testezi dacă ai o potrivire, având în vedere un set de piese de domino, dacă o potrivire este posibilă. Și vom folosi... vom reduce ATM-ul la acest limbaj folosind metoda istoricului de calcul . Deci, cum naiba vom face asta? În primul rând, există un mic detaliu pe care vreau să-l menționez. Nu vă concentrați pe asta, dar voi presupune că meciurile încep întotdeauna cu primul domino de pe listă, primul domino din colecție. Așa că va fi un domino de început. Voi face dovada mea un pic mai simplă pentru a o face în acest fel, iar apoi puteți remedia această presupunere mai târziu. Și dacă avem timp la sfârșit, o voi face sau poate după terminarea prelegerii. Dacă există întrebări, vă pot arăta cum să remediați această presupunere. Dar deocamdată, pentru a simplifica dovada, vom presupune că a existat un domino de început, că meciurile trebuie întotdeauna să înceapă cu acel domino anume. Dacă nu ai urmat acest punct, nu-ți face griji. Poți pur și simplu să-l ignori. Vei vedea unde apare mai târziu. Deci acum vom reduce ATM-ul la PCP. Deci, presupunând că avem o mașină care decide PCP, o vom folosi pentru a face o mașină care decide ATM-ul ca înainte. Deci, iată mașina Turing S, care va decide ATM-ul. Și felul în care o vom face este așa. Ni se dă M și w. Vrem să știm, ca întotdeauna, M acceptă w? Ceea ce vom face este să construim o instanță a problemei PCP. Așa că vom construi o colecție de piese de domino care vor-- și acea colecție va fi construită știind M și w. Deci asta va afecta piesele de domino pe care le vom crea. Deci această colecție de piese de domino se va numi P de Mw. Depinde de M și W. Și găsirea unei potriviri pentru acest set de ws te va forța să simulezi M pe w, deoarece potrivirea va corespunde unui istoric de calcul pentru M pe w. Deci vom folosi-- odată ce facem asta, odată ce construim setul de piese de domino în care o potrivire corespunde unui istoric de calcul, vom folosi R pentru a determina dacă există sau nu o potrivire. Sau, cu alte cuvinte, dacă există sau nu un istoric de calcul, adică dacă M acceptă sau nu w. Deci, dacă există o potrivire, vom accepta pentru că știm că M acceptă w. Și dacă nu există potrivire, vom respinge pentru că știm că M nu acceptă w. BINE. Acesta este planul. Nu ți-am spus încă cum să faci asta. Adică, sunt îngrijorat de numărul semnificativ dintre voi care vă simțiți confuzi de metodă. Adică, băieți, ar trebui să ne trimiteți mesaje text, mie și AT pentru a încerca măcar să înțelegeți cum funcționează asta. Adică, vom merge... vom face din nou metoda. Va fi puțin mai complicat pentru că trebuie să ne ocupăm și de aceste domino și toate chestiile astea, și de aceea v-am prezentat-o prima dată în decorul LBA-urilor, care au fost, într-un fel, metoda iese poate mai simplu. Deci o potrivire va corespunde unui istoric de calcul de acceptare. Uneori, dacă nu folosesc cuvântul accept, sunt doar puțin neglijent. Istoricul de calcul și istoricul de calcul de acceptare, pentru noi în acest moment , sunt la fel. Adică, mai târziu, s- ar putea să vorbim de fapt despre respingerea istoriilor de calcul, dar să nu ne încurcăm. Istoricul de calcul trebuie întotdeauna să se încheie cu mașina care acceptă. BINE. Cineva întreabă, ce înseamnă ca potrivirea să corespundă unui istoric de calcul? Vei vedea. Asta va fi pe următorul meu slide. Oh. Deci aceasta este o întrebare bună. Pasul meu doi încearcă să folosească R pentru a determina dacă M acceptă w? Ei bine, da, dar fac asta testând dacă aceste piese de domino au o potrivire. Pentru că R decide PCP. Pot folosi R doar pentru a testa dacă lucrurile se potrivesc. Cineva întreabă, ar trebui pasul doi să fie folosirea R pentru a determina dacă M acceptă w? Ei bine, de fapt, asta face, dar face indirect prin testarea dacă acest PCP-- dacă aceste piese de domino au o potrivire. Pentru că acele piese de domino te vor obliga să simulezi M pe w. OK, cred că mă repet aici, așa că să evităm să intrăm într-o buclă a prelegerii și să vedem cum construim de fapt P de Mw. Deci acum înțelegi ce... trebuie să ai planul în minte. Ni se dă M și w. Încercăm să facem un set de piese de domino în care o potrivire va fi un istoric de calcul pentru M pe w. Deci șirul pe care îl veți obține în acea potrivire, șirul de sus și șirul de jos, care vor fi-- trebuie să se potrivească, vor fi istorii de calcul-- vor fi un calcul istoria lui M pe w. Așa că vreau să-mi dau seama cum să- mi forțez dominoul. BINE. Așa că dominoul meu de pornire , așa cum v-am spus, va fi un domino de început special în colecția mea, care va necesita ca meciul să înceapă cu acel domino. Acesta va fi aici. Va avea aceste două șiruri în el. Și puteți vedea deja, începe să arate ca o istorie de calcul. Piesele de domino vor avea această caracteristică. Deci este perechea de șiruri și am scris-o ca să te ajut să vezi ce se întâmplă. Este un semn de lire sterline în partea de sus și configurația de pornire pentru M pe w în partea de jos. Și ceea ce voi face pentru tine aici este în partea de jos a diapozitivului, voi lua piesele de domino pe care le-am notat până acum și voi încerca să construiesc un meci și vei vedea cum acea potrivire. forțează o simulare a mașinii. Deci, să luăm asta ca o ilustrare. Să presupunem intrarea în M, așa că rulez M pe w acum. Încerc să văd, acceptă M w? w este un șir 223. Deci configurația de pornire pentru M pe w este q0, aceasta este starea de pornire pentru M, iar apoi w care urmează este 223. Asta va apărea pe banda mașinii Turing pentru a începe. Deci aceasta este configurația de pornire pentru M pe w, presupunând că am avut acest șir de intrare special pentru w. Și, având în vedere piesele de domino pe care ți le-am oferit până acum, doar una, așa va începe meciul. Acum, vor veni mai multe piese de domino. Deci, pentru fiecare simbol și stare posibilă de bandă, nu vă încurcați de limbajul de aici, acesta este lucrul important. Dacă sunteți în mașina Turing... și vă voi citi asta în engleză. Dacă mașina Turing, când este în starea q, iar capul citește un a, se deplasează în starea R, scrie un b în acel punct și capul său se mișcă spre dreapta. Mă concentrez pe pașii mașinii Turing care se mișcă spre dreapta chiar acum. Dar pentru fiecare stat posibil și simbol de bandă și uitându-mă la ce se întâmplă, voi avea un domino care va capta aceste informații și va fi acest domino aici. q a deasupra, b r jos. Deci doar o sfoară. q a în partea de sus, b r în partea de jos. Deci, să vedem de ce? Ei bine, asta are un aspect arcanic. De ce este un lucru bun pentru... de ce este un domino util de pus aici? Ei bine, dacă aruncați o privire, să presupunem că mașina mea Turing, când este în starea q0, care este starea de pornire, și capul citește un 2, pe care se va întâmpla să îl citească pentru că șirul w începe cu un 2, dacă intră în starea q7 și scrie un 4 și apoi se mișcă la dreapta, voi avea -- în acest domino, voi avea q02 deasupra și 4q7 în jos, deoarece 4 este ceea ce eu -- chiar aici , acesta este b, iar noua stare în care intru este q7. Deci acesta va fi domino-ul pe care îl voi primi. Și iată-l. Iată acel domino care apare în meci. Deci se va potrivi cu q02, care nu primește-- șirul de sus trebuie să fie egal cu șirul de jos. Deci și aceasta va fi singura opțiune pe care o am pentru a prelungi meciul. Deci, q02 va fi în partea de sus când îl voi pune acolo, dar asta va forța 4Q7 să apară în partea de jos, deoarece acesta va fi șirul de jos corespunzător lui q02 de sus. BINE? Deci, dacă vă uitați aici în jos, acesta este începutul celei de-a doua configurații a mașinii. Asta vreau să se întâmple. Vreau să fiu... acea potrivire ar trebui să arate ca un istoric de calcul. Deci asta va fi... toate mișcările din dreapta posibile vor fi gestionate în acest fel și va fi un proces similar pentru mișcările din stânga, dar să nu... Las asta la imaginația ta. Acum, cum pot continua de acolo? Cum arată restul acestei configurații? Ei bine, asta ar trebui să fie doar o copiere a simbolurilor rămase care erau pe bandă pentru că nu se schimbă. Lucrurile se schimbă doar în jurul capului. Restul acestor simboluri, care este 2 și 3, acestea ar trebui să fie copiate aici. Așa că voi avea două simboluri suplimentare... voi avea simboluri suplimentare în... piese de domino din colecția mea. Deci, pentru fiecare simbol pe bandă, voi avea să fie un domino. Deci, pentru fiecare simbol de bandă a, voi avea aa un domino în colecția mea. Și asta spune că pot avea... așa că va fi un domino 2 2. Așa că pot egala acest 2 de aici, dar asta mă obligă să pun un 2 acolo. Va fi și un domino 3 3, care se va potrivi cu acel 3, dar mă va forța să pun un 3 acolo. Doar așa pot extinde acest meci pe care l-am construit până acum. Nu am de ales. Acestea sunt singurele piese de domino care mi se vor da. Și, făcând așa, te oblig să simulezi practic mașina. Acum, ceea ce vreau să se întâmple în continuare este un semn de lire sterline să apară aici și asta va încheia a doua mea configurație. Așa că va fi și un domino cu semnul lire sterline, pentru că aici este un semn lire sterline. Se va potrivi cu semnul lire sterline de sus. Forțează un semn de lire sterline să coboare pe fund. Și dacă te uiți la felul în care suntem acum, suntem exact ca unde eram la început, când a apărut doar acest prim domino. Dar acum suntem o configurație mai târziu. Deci, dacă ai înțeles asta și recunosc că e... există doar o idee aici. Și odată ce ai înțeles ideea, totul este banal. Totul este foarte simplu. Dar trebuie doar să-ți faci această idee. Încerc să-mi dau seama cum să-ți trec ideea în cap. Odată ce îți dai ideea, poți scrie singur toate aceste lucruri. Deci, urmând această descriere a modului în care funcționează funcția de tranziție a mașinii și copierea simbolurilor de pe bandă la următoarea configurație, voi putea obține configurație după configurare până ajung la un punct în care există o acceptare. Și acum, din perspectiva mașinii, am terminat. Aparatul și-a acceptat intrarea. Acesta este istoria noastră de calcul. Dar este o potrivire? Ei bine, până... acest lucru de jos este istoricul calculelor, dar nu se potrivește pentru că partea de sus nu este egală cu partea de jos. Mai sunt lucruri în plus în partea de jos, pe care partea de sus nu le are. Deci, ceea ce va trebui să fac acum este să adaug niște tipuri de pseudo-pași suplimentari ai mașinii în care voi permite ca partea de sus să ajungă până la partea de jos. Și felul în care mă voi gândi la asta, și asta nu este real pentru o mașină Turing la fel de mult pe cât este reală mașina Turing oricum, dar vă veți imagina că voi adăuga un nou tip de mișcare. la mașină care va permite capului să mănânce simbolurile de pe bandă ca Pac-Man. BINE? Și modul în care voi obține acest efect, în partea de sus, dacă am vreun simbol de bandă lângă un qaccept de ambele părți în partea de sus, ceea ce o să vă fac să scrieți în partea de jos este doar qaccept cu acel tas... cu acel simbol pe bandă dispărut. Și repetând acea mișcare după mișcare, banda reală se va micșora. Simbolurile de pe bandă vor coborî unul câte unul, mișcare cu mișcare, până când nu va mai rămâne nimic decât doar qaceptul de la sine. BINE? Deci am un gen de idee de Pac-Man. Voi mânca simbolurile de pe bandă. Și apoi, în sfârșit, ajung la un punct în care pe bandă apare doar qaacceptul. Nu mai sunt simboluri de consumat. Și apoi voi adăuga un ultim domino aici, care este qaccept pound pound potrivire cu doar pound, care termină convenabil meciul. Și astfel meciul este încheiat. Acesta este de fapt puțin detaliat aici. Ezit chiar să o aduc în discuție pentru că cred că este genul de lucru în care dacă înțelegi totul până în acest moment, ai putea să-l completezi singur. Dar doar pentru a fi complet, trebuie să faceți față situației în care capul mașinii Turing s-ar putea muta în porțiunea goală a benzii, care nu este luată în considerare aici. Și modul în care obținem acest efect este să avem un alt domino aici, care îmi permite să adaug simboluri goale în partea de jos, după cum este necesar. Acesta este doar un detaliu. Sunt mai îngrijorat că înțelegeți conceptul de bază. Deci aici va fi un check-in. Încerc să-mi amintesc... OK. Dar atât de bine. Deci, ce altceva putem concluziona din aceste informații? Deci știm... în acest moment, știm că PCP este indecidabil. Asta tocmai am terminat de dovedit. Ce mai știm, dacă ceva? Sau măcar știm asta? Să vedem. Poza mea acoperă puțin procesul de check-in, dar este încă lizibilă. Deci, vreau să spun, acesta nu este un concept ușor de făcut ideea. Dar odată ce îl vei primi, vei vedea că nu este chiar atât de rău. BINE. Încă 15 secunde. Deci această porțiune... această întrebare nu se bazează atât de mult pe metoda istoricului de calcul. Se bazează doar pe faptul că PCP este indecidabil. BINE. Toată lumea aproape gata? Cinci secunde. În regulă. Așa că văd că există un anumit nivel de confuzie. Deci, motivul pentru care B este corect este că știm că PCP este indecidibil, dar știm și că este de recunoscut pentru că ai putea încerca toate modalitățile posibile de a combina domino și una după alta, cu excepția cazului în care vei găsi vreodată o potrivire. Deci asta s-ar putea să dureze pentru totdeauna. Dar dacă există o potrivire a unui posibil, îl vei găsi în cele din urmă. Deci, PCP este un limbaj recunoscut. Indecidabil. Și, prin urmare, știm că complementul său trebuie să fie de nerecunoscut pentru că asta este ceva ce am arătat înainte. Dacă o limbă și complementul său sunt ambele recunoscute, atunci este decidabilă, dar știm că PCP nu este decidabilă, așa că ambele părți nu pot fi recunoscute. BINE. Așa că permiteți-mi să vă demonstrez o ultimă teoremă care vă va fi utilă pentru temele care implică metoda istoriei calculelor. Deci veți avea o ultimă șansă de a înțelege modul în care vom folosi acest lucru, deși acesta va fi puțin mai asemănător în spirit cu versiunea LBA decât cu versiunea PCP, care are acest tip suplimentar de complicație legată de codificarea calculelor mașinii în piese de domino. Aici, vom opera cu un alt automat, care va fi mai simplu. Dar oricum, OK. Trec înaintea mea. Deci, dacă vă amintiți, pentru gramaticile fără context, am avut problema ECFG, problema vidului. Am arătat că este decizibil. Deci, testarea dacă limbajul unei gramatici fără context este goală este determinabilă. Cu toate acestea, testarea dacă limbajul unei gramatici fără context este totul, dacă este egal cu sigma star, asta se dovedește a fi... asta se dovedește a fi indecidabil. BINE? Deci testarea de goluri pentru gramatici fără context, decidabilă. Testarea stelei Sigma, indecidabilă. BINE. Așa că vom arăta că ATM-ul poate fi redus la vechiul PDA prin metoda istoricului de calcul. Și deci presupunem că avem aceleași tipare. Să presupunem că avem un decident pentru toate PDA și să facem un decident pentru vechiul t-- decider pentru ATM. Iată decizia ATM-ului. Și acum, similar cu ceea ce am făcut pentru cazul LBA, dar cu o întorsătură. Vom realiza un automat pushdown care își va verifica intrarea pentru a vedea dacă este un istoric de calcul acceptabil al lui M pe w. La fel cum a făcut LBA, dacă te gândești la modul în care a funcționat. Amintiți-vă, LBA și- a testat intrarea pentru a vedea dacă este un istoric de calcul acceptat. Acceptat dacă a fost, apoi testăm limbajul LBA pentru a vedea dacă există istorii de calcul. Așa că facem același tip de lucru, cu excepția faptului că PDA-ul își va testa intrarea pentru a vedea dacă este un istoric de calcul care acceptă și, dacă este, va respinge. Va face invers față de ceea ce a făcut LBA. Și asta se va dovedi a fi necesar. Dar, pentru moment, să mergem cu asta, și poate o vom vedea în dovadă, de ce trebuie ca dovada să fie așa. Deci, acest automat pushdown își va accepta intrarea dacă nu este în acceptarea istoricului de calcul pentru M pe w. În caz contrar, va accepta. Deci, vă puteți gândi la acest PDA ca acceptând toate vechiturile. Pur și simplu nu acceptă lucrurile bune, istoria de calcul de acceptare. BINE? Este acceptarea tuturor lucrurilor care nu reușesc să fie o istorie de calcul acceptabilă. BINE? Și apoi, odată ce avem asta, testăm dacă limbajul lui R este totul, dacă limbajul lui BMw este tot ce folosește R. Pentru că, dacă limbajul acelui PDA este totul, atunci știm că nu ar putea exista o istorie de calcul acceptabilă, deoarece acesta este singurul lucru care nu ajunge. admis. Acesta este singurul lucru care este respins. Deci, dacă acceptă totul, nu va exista un istoric de calcul care acceptă. Deci, dacă nu există... dacă aceasta este egală cu stea sigma, atunci nu ar putea exista un istoric de calcul acceptabil, și așa vom accepta. BINE. Deci, cum va funcționa asta? Deci, ceea ce este diferit acum la acest caz de cazul LBA este să nu uitați, LBA a primit istoricul de calcul pe intrare și și-a folosit capacitatea de a scrie pe bandă pentru a verifica dacă fiecare configurație a urmat următoarea. Nu avem capacitatea de a scrie pe bandă într-un automat pushdown. Și, apropo, sper că vă simțiți confortabil cu utilizarea PDA-urilor în loc de gramatici, pentru că ne putem schimba unul cu celălalt. Ar fi trebuit să menționez asta când am făcut-o. Dar PDA-ul își va folosi stack-ul pentru a compara fiecare configurație cu următoarea, OK? Așadar, modul în care se va întâmpla este că va lua în mod nedeterminist una dintre acestea -- așa că primul lucru pe care îl face este, ca și înainte, să verifice pentru a se asigura că începutul intrării este configurația de pornire. Dar odată ce asta e... asta e partea ușoară. Dar odată ce începem cu asta, împingem fiecare configurație - ei bine, în primul rând, alegem nedeterminist care configurație ar putea fi cea care eșuează acolo unde una nu reușește să treacă la următoarea. Pentru că aceștia sunt cei pe care încercăm să-i acceptăm, atunci când există un eșec. Deci acum suntem hotărâți să căutăm pur și simplu locul în care există un eșec. Îl împingem pe stivă, apoi îl scoatem din stivă și îl comparăm cu următoarea configurație. Deci, așa folosim stiva în loc să putem marca pe intrare. Acum există o... așa că o să ilustrez asta aici. Deci, pe măsură ce vom citi chestia asta aici, o voi pune în stivă. Deci chestia asta se mută aici, iar această intrare de aici a fost pusă în stivă. q0, w1, w1, este q0, w1, w2. Vezi asta. Prima configurație se află acum pe stivă. Acum, pe măsură ce îl vom scoate, îl vom potrivi cu a doua configurație. Acum, dacă mă urmărești, îți vei da seama că aici este o dificultate pentru că iese invers. Iese în ordinea inversă în care am pus-o și nu asta trebuia să facem. Deci, ce vom face aici, și iată un mic fel de întorsătură, vom schimba modul în care scriem istoriile de calcul făcându-le-- scriindu-le-- inversând cele cu numere pare . Deci, acesta de aici va fi scris invers. Și asta e perfect în regulă. Putem scrie istoriile de calcul în orice mod dorim să ne satisfacem nevoile. Așa că vom inversa-- le vom inversa pe cele alternative. Și acum, când împingem unul, va ieși în ordinea corectă pentru a compara cu următorul. Și așa funcționează procedura. BINE? Ajungem puțin la timp. Trebuie să poți... să vedem. Așa că lasă-mă să trec la o recapitulare rapidă. Metoda istoricului de calcul este utilă pentru a arăta indecizia problemelor atunci când testați existența unui obiect. Fiecare dintre acele patru cazuri pe care le-am arătat astăzi implicat în testarea dacă există ceva. Deci, există o soluție întreagă a polinomului? Există ceva șir în limbă? Există șir care nu este în limbă? Sau există vreo potrivire? Deci, acesta este un caz tipic când apare această metodă de calcul istoric . Și, ca o scurtă recenzie, acestea sunt lucrurile pe care le-am arătat astăzi. Bine, deci de ce nu... nu avem timp. Și așa o să te las să pleci, dar voi rămâne încă 5 sau 10 minute. Încântat să răspund la orice întrebări dacă le aveți, dar acesta este oficial sfârșitul prelegerii. BINE. Așa că lasă-mă să încerc să ajung la... există o mulțime de întrebări în chat. Nu uitați, scrieți și AT-urilor. Deci, dacă M nu acceptă w, ce se va întâmpla cu istoricul de calcul? Deci, dacă M nu acceptă w, atunci nu există calcul - nu există nicio istorie de calcul acceptabilă. Acesta este singurul tip de istorii de competiție pe care îl luăm în considerare. Deci, dacă M nu acceptă w, nu există un istoric de calcul acceptabil . Nu există istoric de calcul. Deci nu știu ce înseamnă, ce se va întâmpla cu ea. Pur si simplu nu exista. Așa că sper să fie de ajutor. Nu trebuie să putem adăuga stări la sfârșitul casetei? Hm. Nu știu ce înseamnă asta. Adăugați stări la sfârșitul benzii. Nu sub-- va trebui să o repeți, scuze, sau să explici asta mai bine. Ah. Deci, aceasta este o întrebare-- aceasta este o întrebare foarte bună aici. Unde eșuează dovada anterioară când se încearcă reducerea ATM-ului la ECFG? Trebuie să eșueze pentru că ECFG este decidabil. Deci asta e o întrebare foarte bună. Poate ne putem întoarce la ultimul slide aici. Deoarece aveam puțin timp scurt, nu m-am concentrat cu adevărat pe motivul pentru care trebuie să acceptăm șirurile de istorie non-calculare . De ce acceptăm toate șirurile nedorite și respingem doar șirurile care sunt istoriile de calcul? Deci căutăm șiruri care eșuează. Un șir poate eșua deoarece începe greșit. Nu are configurația de pornire. Sau poate nu se termină cu acceptarea configurației. Sau poate că o configurație nu duce corect la următoarea. Oricare dintre aceste cazuri este un eșec și va fi un motiv pentru a accepta. Motivul pentru care putem face asta este pentru că profităm de non-determinismul pushdowns. Nu știm unde s-ar putea produce eșecul, așa că vom ghici în mod nedeterminist unde are loc eșecul. Dacă ar fi să răsturnăm asta și să spunem să le acceptăm doar pe cele bune și să respingem orice altceva, ar trebui să testăm că fiecare configurație a dus la următoarea. Așa că ar trebui să le verificăm pe toate. Deci, dacă ceva eșuează, trebuie doar să eșueze într-un singur loc și apoi putem accepta. Dacă este un istoric bun de calcul , trebuie să... trebuie să fie bun peste tot. Și așadar automatul pushdown, într-adevăr, dacă aveți de gând să ajungeți la esențial, automatul pushdown poate verifica dacă această configurație duce la acea configurație să împingă stiva și apoi să o scoată. Dar acum, până ajungeți aici, doriți să verificați dacă această a doua configurație duce la a treia. Ar trebui să împingeți a doua configurație pe stivă, dar în acest moment, sunteți deja după a doua configurație, așa că nu putem face backup și împinge a doua pe stivă. Deci, automatul pushdown nu poate verifica în sens pozitiv că aveți un istoric de calcul. Nu poate decât să-- și să le accepte. Este doar să verificați în sens negativ că nu aveți un istoric de calcul și să acceptați toate cele care eșuează. Și asta doar pentru că trebuie să eșueze doar într-un singur loc. Sper ca te ajuta. Deci, de aceea nu am putut să răsturnăm asta și să facem ca această dovadă să funcționeze pentru problema golului și trebuie să funcționeze doar pentru problema totul, problema tuturor. În regulă. OK, deci la revedere tuturor și ne vedem marți.