[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Bine, toată lumea. Să începem. Bine ați revenit la cursul de Teoria calculului numărul șase. Deci ne-am uitat la o serie de modele diferite de calcul. Și ultima prelegere a fost de fapt una importantă pentru noi, deoarece am schimbat treptele de la modelele noastre limitate, automate finite, automate pushdown și modelele lor generative asociate , expresii regulate și gramatici fără context la mașinile Turing, care vor fi modelul la care vom merge -- care este modelul cu care ne vom menține pentru restul semestrului, pentru că acesta va fi modelul nostru, așa cum vom argumenta astăzi, pentru un scop general calculator. Deci, într-un fel, tot ceea ce am făcut până acum sau până în acel moment a fost un fel de încălzire. Dar, totuși, a avut ocazia să introducem câteva concepte importante care sunt folosite în practică și, de asemenea, ne vor servi drept exemple bune pentru a merge mai departe. Și, de asemenea, doar pentru a ajunge într-un fel pe aceeași pagină. Deci, ceea ce vom face astăzi este să ne uităm la modelul mașinii Turing mai detaliat. Se pot defini mașinile Turing în tot felul de moduri diferite. Dar se va dovedi că nu va conta, pentru că toate aceste moduri diferite vor fi echivalente unele cu altele. Și așa vom rămâne cu cea mai simplă versiune, cea pe care am definit-o deja, și anume mașina Turing simplă cu bandă. Dar, practic, vom justifica acest lucru analizând unele dintre aceste alte modele și dovedind echivalența. Deci ne vom uita la mașinile Turing cu mai multe benzi, ne vom uita la mașinile Turing nedeterministe și ne vom uita la un alt model care este puțin diferit, dar se bazează în continuare pe mașinile Turing numite enumerator. Și vom arăta că toate acestea, în cele din urmă, vă oferă aceeași clasă de limbi. Și, în acest sens, toate sunt echivalente între ele. Și asta va fi-- va servi ca un fel de motivator, într-un fel recapitulează o parte din istoria subiectului și va conduce la discuția noastră despre ceea ce se numește teza Church Turing. Deci vom ajunge la asta în timp util. Și vom vorbi, de asemenea, despre unele notații pentru mașinile Turing și pentru codificarea obiectelor care urmează să fie introduse în mașinile Turing, dar vom ajunge și la asta în scurt timp. Deci hai să mergem mai departe, atunci. Vom intra în continuare într-o mică trecere în revistă a ceea ce am făcut cu mașinile Turing. Și vreau doar să ne asigurăm că suntem cu toții împreună pentru asta. Este un concept foarte important pentru noi acest termen. Deci modelul mașinii Turing pare că va exista acest control finit. Există o bandă cu un cap care poate citi și scrie pe bandă, se poate mișca în ambele direcții. Banda este infinită într-o parte și așa mai departe, așa cum am menționat data trecută. Ieșirea mașinii Turing va fi fie o oprire, acceptare sau respingere, fie o buclă pe care mașina poate rula pentru totdeauna. Cu trei rezultate posibile pentru orice intrare anume. Aparatul poate accepta acea intrare introducând q accept. Poate opri și respinge introducând q respinge. Și s-ar putea respinge prin buclă, ceea ce înseamnă că pur și simplu nu ajunge niciodată la starea de acceptare sau nu obține niciodată o stare de oprire. Doar că merge pentru totdeauna. Dar încă considerăm că este respingerea intrării, doar respingerea prin buclă. Și așa cum am definit data trecută, un limbaj este Turing recognoscibil sau, așa cum scriem de obicei, T recognoscibil, dacă este limbajul unei mașini Turing, colecția de șiruri acceptate de la acea mașină Turing. Din nou, la fel ca înainte, mașina poate accepta 0 șiruri, un șir, multe șiruri, dar are întotdeauna o singură limbă, colecția tuturor șirurilor acceptate. Acum, dacă aveți un decident, care este o mașină care nu face niciodată bucle, care se oprește întotdeauna la fiecare intrare, atunci spunem că limbajul său este un limbaj determinabil. Deci vom spune că o limbă este Turing decidabilă sau pur și simplu decidabilă dacă este limba unui decident, care este o mașină Turing care se oprește întotdeauna la toate intrările. Deci avem acele două noțiuni distincte, Turing limbi recunoscute și Turning decidable languages. Acum, pe măsură ce vom argumenta această prelegere, mașinile Turing vor fi modelul nostru de computer de uz general . Așa că așa ne vom gândi la computere ca la mașini Turing. Și de ce mașinile Turing? De ce nu am ales altceva? Ei bine, adevărul este că nu contează. Și acesta va fi scopul acestei prelegeri. Toate modelele rezonabile de calcul cu scop general, calculul nerestricționat în sensul memoriei nu limitate, toate vor fi - toate au fost arătate, toate modelele pe care le-am întâlnit vreodată s-au dovedit a fi echivalente între ele. Și astfel ești liber să-l alegi pe oricine îți place. Și, pentru acest curs, vom alege mașinile Turing pentru că sunt foarte simplu de argumentat matematic și, de asemenea, au un anumit element de familiaritate prin faptul că se simt ca-- ei bine, sunt mai familiare decât unele dintre ele. celelalte modele care au fost propuse și care există, cum ar fi sistemele de rescriere, calculul lambda și așa mai departe. Mașinile Turing se simt ca un tip primitiv de computer. Și în acest sens, au o anumită familiaritate. OK, deci să începem să vorbim despre variațiile modelului mașinii Turing. Și vom argumenta că nu are nicio diferență. Și apoi acesta va fi un fel de precursor al unei discuții despre o parte din istoria subiectului la care vom ajunge în a doua jumătate a prelegerii. Deci, o mașină Turing cu mai multe benzi este o mașină Turing, așa cum vă puteți imagina, care are mai mult de una - ei bine, are una sau posibil mai multe benzi. Și astfel, o singură mașină Turing cu bandă ar fi o versiune specială a unei mașini Turing cu mai multe benzi. Asta e ok. Dar este posibil să aveți mai multe casete, așa cum am arătat în această diagramă. Acum, cum folosim de fapt o mașină Turing cu mai multe benzi? Ei bine, prezinți... și le vom vedea venind pentru comoditate. Uneori este plăcut să lucrezi cu mai multe benzi. Așa că le vom vedea și pe acestea mai târziu în semestru de câteva ori. Dar deocamdată, setăm modelul astfel încât intrarea să fie prezentată pe o bandă de intrare specială . Așadar, acolo apare intrarea și va fi urmată de spații libere, așa cum am avut înainte. Și acum avem aceste posibile alte benzi, posibil alte benzi, pe care le numim benzi de lucru în care aparatul poate scrie alte lucruri după cum dorește. Și casetele respective vor fi inițial goale. Deci doar toate spațiile libere de pe ele. Toate casetele vor fi citite și scrise. Deci puteți scrie pe banda de intrare. Evident că puteți citi pe banda de intrare și puteți citi și scrie și pe celelalte casete. Deci, ceea ce vrem să stabilim mai întâi că, având aceste benzi suplimentare, nu veți obține putere suplimentară pentru mașină, în sensul că nu veți avea - nu veți avea limbi suplimentare pe care le puteți recunoaște în virtute de a avea aceste benzi suplimentare. Adică, vă puteți imagina că dacă aveți mai multe casete, vă va permite să faceți mai multe lucruri. De exemplu, dacă aveți un automat pushdown cu două stive, puteți face mai multe limbi decât puteți cu o stivă. Deci, este de imaginat că, având mai multe casete, să poți face mai multe limbi decât ai putea cu o singură bandă. Dar, de fapt, nu este cazul. O bandă este la fel de bună ca a avea mai multe benzi. Și o să dovedim asta. Vom schița rapid dovezile acestui fapt. Deci teorema este că o limbă este Turing recunoscută. Și când spunem că Turing este recunoscut, deocamdată ne referim doar la o bandă. Așa am definit-o noi. Deci, o limbă este Turing recunoscută dacă și numai dacă o mașină Turing cu mai multe benzi recunoaște acea limbă. Deci, într-adevăr, un alt mod de a spune că, dacă ai o limbă pe care o poți face cu o singură bandă, o poți face cu o bandă multiplă și invers. Așadar, o direcție a acesteia este imediată, deoarece o singură mașină Turing cu bandă este deja o mașină Turing cu mai multe benzi care se întâmplă să aibă o bandă. Deci direcția înainte a acesteia este... nu e nimic de spus. Este adevărat imediat. Dar dacă vrem să dovedim invers, atunci va trebui să lucrăm. Iar munca va arăta cum se transformă o mașină Turing cu mai multe benzi într -o singură mașină Turing cu bandă. Deci, dacă avem ceva care este recunoscut de o mașină Turing cu mai multe benzi, este tot Turing recunoscut. Și asta înseamnă că o poți face cu o singură mașină Turing cu bandă. Deci trebuie să arătăm cum să facem conversia. Și vă arăt că gândesc într-un mod convingător dar fără a intra în prea multe detalii. Deci, iată o imagine a unei mașini Turing cu mai multe benzi în timpul introducerii sale. Deci am început deja. Inițial începe cu celelalte benzi, benzile de lucru fiind toate goale. Dar acum a fost procesat pentru un timp, iar capul de pe banda de intrare s-a mutat din poziția sa de pornire la capătul din stânga. Este undeva la mijloc. Sunt chestii scrise pe celelalte casete. Și ceea ce vrem să facem este să arătăm cum să reprezentăm aceleași informații pe o singură mașină Turing cu bandă într-un mod care să permită mașinii Turing cu o singură bandă să efectueze pașii mașinii Turing cu mai multe benzi, dar folosind doar o singură bandă în virtutea a unui fel de structură de date care permite ca simularea să continue. Deci, cum va simula mașina Turing cu o singură bandă , va avea același efect de a avea aceste benzi multiple pe mașina Turing cu mai multe benzi? Așa că iată o imagine a mașinii Turing cu bandă unică. Are doar o bandă. Apropo, ar trebui să menționez că toate benzile sunt infinite în dreapta în mașina Turing cu mai multe benzi, la fel cum am făcut-o pentru mașina Turing cu o singură bandă. Și acum, cu această mașină Turing cu o singură bandă, va reprezenta informațiile care sunt prezente pe aceste benzi multiple, dar folosind doar o singură bandă. Și modul în care aleg să fac asta va fi deosebit de simplu. O să mă împart, așa că aici o spun în cuvinte. Va simula m prin stocarea conținutului benzii multiple pe o singură bandă în blocuri separate. Deci, practic, voi împărți banda cu bandă unică a mașinilor Turing în regiuni separate în care fiecare dintre acele regiuni va avea informațiile care se afla pe una dintre benzile din aparatul cu mai multe benzi. Deci, de exemplu, pe prima bandă are a, a, b, a. Ei bine, asta va apărea aici în primul bloc de pe mașina Turing cu bandă unică. Un fel de văzut-o plutind în jos pentru a sugera că vine de la această mașină Turing cu mai multe benzi. Dar asta chiar a fost dezvoltat de simularea pe care o are mașina Turing cu bandă unică. Evident, mașina Turing cu bandă unică nu are acces direct la aparatul cu mai multe benzi. Dar va fi simulare. Așadar, așa arătăm că datele sunt stocate pe banda cu bandă unică. Deci, în al doilea bloc, va avea conținutul celei de- a doua benzi a mașinii cu mai multe benzi Turing. Și regiunea finală a benzilor unice, blocul final așa-numitul benzii cu o singură bandă va avea-- banda aparatului cu bandă unică-- va avea restul conținutului ultimei benzi din m. Și apoi va fi urmat de aceleași infinitate spații libere pe care fiecare dintre aceste benzi le va avea după porțiunea pe care ar putea-o fi scrisă în timpul calculării lor. Așa va arăta banda mașinii Turing cu bandă unică în timpul calculului său. Va avea informațiile reprezentate în aceste blocuri. Capturând toate informațiile pe care le are mașina Turing cu mai multe benzi într-un mod poate mai puțin convenabil, deoarece mașina Turing cu mai multe benzi , nu am făcut acest lucru în mod explicit. Și, în parte, pentru că nu contează cu adevărat, nu am spus exact cum funcționează aparatul cu bandă multiplă. Ceea ce am în vedere este că aparatul Turing cu benzi multiple poate citi și mișca toate capetele de pe toate capetele într-un singur pas. Deci, într-un singur pas al aparatului cu mai multe benzi, poate obține informațiile care se află sub fiecare dintre capete, să le introducă prin funcția de tranziție și apoi, împreună cu starea aparatului cu mai multe benzi, poate decide cum să schimbe fiecare dintre acele locații și apoi cum să muți fiecare dintre acele capete. Deci funcționează pe toate benzile în paralel. Așadar, cum se desfășoară pașii actuali ai simulării benzii unice-- de către aparatul cu bandă unică , cum merge? Deci, în primul rând, pe lângă stocarea conținutului fiecărei benzi în banda unică a lui S, există câteva informații suplimentare pe care trebuie să le înregistreze. Și anume, M are un cap pentru fiecare dintre casetele sale. Dar S are doar un singur cap. Și fiecare dintre capetele lui M ar putea fi într-o locație diferită. În acest caz, așa cum am arătat , pe prima bandă, capul său se află în locația trei. Pe a doua bandă, este în locul doi. Pe a treia bandă, este pe locație - pe ultima bandă, este în locația unu. Deci unde eram? Am simulat mașina Turing cu mai multe benzi cu mașina Turing cu o singură bandă. Și a trebuit să ținem evidența unde sunt capetele. Și așa vom face asta scriind locațiile de pe acele blocuri. Deci, vom avea un punct special, așa cum am arătat aici, pentru a reprezenta locația capului în primul bloc. Deci capul e pe b. Am să punctez b. Și o să fac același lucru pentru locațiile celorlalți capete. Și cum obțin acest efect? Ei bine, am mai văzut așa ceva înainte, în care doar extindem alfabetul de bandă al lui S pentru a permite aceste simboluri punctate, precum și simbolurile neregulate. De asemenea, l-am extins pentru a include marcatorii delimitatori care separă blocurile unul de celălalt, pe care le scriu ca semn de lire sterline. Așa că putem obține acest efect pur și simplu prin extinderea alfabetului de bandă al lui S. Încă câteva detalii despre S care merită să ne uităm, doar pentru a ne asigura că înțelegem cu toții ce se întâmplă. Deci, pentru fiecare dată când M face un pas, S are de fapt mult de lucru. Pentru că un pas al lui M poate citi și mișca toate acele capete dintr-o singură lovitură. S trebuie să scaneze întreaga bandă pentru a vedea ce se află sub acele capete virtuale de fapt, care sunt locațiile simbolurilor punctate. Trebuie să vadă ce se află sub fiecare dintre aceste capete pentru a vedea cum să-și actualizeze starea la următoarea stare. Și apoi trebuie să scaneze din nou pentru a schimba locația, a schimba conținutul acelor locații ale benzilor și, de asemenea, pentru a muta capul la stânga sau la dreapta, mutând efectiv acum punctul la stânga sau la dreapta. Deci e destul de simplu. Există o complicație care poate apărea, totuși, și anume că ce se întâmplă dacă pe una dintre benzi, să spunem, M începe să scrie mai mult conținut decât aveți spațiu în acel bloc pentru a stoca informațiile respective? Deci, dacă M, are 1, 0, 1, să presupunem că M după câțiva pași își mută capul în porțiunea inițial goală a benzii și scrie un alt simbol acolo. Trebuie să punem acel simbol undeva, pentru că trebuie să înregistrăm toate acele informații. Și blocul este plin. Deci ce facem? Ei bine, în acest caz, S trece la o mică rutină de întrerupere și se mișcă, mută toate simbolurile în locul potrivit pentru a deschide o locație aici unde poate scrie un nou simbol pentru continuarea simulării. Deci, având în vedere acest lucru, S poate menține conținutul curent al fiecăreia dintre benzile lui M. Și permiteți-mi doar să notez asta aici. Este necesară schimbarea pentru a adăuga cameră. Și asta este tot ce se întâmplă în timpul simulării. Și, desigur, dacă S în timp ce simulează M observă că M ajunge într- o stare de acceptare sau de respingere, S ar trebui să facă același lucru. Deci, aceasta este descrierea noastră a modului în care funcționează simularea cu bandă unică a mașinii cu mai multe benzi. Să trecem la mașinile nedeterministe. Acum, dacă vă amintiți pentru finit, și sper că o faceți, pentru automate finite, am avut echivalență între nedeterminist și determinist. Automate finite. Pentru automatele pushdown, nu am avut echivalența. Nu am demonstrat asta, ci doar am afirmat-o ca pe un fapt. Există anumite limbaje pe care le puteți face cu automatele pushdown nedeterministe, care este modelul pe care îl avem de obicei ca standard. Așa că unele lucruri pe care le poți face cu automate nedeterministe pe care nu le poți face cu automatele pushdown deterministe . Chiar ai nevoie de non-determinism. Nu sunt echivalente. Pentru mașinile Turing, vom recupera echivalența. Așa că vom arăta că orice puteți face cu o mașină Turing nedeterministă în ceea ce privește recunoașterea limbajului, puteți face și cu o mașină Turing deterministă. Așa că amintiți-vă, am menționat acest lucru pe scurt ultima dată, mașina Turing nedeterministă arată exact ca o mașină Turing deterministă, cu excepția funcției de tranziție în care avem acest set de putere, care permite rezultate multiple diferite la un anumit pas în loc de doar un singur rezultat pe care l-ați avea într- o mașină deterministă. Așa că reprezentăm asta cu această putere setată aici aplicată posibilităților pe care le-ar avea mașina ca pas următor. Deci acum vom demonstra o teoremă foarte asemănătoare, că A este Turing recunoscut de o mașină Turing obișnuită cu o bandă . Este de la sine înțeles, pentru că așa am definit-o. Turing este recunoscut dacă și numai din partea unei mașini Turing nedeterministe recunoaște limbajul. Din nou, amintiți-vă că folosim non-determinismul așa cum o facem întotdeauna. Și anume că o mașină nedeterministă acceptă dacă există o ramură sau un fir al calculului său ajunge la o acceptare. Alte ramuri ar putea merge pentru totdeauna sau ar putea respinge o parte din drum. Dar acceptarea prevalează întotdeauna dacă vreo ramură acceptă. Așa funcționează non-determinismul pentru noi. Deci, acum, direcția înainte a acesteia este, din nou, la fel ca înainte, imediată, deoarece o mașină Turing deterministă este un tip special de mașină Turing nedeterministă care nu se ramifică niciodată nedeterminist pe niciunul dintre pașii săi. Deci direcția înainte este imediată. Definiția inversă este locul în care va trebui să facem ceva pentru a converti mașina noastră Turing nedeterministă într-o mașină Turing deterministă. Și o vom face după cum urmează. Vom lua o mașină Turing nedeterministă. Iată poza noastră. Și acum ne vom imagina calculul său în termeni de arbore. Și aici este arborele de calcul nedeterminist pentru n pe o intrare w. Deci n pentru nedeterminist. Aici este copacul. Undeva aici jos ar putea ajunge să accepte. Și, așa cum am menționat, asta va defini calculul general de acceptat dacă există un loc aici care să accepte. Și singurul mod în care poate fi calculul neacceptat dacă nu există nicio acceptare care să apară nicăieri. Și cumva, dacă vei transforma această mașină nedeterministă într-o mașină deterministă, mașina deterministă va trebui să obțină același efect. Nu are non-determinism. Deci, cum gestionează asta? Ei bine, se va desfășura într-adevăr simularea așa cum ți-ai imagina făcând-o singur dacă ți s-ar spune că trebuie să simulezi o mașină Turing nedeterministă , adică vei căuta acel copac al posibilităților căutând să vezi. dacă găsiți și acceptați. Dacă o faci, atunci accepți. Dacă nu o faci, ei bine, poate vei pleca pentru totdeauna sau poate vei reuși să percheziționați întregul copac și apoi vei spune, nu, accept, nu, resping. Deci, să vedem din nou cum va arăta structura de date a benzii acelei mașini deterministe . Așadar, modul în care se va desfășura această simulare și ați putea programa aceasta într-o serie de moduri diferite. Și, de fapt, manualul are o simulare oarecum diferită. Dar cred că acesta de aici se pretează puțin mai bine și poate că este puțin mai simplu pentru descriere în această setare. Dar există o mulțime de moduri diferite de a îmbunătăți aceste lucruri. Deci m va simula n un fel puțin similar cu simularea anterioară. Va sparge banda în blocuri și acum va stoca în fiecare bloc un fir diferit la un anumit moment al calculului lui n. Așa că vă imaginați unde m va simula n făcând același paralelism, dar obținând efectul paralelismului nu prin non-determinism, ci prin menținerea unor copii ale fiecărui fir pe banda sa și apoi actualizarea lor în consecință. Deci, cred că ideea nu este prea complicată. Deci haideți să vedem câteva detalii aici. Așadar, aici populăm acele blocuri cu conținutul benzii lui n pe fire diferite. Poate că asta corespunde benzii lui n după al cincilea pas de n pe fiecare dintre acele fire. Aveți aceste trei posibilități, să spunem, scrise ca trei blocuri diferite. Acum, amintiți-vă, în cazul simulării cu mai multe benzi, trebuia să înregistrăm câteva informații suplimentare. În special, a trebuit să înregistrăm locația capetelor folosind acele simboluri punctate. Vom face asta din nou, deoarece fiecare dintre aceste fire ar putea avea capul într-o locație diferită. Dar va trebui să facem mai mult. Deci să facem câte un lucru pe rând. Vom stoca locația capului. Aici sunt toate notate ca simboluri punctate. Dar acum există ceva care merge mai departe. Pentru că într-un caz cu mai multe benzi, a existat o stare globală în care aparatul cu mai multe benzi se afla, desigur, la un moment dat. Doar că cineva are un control finit. Este într-o singură stare. Dar în cazul mașinii nedeterministe pe care o simulăm acum, fiecare fir poate fi într-o stare diferită. Așadar, pe când înainte, am putea urmări starea mașinii cu mai multe benzi în interiorul controlului finit al mașinii cu bandă unică. Acum ar putea exista multe, multe state diferite pe care să le urmăriți. Deci nu veți mai putea stoca asta într-un control finit , deoarece ar putea exista un număr mare de fire active la orice etapă dată. Și unii dintre ei pot fi un singur stat. Alții pot fi în stare diferită. Și cum țineți evidența tuturor acestor lucruri? Așa că va trebui să folosim banda. De fapt, vom scrie în ce stare se află un anumit thread pe acel bloc. Și asta vom face. O să o arăt așa. Așadar, notați starea fiecărui fir din bloc prin notarea simbolurilor care corespund acelor stări. Deci, într-un fel scriem stările chiar deasupra blocului folosind simboluri care corespund acelor stări. Deci, din nou, obținem acest efect prin creșterea alfabetului de bandă al lui M pentru a include simboluri care corespund fiecăreia dintre stările sale. Și vom scrie acele simboluri. Deci, iată simbolul pentru starea q8 care spune că primul fir de calcul al lui n este în starea q8. Este în această a treia poziție pe banda sa. Capul este pe a treia poziție acolo. Și conținutul benzii este a, a, b, a. Așa reprezentăm acel fir al calculului, inclusiv starea. Așa că M va efectua pas cu pas, menținând acele informații pe banda sa. Din nou, la fel ca înainte, ar putea apărea unele situații speciale. Deci, de exemplu, n este nedeterminist. Deci un fir s-ar putea bifurca în două fire. Ce facem atunci? Ei bine, un fel de lucru rezonabil. Dacă există un fir de bifurcare, M apoi copiază acel bloc, face două copii ale blocului pentru a corespunde, sau de câte copii aveți nevoie, pentru a corespunde posibilităților în care se ramifică acel fir. Așa că doriți să le reprezentați pe toate pe diferite blocuri ale casetei lui M. În regulă? Și apoi, dacă M află vreodată că pe unul dintre fire intră în starea de acceptare, poate doar să închidă întregul calcul în acel moment și să spună accept. Deci, poate puțin elaborat, dar cred că conceptual, sper că nu prea rău. Acum, să trecem apoi să vorbim despre un aspect oarecum diferit - ei bine, un fel de model diferit, într-un fel, care are o anumită semnificație istorică și uneori este un mod util de a privi recunoașterea lui Turing. Și, întâmplător, aveți o problemă de teme pe acest model numită enumerator sau enumerator Turing. Deci aici va funcționa oarecum diferit. În primul rând, vom îmbunătăți modelul mașinii Turing . Acum va avea doar o singură bandă. Dar va avea și o imprimantă. Așa că acum adăugăm acest nou dispozitiv în mașina Turing numită imprimantă. Și mașina Turing are bandă ca și până acum, cu excepția faptului că nu furnizăm nicio intrare mașinii. Banda începe întotdeauna complet goală. Este folosit doar pentru citit și scris. Folosit doar pentru muncă. Nu este locul în care prezentați intrarea. Deci, cum vorbiți despre limbajul mașinii? Ei bine, modul în care lucrezi cu această mașină este să iei acest enumerator. Este o mașină Turing deterministă cu o imprimantă, așa cum am menționat. Ai început cu bandă goală. Și rulează și rulează și rulează și periodic poate tipări un șir sub un fel de control al programului, pe care nu am de gând să-l explic pentru tine. Dar vă puteți imagina că ar putea fi necesar să definiți aparatul în așa fel încât, atunci când acesta intră într- o anumită stare de imprimare, să nu punem totul la punct, atunci orice șir se află într-o anumită regiune a benzii, poate de la punctul de pornire în sus în locația capului, care este imprimat pe imprimantă. Și apoi poate tipări alte șiruri în timp util. Și astfel, periodic, vă gândiți la această imprimantă ca tipărind un șir sub controlul enumeratorului mașinii Turing. Și astfel, aceste șiruri de tipărire, aceste șiruri care ar putea tipări w1, w2, apar. Iar mașina ar putea să meargă pentru totdeauna și să imprime un număr infinit de șiruri. Sau s-ar putea să dureze pentru totdeauna și să imprime doar un număr finit de șiruri. Sau s-ar putea opri după un timp prin intrarea într-o stare de oprire. Acceptarea sau respingerea este irelevantă, dar intră într-o stare de oprire. Și apoi șirurile pe care le-a tipărit, numărul finit de șiruri pe care le-a tipărit, aceasta este rezultatul mașinii. Acum, limbajul mașinii este colecția tuturor șirurilor pe care le imprimă vreodată. Deci definim limba într- un mod oarecum diferit aici. Nu sunt șirurile pe care le acceptă. Sunt șirurile pe care le imprimă. Așa că ne gândim la această mașină aproape puțin analogă cu expresia regulată sau cu gramatica, în sensul că este un model generativ. Produce limba mai degrabă decât acceptă șirurile din limbă. Nu este chiar un recunoaștetor. Este un generator. Și limbajul mașinii, așa cum scrie aici, pentru un enumerator de aici, spunem că limbajul său este o colecție de șiruri pe care le tipărește. Acum vom arăta că o limbă este Turing recunoscută în sensul anterior recunoscut de o mașină Turing obișnuită dacă și numai dacă este limba unui enumerator. Și, de fapt, aceasta este o dovadă puțin interesantă. Trebuie să faci ceva de lucru. Este un dacă numai dacă. Acum nicio direcție nu este imediată. Va trebui să lucrezi în ambele direcții. O direcție este puțin mai grea decât cealaltă. Vom începe cu direcția mai ușoară. Să presupunem că avem un enumerator. Sper că ați primit acest concept al acestei mașini Turing, care tipărește periodic șiruri când ați pornit-o pe banda goală. Deci, acum, ceea ce voi construi pentru tine este acel dispozitiv de recunoaștere a mașinii Turing definit din enumerator. Deci, acest dispozitiv de recunoaștere va simula enumeratorul. Deci, practic, acel detector va lansa enumeratorul. Va începe să o simuleze. Acum, dacă vrei, dacă este convenabil, am putea folosi mai multe benzi. Putem folosi o bandă pentru a simula dispozitivul de recunoaștere și aveți la dispoziție și alte benzi pentru comoditate, dacă doriți, deoarece am arătat deja că banda multiplă și banda unică sunt echivalente. Deci, dacă doriți, vă puteți gândi la M ca având mai multe benzi. Nu va fi chiar atât de relevant pentru conversația mea. Dar vei simula E începând cu intrarea goală, așa cum ar trebui să faci. Și apoi veți vedea ori de câte ori E se imprimă în x, veți vedea dacă x este același cu intrarea în dispozitiv de recunoaștere. Înțelegi ideea? Deci avem un dispozitiv de recunoaștere. Are un șir de intrare, poate ca 1, 1, 0, 1. Și vreau să știu. Vreau să accept acel șir dacă este unul dintre șirurile pe care enumeratorul E le imprimă, pentru că asta face recunoașterea. Ar trebui să accepte toate șirurile pe care enumeratorul le imprimă. Deci am primit acest 1, 1, 0, 1. Ce fac? Pornesc acel numărător, îl pun în funcțiune și încep să mă uit la șirurile pe care le imprimă, comparându-le cu șirul meu de intrare, 1, 1, 0, 1. Dacă îl văd vreodată imprimând un 1, 1, 0, 1, grozav. Știu că pot accepta, pentru că știu că este în limba enumeratorului. Dar dacă compar și compar și compar, nu văd niciodată ca enumeratorul să imprime șirul meu de intrare 1, 1, 0, 1. Ei bine, continui să simulez. Dacă E se oprește, atunci pot să mă opresc și să resping dacă nu am văzut niciodată acel șir ieșind ca o ieșire. Dacă E nu se oprește, ei bine, nici eu nu mă opresc. O să plec pentru totdeauna. Dar apoi voi respinge intrarea mea prin loop. Deci aceasta este dovada conversiei în această direcție înapoi, care este direcția mai ușoară. Acum să ne uităm la direcția înainte, care are o anumită încrețitură în ea la care va trebui să ajungem. Deci acum vom construi enumeratorul nostru pentru a simula dispozitivul de recunoaștere. Și modul în care vom face asta este că enumeratorul trebuie să imprime toate șirurile pe care le- ar accepta vreodată recunoașterea. Deci faci ceva evident. Veți lua-- enumeratorul va începe să simuleze recunoașterea M pe toate șirurile posibile. Un fel unul câte unul, făcându-le în paralel, pe rând. Poate că nu am făcut asta atât de explicit. Dar puteți face un tip de timeshare între mai multe posibilități diferite. Un fel de a avea blocuri diferite pentru mașină. Enumeratorul va rula dispozitivul de recunoaștere pe... ei bine, să spunem că o face secvenţial. Îl rulează pe șirul gol. Îl rulează pe șirul 0. Îl rulează pe șirul unul. Îl rulează pe șirul 0, 0. Acestea sunt toate șirurile posibile ale stelei sigma. Tu alergi pe toate. Și ori de câte ori enumeratorul... uh oh. Este gresit. Deci, ori de câte ori M acceptă, imprimă... Nu pot scrie foarte bine. Tipăriți w, wi. Hopa! BINE. Așa că o voi spune doar în cuvinte. Vreau să simulez M pe fiecare wi. Ori de câte ori observați că M acceptă wi, imprimați pur și simplu wi. Pentru că doriți să imprimați toate șirurile pe care M le acceptă. Acum, există o problemă aici. Deci, sper că nu sunteți derutat de această greșeală de tipar. Făcând-o secvenţial, așa cum tocmai am descris, nu prea funcționează. Așa că lasă-mă să susțin asta aici. Făcând-o secvenţial nu prea funcţionează, pentru că M s-ar putea bloca în buclă pe unul dintre wi-uri. Ca, poate, atunci când introduc 0 în M, M merge pentru totdeauna. Deoarece M respinge 0 prin buclă. Dar poate acceptă și acest următor șir din listă, cel șir. Nu voi ajunge niciodată la unul doar introducând corzile în M unul câte unul în felul acesta. Ceea ce trebuie să fac este să rulez toate șirurile din M în paralel. Și modul în care voi indica acest lucru este că vreau să simulez M pe w1 la wi pentru i pași pentru fiecare i posibil. Așa că voi rula M pe tot mai multe șiruri pentru tot mai mulți pași. Și de fiecare dată când observ că M acceptă ceva, îl imprimez. Așa că voi remedia acest lucru în versiunea fișierului pe care o public pe site. Deci, dacă tot nu îl primiți, puteți căuta acolo. Dar doar pentru a înrăutăți lucrurile, am un check-in, care va fi despre acest punct mic aici. Așa că am o întrebare. De unde luăm șirurile wi? Șirurile wi sunt pur și simplu lista tuturor șirurilor din sigma star. Deci, sub controlul programului, putem face M să treacă prin fiecare șir posibil. Ca și cum ai avea un odometru, vei ajunge mai întâi la șirul gol. Apoi treci la șirul 0, apoi la șirul. Puteți scrie un program care va face asta. Și mașina Turing poate scrie cod în mod similar pentru a face asta, pentru a ajunge la fiecare șir posibil unul câte unul. Și atunci asta face enumeratorul. Este obținerea fiecăruia dintre acele șiruri și apoi introducerea lor în M, văzând ce face M. Ceea ce încerc să ajung aici este că nu este bine să le hrănești, rulează M până la finalizare pe fiecare înainte de a trece la următorul. Chiar trebuie să le faci pe toate în paralel pentru a evita problema de a rămâne blocat pe un șir pe care M îl face buclă. În regulă. Deci, acest lucru este relevant pentru temele tale, de fapt. Dacă le convertesc într-un enumerator în acest fel, acel enumerator imprimă întotdeauna șirurile în ordinea șirurilor. Ordinea șirurilor este această ordine aici. Având șirurile mai scurte să apară înaintea șirurilor mai lungi și în interiorul șirurilor de o anumită lungime, doar făcându- le în ordine lexicografică. Așa că sper să urmărești asta. Dar din moment ce acestea nu sunt corecte, acest lucru nu contează pentru noi. Lasă-mă să lansez acel sondaj. Voi vedea cât de aleatoriu este răspunsul aici. Deci o cantitate destul de mare de confuzie. Dacă ești confuz, evident că ești într-o companie bună acolo. Pe cale să închid asta. Mai sunt cinci secunde. OK, termină acum. În regulă. Deci răspunsul corect, după cum l-au primit majoritatea dintre voi, este că ordinea nu va fi respectată aici atunci când E va imprima lucrurile. Este posibil să imprime unele lucruri mai târziu în comandă înainte de lucrurile anterioare din comandă. Ce va controla când E îl va tipări? Dacă M acceptă unele șiruri mai repede în mai puțini pași, atunci E ar putea ajunge să imprime acel șir mai devreme în listă decât un alt șir care ar putea fi un șir mai scurt. Deoarece ordinea în care E va identifica acum că M acceptă acele șiruri depinde de viteza cu care M face de fapt acceptarea. Deci, acest lucru este relevant pentru una dintre temele tale, pentru că ceea ce va trebui să arăți este că, dacă începi cu o limbă decidabilă în loc de o limbă recunoscută, atunci poți crea un enumerator, care imprimă întotdeauna lucrurile în ordine, în ordinea șirurilor. Si invers. Și dacă aveți un enumerator care tipărește acele lucruri în ordinea șirurilor, atunci limbajul este decidabil. Deci trebuie să te gândești la asta. O direcție este o modificare destul de simplă a ceea ce tocmai am arătat. Cealaltă direcție este puțin mai multă muncă. Deci, oricum, de ce nu luăm mica noastră pauză de cafea aici? Deci este o întrebare interesantă. Deci o întrebare este pentru că sigma are un infinit - stea sigma este infinită, dacă înțeleg corect această întrebare , care spune că este un număr infinit de șiruri aici. Cum pornește mașina pentru că trebuie să parcurgă și să le enumere pe toate? Nu, nu este mai întâi să notez toate acele șiruri. Pentru că da, nu poți scrie... nu poți face acest pas infinit de a scrie toate șirurile. Ceea ce am avut în vedere este că vei lua fiecare șir pe rând. Mai întâi vei lua primul șir din lista de stele sigma, vei rula M pe acel șir, iar apoi următorul șir din sigma star, îl vei rula pe acel șir și așa mai departe, șir după șir. Și astfel nu veți avea niciodată infinit de multe șiruri de care să vă ocupați. Doar că vor fi din ce în ce mai multe șiruri pe măsură ce mergi. Și întrebarea la care încercam să ajung este dacă o să le finalizezi pe fiecare înainte de a ajunge la următoarea sau dacă vei încerca să le faci pe toate în paralel, ceea ce trebuie să faci. face pentru a dovedi asta acolo. Nu vor fi infinit de multe wi? Da, deci există o... întrebare similară. Infinit multe wi. Există infinit de multe wi. Dar este doar o buclă infinită în care suntem. Rând pe rând, ai grijă de tot mai mult pe măsură ce mergi. Să vedem aici. Da. Deci o altă întrebare este dacă rulăm toate șirurile în paralel? Da, rulăm toate șirurile în paralel. Dar le rulează în paralel, dar acestea sunt... nu definim o mașină Turing paralelă. Le rulează în paralel folosind partajarea timpului. Se rulează puțin în acest bloc, rulează puțin în acel bloc și un alt bloc și se schimbă și face câțiva pași din fiecare. Și așa capătă efectul paralelismului. Întrebarea este că enumeratorul ar avea în esență o bandă de imprimare și o bandă de lucru? Da, te poți gândi la asta ca având o bandă imprimată. Oricum vrei să-l oficializezi. Nu contează. Adică, sunt puțin capricios când îl atașez la o imagine a unei imprimante adevărate. Dar da, crezi conceptual că poți avea o bandă de imprimare. Oricum îți place să te gândești la asta e bine. Cum putem spune direct asta fără să cunoaștem programul imprimantei? Nu trebuie să intrăm în structura imprimantei. Imprimanta este doar ceva în care spuneți imprimați un șir și iese un șir. Asta este tot ce știm despre imprimantă și asta este tot ce trebuie să știm. Deci nu există niciun program pentru imprimantă. Îmi pare rău dacă nu vă înțeleg întrebarea. Dar întrebarea spune literal, cum putem spune asta fără să știm numele imprimantei? Deci, dacă mașina este decidabilă, de ce trebuie să imprime toate șirurile în ordine? De exemplu, dacă un șir este mai scurt, se poate decide mai târziu? Pai da. Motivul pentru care vrem-- deci întrebarea este, dacă mașina este decidabilă, de ce trebuie să imprime toate șirurile în ordine? Pentru că asta vă cer să faceți în problemă. Dacă citești problema, cred că este numărul cinci pe setul P. Asta vă cer să faceți. De aceea trebuie să o tipăriți în ordine. În caz contrar, nu ar trebui să vă faceți griji cu privire la imprimarea în ordine. Doar pentru că îți cer. Bine, deci cred că nu avem timp. Să ne întoarcem în materialul nostru. A doua jumătate, teza Church-Turing. Așadar, Church, aceasta se întoarce în partea din istoria subiectului din anii 1930. Pe atunci oamenii erau interesați să formuleze noțiunea de ce înțelegem prin algoritm. Nici măcar nu l-au numit algoritm. Unii oameni o numesc procedura. Unii oameni au numit-o procedură eficientă. Unii oameni l-au numit calcul eficient. Dar oamenii aveau în minte -- matematicienii s-au ocupat de secole, mii de ani, cu proceduri pentru a face lucruri. Este un lucru foarte firesc. Și logicienii matematici, în special Church și Turing, Turing, cineva sigur de care ați auzit, Church poate nu. Church a fost consilierul de teză al lui Turing, de fapt. Și amândoi ieșeau din domeniul logicii matematice al matematicii și încercau să folosească logica matematică pentru a oficializa această noțiune intuitivă a ceea ce avem de secole despre ce este o procedură, ce este un algoritm. Și în acele vremuri, au venit cu diferite moduri de a-l oficializa. Deci aici am avut această noțiune de algoritm, care este un fel de concept intuitiv. Turing a propus mașina Turing ca o modalitate de a surprinde asta într-un mod formal, într- un mod precis din punct de vedere matematic. Alți oameni au venit cu alte moduri de a face asta. Și pe atunci, nu era evident că toate aceste formulări diferite ar ajunge să- ți ofere concepte echivalente, noțiuni echivalente. Și, de fapt, au dovedit în detaliu destul de elaborat că diferitele metode cu care au venit oamenii , au existat calculul lambda, au existat sisteme de rescriere, au fost mai multe metode care au fost propuse pentru formalizarea acestei noțiuni și toate s-au dovedit a fi echivalent unul cu altul. Astazi pare evident, chiar dacă am făcut un efort să demonstrez asta doar pentru a vă da o impresie despre cum stau lucrurile. Dacă aveți programe, dacă aveți Pascal și Java, să zicem, și gândindu-vă la ce puteți face matematic în acelea-- nu mă refer la capacitatea lor de a interfața cu Windows și așa mai departe, ci doar la capacitățile matematice. Capacitatea de a efectua calcule sau funcții matematice cu un program Pascal sau un program Java. Ar fi absurd să credem că există un program pe care îl poți scrie în Java pe care nu îl poți scrie în Pascal sau Python. Și motivul este că știm că puteți compila Python în Java și puteți compila Java înapoi în Python. Asta vă spune că cele două sisteme, două limbaje de programare sunt echivalente ca putere. Acest lucru nu a fost evident de la început pentru acești oameni. Așa că au observat că toate eforturile diferite care au venit la formalizarea algoritmului, toate erau echivalente unele cu altele. A fost un fel de moment de descoperire când și-au dat seama că toate modalitățile cu care au venit și, odată ce au primit ideea, și-au dat seama că toate modalitățile rezonabile de a face asta vor fi întotdeauna echivalente. Și asta a sugerat că au capturat cu adevărat această noțiune de algoritm prin oricare dintre aceste metode, să zicem o mașină Turing. Și asta au luat. Nu poți demonstra asta, pentru că algoritmii sunt o noțiune intuitivă. Dar faptul că suntem capabili să surprindem asta într-un mod formal, asta este ceea ce numim astăzi teza Church-Turing. Deci oricare dintre aceste metode a capturat noțiunea de algoritm așa cum am descris-o. Și asta a avut un impact mare asupra matematicii. Dă-mi doar o secundă aici. În regulă. Iată un check-in pentru acesta. Deci îl cunoști pe Alan Turing. Deci, iată câteva fapte care pot fi sau nu adevărate despre Alan Turing. Așa că acum poți să le alegi pe toate pe cele care se aplică pe baza cunoștințelor tale. Evident, acest lucru este mai mult pentru distracție sau interes istoric. Dar să lansăm acel sondaj. Vezi cât de multe știi despre domnul Turing. Bifați tot ce se aplică. OK, aproape gata? Te rog, hai să-l încheiem. Cred că este toată lumea. OK, două secunde. Vă rugăm să obțineți credit pentru a face asta. Încheiați sondajul. De fapt, este cam interesant aici. Știți cu toții că a fost un spărgător de coduri. A lucrat, de fapt, a făcut parte dintr-o echipă, cred că a condus echipa, care a încălcat codul german în timpul celui de-al Doilea Război Mondial. Testul Turing este un lucru faimos pentru cum te caracterizezi când ai o mașină inteligentă. Deci a lucrat cu siguranță în AI. A lucrat și în biologie. Are o lucrare mai puțin cunoscută de informaticieni. Dar dacă îl cauți pe Wikipedia, de unde obțin toate informațiile mele, el, de fapt, și știam asta oricum, are o lucrare foarte faimoasă, o lucrare influentă, despre cum, de exemplu, apar pete pe leoparzi și dungi pe tigri. și așa mai departe. Am dat un fel de model matematic pentru ceea ce demonstrează de fapt -- de fapt este destul de -- surprinde lucrurile într-un mod precis, așa cum sa arătat ulterior. A fost închis pentru că era gay. De fapt, din câte știu din istoria lui, nu a fost în închisoare pentru că era gay. A fost condamnat pentru că este gay și i s-a dat posibilitatea de a alege să meargă la închisoare sau să ia substanțe chimice pentru a-l vindeca de a fi gay. Și a ales să nu meargă la închisoare și să ia chimicalele. Și, din păcate, s-a sinucis la doi ani după aceea. Așa că a fost tratat foarte rău de societatea și guvernul britanic, în ciuda faptului că a avut marea muncă pe care a făcut-o. Și ați putea crede că a fost onorat apărând pe o bancnotă britanică. Nici asta nu este adevărat. Dar vestea bună este că în prezent nu se află pe o bancnotă britanică, dar va fi pe o bancnotă britanică începând cu anul viitor. Deci asta împreună cu Winston Churchill și o serie de alți britanici de seamă. El va fi pe bancnota de 50 de lire sterline. OK, așa că hai să continuăm. Deci, așa cum am menționat, Church-Turing a fost important pentru matematică. Și are de-a face cu aceste probleme Hilbert. Nu știu câți dintre voi ați întâlnit asta. David Hilbert a fost considerat pe scară largă a fi cel mai mare matematician al zilelor sale. Și la fiecare patru ani, matematicienii se reunesc pentru un congres internațional, ei bine, Congresul Internațional al Matematicienilor. Asta se întâmplă de peste 100 de ani. Și a fost invitat la întâlnirea din 1900 pentru a ține o discuție despre orice dorea el. Și ceea ce a decis să facă în timpul acelei prezentări este prezenta 23 de probleme care ar fi o provocare pentru matematicieni pentru secolul viitor. Și avem puțin timp scurt, așa că nu am de gând să intru în ele. Unele dintre acestea vom vorbi mai târziu. Dar a 10-a problemă aici este despre algoritmi. A 10-a problemă din lista lui Hilbert numită a 10-a problemă a lui Hilbert este o problemă despre algoritmi. Și spune să dați un algoritm pentru rezolvarea a ceea ce se numesc ecuații diofantine. Nu l-a numit algoritm. A numit-o o procedură finită sau ceva de genul ăsta. Dar ce sunt ecuațiile diofantine? Mă bucur că ai întrebat. Ecuații diofantine. Ce sunt ei? Ei bine, sunt foarte simple. Sunt doar ecuații polinomiale, de exemplu, acest polinom este egal cu o constantă. Dar acolo unde căutați soluțiile, polinoamele sunt variabile. Cauți soluțiile, dar permiți soluțiilor să fie doar numere întregi. Deci iată un exemplu. Așa că vă dau acest polinom. Aici îl pun egal cu 7. Și vreau să rezolv acea ecuație. Deci are aceste trei variabile, x, y și z. Deci trebuie să găsești o soluție acolo. Dar vă voi permite doar să aveți numere întregi conectate. Și de fapt, există o soluție în numere întregi. 1, 2 și minus 2. Dacă îl conectați, veți vedea că funcționează. În regulă. Acum, problema generală pe care Hilbert o aborda este să presupunem că vă dau un polinom. Să presupunem că este setat la 0. Deci căutăm rădăcinile polinomului. Dar doar o ecuație polinomială. Îl poți pune oricând în această formă. Și vreau să știu dacă are o soluție în numere întregi? Și ceea ce caut este o procedură care să-mi spună da sau nu. Vreau să știu. Dați un algoritm pentru a răspunde la acea întrebare pentru un polinom dat. Sau folosind limba acestui curs, definind aceasta în termeni de limbă, decideți această limbă. Dați o mașină Turing care va decide da sau nu pentru orice polinom dat. Da, există o soluție în numere întregi. Nu, nu există o soluție în numere întregi. Asta a întrebat Hilbert în a 10-a problemă. Dați un algoritm. Acum, după cum știm acum, a fost nevoie de șapte ani pentru a obține răspunsul că nu există un astfel de algoritm. Este o problemă indecidabilă. Și vom vorbi despre asta puțin mai târziu în termen. Dar D nu este un limbaj determinabil. Acum, nu exista nicio speranță de a veni cu acel răspuns în 1900 sau chiar în 1910, pentru că nu aveam o idee oficială despre ce este un algoritm. A trebuit să aștepte până când teza Church-Turing ne-a spus că algoritmii sunt într-adevăr mașini Turing, că există un mod formal de a spune ce este un algoritm. Și odată ce ai avut această noțiune, atunci ai putea dovedi că nu există o mașină Turing. Dar înainte de asta, aveai doar această noțiune vagă, noțiune intuitivă a ceea ce este un algoritm. Și deci nu exista nicio speranță de a răspunde vreodată la asta, pentru că, de fapt, răspunsul este că nu există un astfel de algoritm. Acum, vă voi oferi asta ca un mic exercițiu. Avem puțin timp scurt. Dar această limbă D este de fapt o limbă de recunoscut. Așa că ți-aș sugera să te gândești la asta offline. Dar, practic, puteți încerca să introduceți valori diferite pentru aceste variabile. Și dacă descoperi vreodată că evaluează la 0, atunci poți accepta. Dar altfel, trebuie doar să continui să mergi și să cauți. Așadar, a arăta recunoașterea este foarte simplă, dar determinabilitatea este falsă. Acum să vorbim puțin despre codificări pentru mașinile Turing. Deci vom lucra -- codificări și mașini Turing. Deci, acum vom lucra cu mașinile Turing în viitor. Intrarea către acele mașini Turing ar putea fi polinoame, ar putea fi șiruri. S-ar putea să fie și alte lucruri. Am putea dori să introducem automate în mașinile Turing. Deci, mașina Turing poate răspunde la întrebări despre automate. Ei bine, nu uitați, mașinile Turing iau ca intrare doar șiruri. Așa că trebuie să ne gândim cum vom reprezenta ceva mai complicat, cum ar fi un automat ca șir. Și nu am de gând să intru în detalii despre asta. L- ai putea descrie în detaliu. Dar cred că nu este prea interesant să intru în asta. Vom dezvolta doar o notație care spune că dacă aveți un obiect, ar putea fi un polinom. Ar putea fi un automat. Ar putea fi un grafic. Ar putea fi orice lucru cu care lucrați. O masa. Voi scrie acel O în aceste paranteze pentru a însemna o codificare a acelui obiect într-un șir. Și apoi puteți introduce sfoara în mașina Turing. Așa ne vom gândi să prezentăm mașinile Turing cu obiecte și șiruri mai complicate ca intrare, pentru că le vom reprezenta doar ca șiruri folosind moduri în care sunt sigur că sunteți familiarizați. Adică, așa te descurci cu reprezentarea lucrurilor oricum când îți scrii programele. Dar doar pentru a o face formală și așa o vom scrie în aceste paranteze. Și dacă aveți o listă cu mai multe obiecte pe care doriți să le prezentați împreună unei mașini Turing, le vom scrie împreună între paranteze ca acesta. Acum, pentru a scrie mașinile Turing, în continuare, vom folosi descrieri în limba engleză la nivel înalt. Nu ne vom face griji cu privire la gestionarea... la fel ca lucrurile pe care le-am făcut până acum, nu o să vă cer să faceți asta. Nu o să mai facem asta și nu vă voi cere să o faceți. Gestionarea unde merg lucrurile pe benzi și toate acele lucruri, este un nivel prea scăzut. Pentru că acum că avem teza Church-Turing, suntem foarte interesați să vorbim despre algoritmi. Nu suntem atât de interesați să vorbim despre mașinile Turing, în sine. Suntem interesați de algoritmi și care este puterea de calcul. Așa că acum vom vorbi doar despre mașinile Turing la un nivel superior. Și numai atunci când trebuie să dovedim ceva despre capabilități, ne vom întoarce la mașinile Turing și vom demonstra lucruri despre limitările lor și așa mai departe. Deci, notația noastră pentru rularea mașinilor Turing va fi-- practic vom pune mașina Turing între aceste ghilimele. Și vom ști că, în principiu, am putea scrie mașina Turing într-un mod precis în termeni de stări și funcție de tranziție și așa mai departe, dar nu vom merge niciodată înainte și nu vom face acest exercițiu lung. Înregistrează-te rapid aici. Deci, una dintre caracteristici... Ei bine, lasă-mă să nu dau asta. Deci, dacă x și y sunt șiruri de caractere, vreau să am acum o modalitate de a prezenta două șiruri ca un singur șir ca intrare în mașina mea, pentru că întotdeauna mă gândesc la mașina mea ca primind o singură intrare. Așa că ați sugera o modalitate de a combina două șiruri într-unul singur, care ar fi o codificare bună, este doar să concatenați aceste două șiruri împreună. Asa ar fi modul in care ai face-o? Este o modalitate bună de a o face sau nu este o modalitate atât de bună de a o face? Deci haideți să vedem aici. Pot ajunge la asta în continuare. Și gândește-te la ce ai vrea să se întâmple într-o codificare bună. Gata, setat, vândut. Distribuiți rezultatele. Da. Cred că cei mai mulți dintre voi înțelegeți că aceasta nu este o modalitate bună de a combina două șiruri într-una, pentru că problema este că este cam ambiguă într-un fel. Dacă combinați două șiruri în acest fel, ceea ce este important într-o codificare este că mașina atunci când primește codificarea, le poate decoda înapoi în obiectele originale. Și dacă doar o să lipiți cele două șiruri împreună, nu știți unde se termină un șir și începe următorul șir. Și deci nu va fi o modalitate bună de a combina lucrurile. Ar trebui să găsiți o modalitate puțin mai inteligentă fie de a introduce un alt simbol, fie de a face ceva puțin mai sofisticat, care să vă permită să puteți face atât decodarea, cât și codificarea într-un mod unic. Așa că revenind la notația aceea pentru o mașină Turing. Deci iată mașina pe care am văzut-o deja o dată înainte pentru a la k, b la k, c la k. L- aș scrie acum mai simplu decât să gestionez toate casetele pe care le-am avut prima dată, pe care am făcut ultima prelegere. Aș spune doar că îi dăm o intrare w, verifică dacă w are forma potrivită cu lucrurile în ordinea corectă. Respinge dacă nu este. Numărați numărul de b și c ale lui a din w. Acceptați dacă toate contorizările sunt egale și respingeți dacă nu. Va fi suficient de bun pentru a scrie lucruri la acel nivel superior atunci când veți scrie descrierile algoritmilor. Trebuie doar să te asiguri că orice ai face poți implementa. Nu vrei să faci teste care sunt imposibile sau să faci infinit de multă muncă într-o singură etapă. Asta nu e bine. Dar atâta timp cât este clar că ceea ce faci este să faci doar o cantitate finită de muncă în fiecare etapă și este ceva pe care l- ai putea implementa cu adevărat, poți scrie la un nivel înalt. Am vrut să petrec câteva minute vorbind despre setul de probleme doi, dar avem puțin timp aici. În special, a existat această problemă numărul cinci în care arătați că o limbă este Turing recognoscibilă dacă și numai dacă există un D determinabil. Unde C este Turing recognoscibil, unde D este acum o colecție de perechi. Avem câteva întrebări despre notație, la care sper că am răspuns acum. Deci C este un set de x, astfel încât să existe un șir cu care îl puteți asocia. Astfel încât șirul xy să fie în D. Permiteți-mi să încerc să vă dau o imagine despre asta. Așa că vreau să mă gândesc la D ca la o colecție de perechi de coarde. Și ar putea fi util să ne gândim la un fel de D pe axe aici. Deci, dacă avem o pereche de șiruri xy, pe care încă nu le-am împachetat într-un singur șir, mă gândesc la ele ca la o pereche de două obiecte în acest moment, gândiți-vă la D ca - deci doar partea x este doar mai jos aici pe axa x. D ai putea dori doar conceptual să te gândești la asta ca la o colecție de perechi. Deci este ca un subset al tuturor acestor perechi. Și C este toate x-urile care corespund oricărei perechi de aici. Uneori numim asta proiecție, pentru că sunt toate lucrurile care sunt dedesubt sau umbră. Dacă ai avut o lumină așezată aici, sunt toate lucrurile care sunt cam sub un D. Așa că am scris C aici un pic mai gros, dacă poți vedea asta. Deci acesta este limbajul C. Și aici sunt două direcții. Unul este mult mai ușor decât celălalt. Dacă vă dau un D determinabil și vreau să testez dacă ceva este în C, așa că vă voi da un x, vreau să știu dacă este x în C? Ei bine, acum trebuie să testați dacă există un y pe care îl pot asocia cu x unde perechea este în D? Deci poți începe să cauți acel y. Dacă găsești vreodată unul, știi că x este în C. Există infinit de multe yuri de căutat. Dar nu uita, cauți doar un dispozitiv de recunoaștere pentru C. Deci, din partea respingerii, ai voie să pleci pentru totdeauna. Așa că vă ofer un mod de a vă gândi la direcția ușoară. Direcția grea, trebuie să te gândești cum vei ajunge cu acel D determinabil. Dacă îți dau C, trebuie să găsești un D determinabil. Și acum aduci ceva mai jos. Începeți cu o limbă recunoscută și o limbă determinabilă, care va fi oarecum omologul cu aceasta și, într-un fel, este un limbaj mai simplu. Și modul în care devine mai simplu este că y vă va ajuta să determinați dacă x este în C. Și cred că lucrul cu care vă voi lăsa este, și poate putem vorbi despre asta puțin mai mult marți, eu Voi încerca să las puțin mai mult timp dacă vrei să testezi dacă ceva este în C, x este în C, dar nu vreau să te mai las pentru totdeauna, pentru că vreau să fiu o limbă decidabilă. Și o să mă folosesc de tine ca să te ajut. Ce informații te-ar ajuta să garantezi că obții răspunsul corect pentru x fiind în C? Dar că ar trebui să fii sigur că primești răspunsul corect. Deci tu ar putea fi doar răspunsul. Dar atunci nu știi că asta e... trebuie să fii convins că ai răspunsul corect. și doar spunând ce este, vreau să spun, și ați putea spune că x este în D chiar și atunci când nu este adevărat. x este în C chiar și atunci când nu este adevărat. Deci, ce informații v-ar permite să verificați dacă x este în C? Care ar fi informații utile pentru a verifica dacă x este în C, unde ai evita să fii nevoit să mergi pentru totdeauna? Un pic prea grăbit aici pentru ca asta să fie de ajutor. Oricum, haideți să concluzionam ce am făcut. Doar un scurt rezumat aici. Și nu vreau să te țin peste timp. Așa că voi lăsa asta pe tablă. Voi vedea dacă există vreun... așa că prelegerea s-a terminat și poți să pleci după cum vrei. Voi sta aici câteva minute. Am o altă întâlnire în curând, dar voi încerca să răspund la câteva discuții. În regulă. Oamenii comentează despre acest film despre Turing, The Imitation Game. Daca nu ai vazut asta, ti-l recomand. Și este o idee bună să faceți y să fie egal cu șirul repetat în buclă? Hm. Nu sunt sigur de asta. Vă mulțumesc, tuturor, pentru că ați trimis notele voastre amabile. teza Church-Turing. Întrebarea este este în carte? Da. Este în carte. Cam asemănător cu ceea ce am spus deja, dar da. OK, aceasta este o întrebare bună aici. Teza Church-Turing. Cineva m-a întrebat, se dovedește în carte? Nu e nimic de dovedit. Teza Church-Turing este o echivalență între intuitiv și formal. Nu poți demonstra așa ceva. Poți doar să faci... într- un fel este o ipoteză că singurul lucru pe care îl vei putea calcula este ceva ce poți face cu o mașină Turing. Adică, asta are ceva de-a face cu natura lumii fizice. Și nu cred că asta au avut oamenii în minte. Este că genul de lucruri pe care în mod normal ne gândim că le putem face cu o procedură din punct de vedere matematic sunt exact genul de lucruri pe care le poți face cu o mașină Turing. Deci cineva subliniază, încercând să fie de ajutor aici, poate că acești oameni întreabă despre echivalentele diferitelor modele de calcul diferite care sunt dovedite în carte, nu teza Church-Turing în sine. Ei bine, vreau să spun, lucrurile pe care le- am dovedit în prelegere sunt și ele dovedite în carte. Despre echivalența mașinilor cu o singură bandă, a mașinilor cu mai multe benzi, a mașinilor nedeterministe, toate acestea sunt dovedite în carte. Adică, există o mulțime de modele acolo. Deci am putea petrece mult timp demonstrând echivalențe. Și există cărți care petrec mult timp dovedind echivalențe. Dar cred că ceea ce am dat este probabil suficient. Asta e o intrebare buna. Dacă dați un algoritm, nu trebuie să dați mașina reală înainte, decât dacă vi se cere în mod explicit. Dar da, nu mai trebuie să dai stările și tranzițiile . BINE. Deci e puțin după ora 4:00. Cred că voi trece la următoarea mea întâlnire. Așa că vă mulțumesc că sunteți aici și ne vedem marți.