[SCRÂȘIT][FOȘIT][CLIC]
MICHAEL SIPSER: Deci suntem...
bine ați revenit, toată lumea.
Și vom
continua discuția
despre teoria computabilității,
mașinile Turing și despre cum să
dovedim că lucrurile sunt indecidabile,
ceea ce am făcut.  Așa că am
vorbit despre această
metodă mai avansată
de demonstrare a lucrurilor indecidabile în
ultima prelegere, numită metoda
istoriei calculelor
, care apare
în tot felul de dovezi de
indecidibilitate, de obicei mai
complexe.
Cum ar fi, de exemplu,
demonstrarea celei de-a 10-a probleme a lui Hilbert pe care am
menționat-o,
dacă doriți
să-- dacă doriți să testați
dacă un polinom are
o soluție în numere întregi.
Este o reducere de la
ATM, la fel cum am
făcut-o tot timpul.
Toate aceste dovezi sunt
destul de reductive
față de ceva indecidabil.
Această reducere de la ATM este un
punct de plecare la fel de bun ca oricare.
Și folosește
metoda istoricului de calcul.
Deci ceea ce fac ei
este, având în vedere o mașină Turing
și o intrare,
construiți un polinom
care are mai multe variabile.
Și pentru a
obține o rădăcină întreagă,
o soluție întreagă
a acelui polinom,
una dintre variabile
va trebui să
fie atribuită
unui fel de codificare
a unui istoric de calcul al
mașinii Turing a lui M pe w.
Una dintre aceste variabile va
fi un istoric de calcul --
un număr întreg care reprezintă
istoricul de calcul pentru m pe W.
Iar celelalte
variabile sunt acolo
pentru a vă ajuta să
decodați asta, astfel
încât polinomul să poată
verifica și să facă o soluție.  Devine
o soluție
dacă acesta este de fapt
o istorie legitimă de calcul
a lui m pe W.
Deci, folosește într-adevăr
aceeași metodă pe care am
folosit-o de-a lungul timpului,
dar este destul de dificil
să construim acel polinom
și să facem verificarea în felul în
care  trebuie să faci.
Deci, pentru
problema corespondenței post pe
care am introdus-o
data trecută, efectuarea verificării
este relativ simplă.
Știți că potrivirea este
istoricul de calcul
și, urmând
regulile potrivirii,
este destul de simplu să construiți
acea
instanță a problemei Post Corespondență.
Am vorbit despre
automate mărginite liniar.
Desigur, am definit
configurații și
istoriile de calcul pe parcurs și am
dovedit anumite probleme --
alte probleme sunt
și ele indecidabile folosind aceeași metodă.
Bine, așa că astăzi, vom
schimba vitezele.
Vom--
în ultima noastră prelegere
despre
secțiunea de calculabilitate a cursului, vom
vorbi despre
ceva numit
teorema recursiunii, care, practic, oferă
mașinilor Turing capacitatea
de a se referi la ele însele.
Mașini Turing în
orice program, pentru a face
auto-referință, astfel
încât să puteți
ajunge efectiv la codul
mașinii Turing
sau codul programului
pe care îl scrieți.
Chiar dacă aceasta nu este o
primitivă încorporată a
limbajului de programare sau a
sistemului de operare cu care lucrați,
tot îți oferă acel acces.
Și, de asemenea, vom--
dacă avem timp la sfârșit, voi
vorbi puțin
despre logica matematică, care
este un fel de o aplicație frumoasă
a teoremei recursiei.
Și este un
subiect frumos în sine.
Și este ceva la care pot
face o scurtă prezentare.
OK, deci subiectul de astăzi este
despre auto-referință,
mașini care se reproduc singur
și despre subiectul mai larg
numit teorema recursiunii.
Așa că permiteți-mi să o introduc
cu ceea ce aș numi
paradoxul auto-reproducției.
Și adică, să presupunem că aveți
o fabrică, cum ar fi un efect Tesla
sau o fabrică de producție de mașini.
Vezi, există o poză
a fabricii
și produce mașini.
În regulă?
Deci avem o fabrică
care face mașini.
Și ce putem spune despre
complexitatea relativă a mașinilor
în comparație cu cea din fabrică,
într-un anumit sens informal?
Deci, aș susține
că ați fi
rezonabil să spuneți că
complexitatea fabricii
va trebui să fie mai mare
decât complexitatea mașinilor pe care le
produce.
Pentru că nu numai că
fabrica
trebuie să știe cum
să facă mașinile,
așa că trebuie să aibă
toate instrucțiunile
și orice lucruri
care merg într-o mașină,
trebuie să fie inclusă
cel puțin într-un fel de--
trebuie să fie,  într-un anumit sens,
reprezentat în fabrică.
Dar fabrica trebuie să
aibă și alte lucruri --
roboții și celelalte
articole de fabricație,
unelte și așa mai departe --
pentru fabricarea mașinilor.
Deci, fabrica trebuie să
aibă încorporată toată complexitatea
unei mașini
plus și alte lucruri.
Și din acest motiv, s-ar
putea imagina
că complexitatea fabricii este
mai mult decât complexitatea mașinii.
Dar acum, să presupunem că vrei
să ai o fabrică care
face fabrici--
așa că imaginează-ți aici imaginea--
sau, în general, o mașină
care face copii ale ei înșiși.
Ei bine, asta pare, la prima
vedere, imposibil.
Pentru că, evident, nu numai că
fabrica trebuie să
aibă toate
instrucțiunile despre cum
este o fabrică, dar trebuie
să aibă toate lucrurile suplimentare
de care ar avea nevoie pentru a
face fabricarea.
Și, din acest motiv,
se pare că nu este
posibil ca o mașină
să facă copii după sine.
Vreau să spun, te-ai confrunta cu
aceeași problemă
dacă ți-aș cere să
produci un program
în limba ta preferată,
care să se tipărească singur -
o copie exactă a aceluiași cod.
Puteți scrie oricând
un program care va
tipări un
șir, cum ar fi Hello, world.
Este ușor pentru că
puneți Hello, world
într-un fel de variabilă
sau un fel de tabel
în program și
spuneți tipăriți acel tabel.
Dar dacă doriți ca programul
să imprime o copie a lui însuși,
nu puteți lua întregul program
și îl înfigeți într-un tabel,
deoarece programul
va trebui să
fie mai mare decât tabelul.
Și așa, vei
ajunge cu ceva
imposibil să se întâmple.
Deoarece programul-- o
copie întreagă a programului
nu poate încadra în program.
Doar primiți programul
în sine, în sine, în
sine, pentru totdeauna.
Și astfel, ajungi cu un
program infinit așa.
Deci, dacă
abordați cu naiv problema
cum să faceți un
program care
va tipări o copie a
lui, nu este atât de ușor de făcut.
Dar sperăm că, după
prelegerea de astăzi,
veți vedea că este posibil
și, de fapt, cum să o faceți.
Și nu numai că este un
pic de curiozitate,
dar există de
fapt aplicații
pentru ce ați putea dori
să faceți asta, în principal
în matematică și în
teoria informaticii.
Dar există chiar și un fel de
aplicație în lumea reală,
dacă vreți, într-un fel.
Deci vom ajunge la asta la final.
Așa că pare, așa cum
spun, imposibil să existe
o mașină de auto-reproducere.
Dar știm că
în lume,
există lucruri care fac copii
ale lor însele - lucruri vii.
Deci pare un paradox.
Celulele pot face copii
exact ale lor.
Toate ființele vii pot
face copii ale lor.
Deci, cum reușesc să
ocolească acest paradox?  Ei
bine, de fapt, nu este un
paradox pentru că este posibil
să faci o mașină
care să se auto-reproducă,
care să-și facă copii.
Și asta se
știe de mulți ani.
Probabil, se
întoarce la Von Neumann,
care a scris o lucrare faimoasă despre
mașinile care se reproduc automat.
OK, deci
sunt posibile, de fapt, mașinile cu auto-reproducție.
Așa că permiteți-mi să vă dau
un exemplu despre cum
ați face o mașină
Turing care se reproduce singur
.
Ce vrem să spunem prin asta?
Adică o mașină -- o voi
numi SINE --
care îi ignoră intrarea.
Deci, la orice intrare, o
porniți, mașina se macină
pentru un timp și se oprește cu
o descriere a lui însuși
pe bandă -
cu descrierea
SINElui, propriul său cod,
stând pe bandă.
Așadar, la fel ca să
producem un program care
să-și imprime propriul cod,
asta facem cu adevărat.
Deci, pentru asta, vom avea
nevoie mai întâi de
o mică lemă, care
este o lemă foarte simplă,
dar arată mai rău decât este.
Așa că lasă-mă să
ți-l citesc
și apoi îți voi explica
ce spune.
Pentru că ceea ce spune
este extrem de simplu.
Deci există o
funcție calculabilă, o voi
numi
q, care mapează
șiruri cu șiruri, care
va lua orice șir,
w și va produce din w o
mașină Turing care va tipări w.
BINE?
Asta e tot ce face.
Deci, după cum știți, dacă
vă dau un șir, w,
ați putea produce
o mașină Turing
care ar avea w
reprezentat în stările
și tranzițiile mașinii.
Astfel încât, dacă porniți aparatul
, acesta va scoate w.
Dacă vreau să-
mi dai o mașină Turing care
imprimă șirul 1, 1, 0, 1 pe
bandă, poți face asta...
sper.
Și indiferent care ar
fi acel șir, în loc de 1, 1,
0, 0 sau orice altceva, sunt
20 0 și apoi cinci 1,
ai putea face și asta.
Și, de fapt, există
o procedură simplă
care ia un șir
și îl mapează
pe o mașină Turing care
tipărește acel șir.
Deci, aceasta este o funcție calculabilă,
care practic ia un șir
și îl convertește în ceva
care evaluează acel șir.
Și o numesc q.
Nu știu dacă acest lucru
vă este de ajutor sau nu.
Este ca și cum ar converti
șirul w în w între ghilimele.
Deci, q reprezintă
ghilimele, într-un fel.
Deci, dacă este de ajutor, atunci bine.
Dar oricum, Pw este
o mașină Turing.
Când îl porniți, se
imprimă doar w și se oprește.
Și pot găsi Pw de la w... o
dovadă simplă.
Așa că acum, am să
vă spun, presupunând
că avem acea
funcție calculabilă, q,
vă voi spune cum să
faceți această mașină AUTO.
Și nu este complicat.
Mașina Turing
SELF va avea
două părți pe care le voi numi
A și B. Iată
o schemă pentru mașină.
Așa că aici este SINELE.
Este în două părți A și B.
Și ceea ce vreau să spun prin A și B,
sunt ca două echipe separate.
SELF va
începe să ruleze A,
iar când A va termina, îi va
trece controlul lui B.
Și apoi B va
termina treaba.
Și când va fi gata,
veți avea descrierea
SINE pe bandă.
În regulă?
Deci, ceea ce rămâne este să
vă dau codul pentru A și pentru B.
Deci A va fi
ceva super simplu.
A va fi acea
mașină care va tipări B--
tipărește o descriere
a lui B. Cea pe
care am descris-o aici.
Așa că nu uitați, Pw este
mașina care imprimă w.
Și P sub descrierea
lui B este pur și simplu o
mașină care are
acest șir, PB, stocat
în stările și tranzițiile sale.
Porniți acea mașină
și imprimă B
și apoi este gata.
Deci acesta este un foarte simplu...
A este foarte simplu.
Deci, aici, PB face parte din
A. Și când se termină,
B apare pe bandă.
Deci, acesta este momentul în care
A și-a terminat munca.
Acum îi va
trece controlul lui B.
Deci, evident că nu am terminat
încă, pentru că ceea ce ne dorim
este ca A și B
să fie ambele pe bandă,
nu doar B. Pentru că SELF
este o combinație de A și B
împreună.
Așa că trebuie să vă spun cum
funcționează B pentru a termina treaba.
Deci, ați putea crede,
în primul rând, având în vedere
ce am făcut pentru a
obține B pe bandă,
că vom obține A pe
bandă în același mod,
punând o copie a lui A în interiorul
B. Deci o copie a lui B este înăuntru  A
și o copie a lui A se află în interiorul lui B.
Și la un anumit
nivel conceptual,
se pare că asta
ar putea face treaba.
Dar chiar nu este...
asta nu este o soluție.
Pentru că faptul că
pot pune B în interiorul A
îmi interzice un fel să
pun și A în interiorul
P, pentru că acesta va
fi același tip
de raționament circular
de a pune
o mașină în interiorul ei.  Pur și
simplu nu poți face
asta pentru că așa vei
ajunge cu o
mașină infinit de mare
.
De fapt, dacă
pun B în A--
o copie a lui B în ceea ce privește
descrierea sa în A, A
va fi într-adevăr
mult mai mare decât B.
Pentru că are tot B în
interior, plus alte lucruri-  -
toate stările și tranzițiile
pentru tipărirea acelui B.
Deci nu pot ca A să
fie mult mai mare decât B
și apoi B, de asemenea,
mult mai mare decât A.
Așa că nu este bine.
Va trebui
să facem altceva.
Deci cum va face B acum să-l
apuce pe A?
Și trucul pentru a face
asta, fără a avea
o copie a lui A în B--
care nu funcționează.  Asta
nu va
fi o soluție bună.
În schimb, modul în care
B va obține A, va da

seama ce este A.
O să-și dea
seama ce este A.
Și cum se va da
seama ce este A?
Pentru că, dacă îți amintești, B se poate
uita acum poate să se uite la bandă.
Vede acolo un șir
care se întâmplă
să fie o descriere a lui
însuși, dar nu-i pasă.
Vede niște șir pe bandă.
A este mașina care
tipărește acel șir.
A este q din acest șir.
Deci B pur și simplu va
calcula q din orice
vede pe bandă.
Asta este A. OK?
Deci nu stiu daca stii sa citesti.
E cam mic aici.  Va
calcula A
din B stând pe bandă.
Așadar, iată
instrucțiunile pentru B. Va
calcula q din
conținutul benzii, care
se întâmplă să fie
descrierea lui B.
Dar asta este irelevant
pentru B. B vede doar
un șir pe bandă.
Acesta calculează q din
asta, și acesta este A.
Pentru că A este mașina
care tipărește acel șir.
Apoi va
combina A cu B,
făcând orice
interfață ușoară
care trebuie să se întâmple --
Nu voi intra
în acele detalii --
pentru a converti acele două
piese într-o singură mașină,
care este SINELE mașinii.
Și apoi se va imprima
cu SELF pe bandă, așa cum voi
indica aici.
BINE?
Așa este modul în care o
mașină Turing poate
tipări o copie a
propriei descrieri
și o poate lăsa pe bandă.
Și ceea ce este frumos
în asta nu este nimic
specific despre mașinile Turing.
Aceasta este o
procedură generală care permite
oricărui
limbaj de programare să imprime
o copie a propriului cod.
Puteți
face acest lucru chiar și în engleză,
așa cum voi face
în următorul diapozitiv.
OK, deci iată o întrebare bună.
Există multe
mașini Turing posibile care
pot imprima B. Așa este.  De
unde știu cum să
obțin acel anume?
Ceea ce am în minte,
aceasta este
o întrebare puțin subtilă,
dar este o întrebare bună.
Mă gândesc la
mașina Turing specială
care imprimă B, care
este cea pe care q o produce.
Amintiți-vă, așa că trebuie să ne
referim la această lemă.
Această lemă produce
o anumită mașină
care imprimă B din B.
Și aceasta este cea pe care o
voi folosi pentru A
și aceasta este cea
pe care B o va
putea obține prin rularea
algoritmului q pentru a afla
ce A  este.
Deci trebuie să te asiguri că
ești consecvent atunci.
Acesta este un detaliu,
dar este o întrebare bună.
Și de ce nu creează
și asta un argument circular?  Ei
bine, asta a fost o
altă întrebare pe care o
văd aici pe bandă.
Ei bine, nu
mai există nimic... vezi,
B nu trebuie să aibă
A stocat în el.
Înțelege A.
Deci, într-un anumit sens, mai
întâi vei scrie codul pentru B.
B este doar un program simplu.
Iată-l.
Nu este nimic
circular în asta.
Se spune că B este un
simplu - codul pentru B
este, aruncați o privire pe
bandă, calculați q,
combinați rezultatul cu
orice a fost pe bandă
de înainte și imprimați-l.
Adică, este o bucată de
cod pe care o poți scrie.
Acest lucru va deveni mai
clar, sperăm,
în următorul nostru slide,
unde vorbim despre
implementarea în limba engleză.
Dar doar, nu
vreau să mă grăbesc la asta.
Deci ai putea să-ți dai seama de B
fără să știi măcar ce este A.
B stă singur.
Dar apoi, pentru că B este
doar o bucată de cod
care rulează q pe baza a
ceea ce vede pe bandă.
A, acum trebuie să
știți ce este B pentru
a obține A. Pentru că A are
codul pentru B încorporat
în A ca șir.
Deci mai întâi produceți B, apoi
vă puteți da seama -- apoi
puteți obține A. Nu
este nimic
circular în acest argument.
Nu știu dacă îți este de
ajutor,
dar poate fi necesar să te
gândești la asta.
Sau poate că va fi de ajutor
din următorul diapozitiv.
Deci hai să mergem acolo acum.
Deci, așa cum spun, puteți
implementa acest lucru în orice limbă.
În special,
îl puteți implementa în engleză.
Deci, să schimbăm vitezele.  Să
vorbim despre scrierea
instrucțiunilor în limba engleză.
Și apoi vă voi arăta ce se
întâmplă dacă urmați
acele instrucțiuni.
Deci, să începem simplu.
Ce zici de propoziție,
scrie „Hello World”.
Așa că o persoană ascultătoare care
citește acele instrucțiuni
ar scrie apoi „Hello World”
pe hârtie sau oriunde.
Bine, bine, sper că ai înțeles
ideea.
Deci, acum, ce mi-aș dori...
iată o altă propoziție, o
altă instrucțiune.
Scrie această propoziție.
Și cititorul ascultător ar fi
atunci, OK, să scrie această propoziție.
Acesta este genul de
lucru pe care îl caut.
Iată o propoziție care
îndrumă cititorul
să facă o copie exactă.
Dar asta nu-mi place
, deși
face, într-un fel,
ceea ce caut.
Pentru că cam trișează.
Când are aceasta, aceasta se referă
la întreaga propoziție în sine.
Se folosește
implicit aici un construct
pe care o
mașină Turing nu o are.
Mașina Turing
nu are o modalitate
de a accesa propriul cod.
Și, de fapt,
scopul întregii teoreme pe
care o vom
prezenta este
că nu trebuie să aveți această
auto-referință ca primitivă.
Puteți obține acest lucru eficient
folosind procedura pe
care o descriu, care
vă va oferi același efect.
Deci nu ai nevoie de
el ca primitiv.
Puteți proiecta un
software practic,
care vă va oferi
același efect.
Așa că permiteți-mi să vă arăt cum
să faceți asta în engleză.
Deci, să ne uităm la
ceva mai mult...
ui, trișare,
așa că mașinile Turing
nu au această
primitivă de auto-referință.
Deci, să ne uităm la o
altă propoziție aici.
Scrie următoarele de
două ori, a doua oară
între ghilimele și
apoi „Bună lume”.
Deci, ce obținem dacă
respectăm această instrucțiune?
Ei bine, primești „Hello World”
și apoi „Hello World”
din nou, acum între ghilimele.
BINE?
Sper să nu fie prea rău.
Dar acum, sunt la un
pas de
implementarea
algoritmului de auto-reproducere
în limba engleză.
Scrieți următoarele de două ori,
a doua oară între ghilimele
și apoi între ghilimele,
același text.
Acum, urmând
aceste instrucțiuni,
obțineți, ei bine, „Scrieți
următoarele de două ori,
a doua oară între ghilimele”,
așa că iese aici.
Și a doua oară,
l-ai pus între ghilimele, la fel
cum ai făcut cu
„Hello World”.
Dar asta este exact
aici, ieșirea
este exact ceea ce a fost intrarea.
Și chiar dacă aici există o
parte a propoziției
care se referă la
o altă parte,
deci aici prima parte se
referă la a doua parte,
niciodată nu trebuie să am
propoziția să se refere
la întregul ei.
Nu există nicio parte a
propoziției aici
care să indice
întreaga propoziție.
Și așa, aici
reușește să obțină efectul pe care îl
caut, unde
rezultatul este egal cu codul,
dar evită să aibă
auto-referința.
Un lucru este să te referi
la altceva,
dar să nu te referi
la sine.
Așa că lasă-mă să văd aici.
Așa că aici, voi avea o
verificare în acest sens într-un minut.
Așa că voi încerca să
contrastez ceea ce se întâmplă aici
cu ceea ce se întâmplă în
acel SINE mașină Turing
pe care l-am avut din
slide-ul precedent.
Așa că de ce nu te gândești la asta
și o să-ți ofer
un check-in pentru a vedea...
acesta este un pic cam
provocator de check-in.
Dar haideți să vedem dacă vă puteți da
drumul.
Și practic spune, așa că ceea ce
facem aici
se numește
teorema recursiunii, după cum veți vedea.  De
fapt, vom prezenta
formal teorema recursiunii
în următorul diapozitiv.
Dar aici, în ambele
cazuri,
avem un fel de
parte șablon și o parte de acțiune.
În ambele cazuri, există două
părți ale instrucțiunilor,
șablonul și acțiunea.
BINE?
Așa că o să vă las
pe voi să încercați
să vă imaginați care
dintre acestea este care,
în fiecare dintre aceste două exemple.
Și apoi, am să
vă rog să alegeți.
În mașina Turing, care
este acțiunea și care
este șablonul,
iar în propoziție,
care este acțiunea și
care este șablonul.
Acțiunea este
partea în care se întâmplă
niște lucruri interesante

pe care trebuie să le desfășurați.
Șablonul este practic
doar text sau doar un șir.
Deci, lasă-mă să ridic acel sondaj.
Vezi ce crezi.
Pentru că vă rog
acum să indicați unde
este partea de acțiune în
ambele cazuri.
Care este
fraza superioară și fraza inferioară?
Adică din această propoziție aici.
Deci scrie de două ori următoarele.
Aceasta este fraza superioară.
Iar partea din ghilimele
este fraza inferioară... scuze.
OK, aproape terminat aici?
5 secunde, câțiva dintre voi
nu au răspuns încă.
Raspunde.  Mai
rămâne o secundă.
OK, iată-ne, terminând sondajul.
Deci majoritatea de aici are dreptate.
Aș spune, în
propoziția din engleză de aici,
partea de acțiune
este prima parte.
Acolo ai fost de fapt
direcționat să faci ceva.
A doua jumătate a propoziției,
partea inferioară a propoziției,
este doar un șablon scris.
Acesta este doar un șir aici.
Nu există nicio acțiune cu
adevărat regizată.
Se întâmplă să fie la
fel cu partea de sus,
dar acesta ar fi putut
fi doar Hello World.
Acest lucru ar fi putut fi orice.
Și apoi
partea superioară acționează în acest sens.
Deci partea superioară
este partea de acțiune.
Deci, fraza superioară
este partea relevantă.
Acum, în
mașina Turing, într-un fel,
este invers.
Prima parte este de fapt
doar șablonul.
A doua parte, B, este locul în care
lucrați efectiv
la șablon.
Luați asta, practic
text, care ar putea fi orice.
A ar putea fi orice.
Și te uiți
la acel șablon
și reconstruiești ce a
fost A din acel șir care
apare pe bandă.
Deci B este de fapt cel
care face treaba.
Deci este B și
fraza superioară cu partea c este corectă.
Deci haideți să continuăm atunci.
Oh, vreau să menționez aici
problema 6 de pe Pset.
Deci treaba ta este
să implementezi acest lucru în --
dacă ai un
limbaj de programare care îți place --
ar putea fi Python sau oricare ar fi
Java ta preferat, orice
vrei -- poți
implementa asta.
Dacă nu cunoașteți niciun
limbaj de programare,
atunci creați un fel
de limbaj de pseudo programare
și implementați-l acolo.
Permiteți-mi să subliniez că a
corecta citarea
este puțin dureroasă pentru că
trebuie să scapi de
citate și așa mai departe.
Nu voi fi
agitat în privința asta.
Deci, puteți obține în continuare
credit complet, chiar dacă nu obțineți
partea de citare destul de corectă.
Fă tot ce poți.
Cred că este o
problemă interesantă de încercat să o rezolvi.
Și dacă te lupți cu ea
o vreme, este alunecos.
Este genul de
lucru pe care îl poți
petrece cu ușurință câteva
ore pe această problemă.
Pentru că este puțin
dificil să reușești
să faci un program care să se
tipărească singur,
care este sarcina
problemei pe Pset.
Dar nu te agita
prea mult cu citatul
dacă acesta este singurul lucru
care te agăța.
Încercați să obțineți structura principală
a acesteia, care este destul de simplă,
de fapt.
Și dacă nu puteți face
partea de citare să funcționeze, le
voi cere elevilor să nu
vă penalizeze pentru acea parte.  Să ne
uităm la felul de
versiune mai formală
a ceea ce tocmai am făcut și să
o ducem
la nivelul următor.
Pentru că a putea
tipări o copie a ta
este într-un fel o curiozitate.
Dar teorema recursiunii
spune că nu numai că poți
face o mașină care
imprimă o copie a ei însăși,
dar poți face de fapt
o mașină care
să obțină o copie a ei
și apoi să faci niște calcule
pe acea copie a ei înșiși, pe
propria sa descriere.  , care de fapt se
dovedește a fi un
lucru util de făcut.
Odată ce aveți acces la
propria descriere,
așa cum veți vedea din
câteva exemple,
atunci puteți face, poate, unele
lucruri interesante cu asta.
Deci, practic, ceea ce
este teorema recursiunii
este un fel de compilator.
Vă permite să aveți o
nouă primitivă atunci când
scrieți
mașini Turing, adică să
vă calculați propria descriere.
Și teorema recursiunii
va implementa asta pentru tine.
BINE?
Deci, forma tehnică
a teoremei recursiunii
va părea puțin
contraintuitivă, poate.
Lasă-mă să-l pun acolo.
Dacă te lupți puțin
cu toboganul, nu-l transpira.
Principalul lucru de reținut,
și vom vedea din exemple,
este că vă puteți calcula
propria descriere într-o
mașină Turing.
Și asta va
fi permis ca cod.
Deci, modul în care vom
face acest lucru
este, ceea ce
face teorema recursiunii
pentru tine este că spune că poți
scrie o bucată de cod aici.  Să-i
spunem o bucată de cod
al mașinii Turing--
cod algoritmic--
numit T. Și T va
fi transformat
într-o nouă mașină, R.
Și R va
primi o copie a programului
în sine, care este doar un
descrierea lui R, gratuit.
Dar altfel, va
acționa exact ca T.
Deci R va
acționa exact ca T,
cu excepția faptului că R va fi
furnizat o copie a lui R.
Și asta este ceea ce teorema
vă arată cum să implementați.
Așa că lasă-mă să văd.
Deci, pentru orice mașină, T,
există o mașină R
care, pentru orice w, care va
fi intrarea pentru R. R, pe w,
funcționează la fel ca
R pe intrarea cu w
unde i se dă R. Deci R  va avea
acces
la R fără-- va
obține
R prin calculul lui.
Poate că va fi clar
din dovezi.
M-am luptat mereu cu cum
să explic acest lucru clar.
Deci, acum, dovada
acestui lucru va
fi foarte asemănătoare cu
dovada din două
diapozitive înapoi, cu excepția că va
fi în trei părți.
Aceasta este partea, T, pe care o
vei oferi.
Și T va fi
codul mașinii Turing care
spune: obțineți propria descriere.
Și nu trebuie să vă faceți griji
despre cum se întâmplă asta.
Compilatorul va adăuga
părțile A și B, care va
primi întreaga
descriere a întregului lucru,
care este R, și o va introduce în
T ca și cum T ar avea-o ca intrare.
Deci, lui T i se va permite
acum să obțină propria sa descriere
și să opereze pe -- acum își face
treaba pe intrarea w.
Deci, modul în care va
funcționa, deci este dat T.
A va fi, la fel ca înainte,
descrierea lui B acum cu T.
Deci, când A se termină, va
produce BT așezat pe bandă de
lângă w.
B o să-și dea seama acum
ce a fost A de la BT care stă
pe bandă.
Și apoi, va combina
asta pentru a obține ABT, care este R.
Și după aceea, îi trece
controlul lui T cu w și acum R
așezat pe bandă.
Și acum, T va
avea propria sa descriere.
Dar nu uitați, acum T
a fost modificat pentru a fi R.
Deci nu este că T va
primi T pe bandă.
Pentru ca acest lucru să aibă
sens, aceasta va
fi acum noua mașină R.
Și R apare pe bandă.
Și acum, codul pe
care l-ați furnizat,
T, va începe să
opereze pe asta.
BINE?
Dacă nu ai înțeles asta,
nu sunt atât de îngrijorat.
Principalul lucru este
că puteți utiliza să
vă calculați propria
descriere atunci când
descrieți mașinile Turing.
Asta
iti spune chestia asta.
Cred că va fi...
oh, există un check-in aici.
Da, deci nu știu.
Hai să facem asta mai
repede aici.
Putem folosi teorema recursiunii
pentru a proiecta o mașină T care, în
loc să-și producă
propria descriere,
acceptă doar propria sa
descriere ca intrare?
Deci limbajul
acestei mașini va
fi pur și simplu un
șir, descrierea lui T.
Deci putem face o mașină,
T, care face asta?
Acum mă uit
la acest check-in.
Acest T aici este
confuz cu acel T.
Nu este același T. Asta e rău.  Ar
trebui să o numesc M. Proiectați
o mașină, M, unde L din M
este descrierea lui M.
Și putem folosi
teorema recursiunii pentru a face asta?
Ceea ce v-aș ruga să faceți este să vă
gândiți la asta în acest context.
Puteți utiliza să
vă calculați propria descriere
atunci când scrieți
codul pentru această mașină.
Dacă ai putea face asta,
ai putea crea o mașină
care acceptă doar
șiruri care se întâmplă
să fie propria lor descriere?
Acest lucru ar trebui să fie ușor.
Dar cred că a ajuns să fie
puțin mai complicat
decât mi-am dorit.
Lansați sondajul, faceți cea
mai bună ghicire.
Cred că vedeți cu toții... V-am
cam condus,
vă conduceam pe drumul de
aici.
Da, deci, cred că
aproape toți înțelegi.
Poate ca unii dintre voi sunteti nesiguri.
Dar oricum, haideți să o
încheiem repede,
astfel încât să putem merge mai departe.
Cred că ești destul de... așa că,
5 secunde, o voi termina.
Deci răspunsul corect este
Da, așa cum am făcut aluzie.
Așa că cred că poate acest exemplu
ar fi fost mai bun
după exemplul următor.
Și apoi vom
face o pauză.
Deci, iată o nouă dovadă
că ATM-ul este indecidibil,
dar acum se utilizează
teorema recursiunii.
Și acesta
vă va oferi un exemplu frumos despre cum
folosim
teorema recursiunii în acțiune.
Așa că nu uitați, am petrecut o jumătate de
curs sau mai mult cu o dovadă
prin diagonalizare.
Ca primul nostru exemplu de
ATM cu problemă indecidabilă,
am
arătat ulterior alte lucruri
indecidabile prin reducere.
Dar pentru primul exemplu,
am folosit acea diagonalizare.
Acum am să-
ți dau o nouă dovadă.
Deci, dovadă prin
contradicție, presupunem că
avem o mașină Turing,
H, care decide ATM.
Începe în același mod în care
a mers și proba de diagonalizare.
Dar acum voi
face o nouă mașină numită
R. Deci aceasta va fi
diferită de
dovada anterioară.
R spune, la intrarea w,
primesc propria mea descriere.
Utilizați teorema recursiunii.
Așa
încep întotdeauna aceste lucruri.
Acum, voi folosi H. Acum
că îmi cunosc propria descriere, voi
alimenta--
pot întreba H. Pot alimenta R, w--
w a fost intrarea aici.
Pot introduce R, w în H pentru a
determina dacă R acceptă w.
Asta face H.
Rezolvând ATM, H va spune acestei
mașini dacă R acceptă w.
R este mașina pe care o
scriem, totuși.
Aceasta este mașina
care funcționează în prezent.
Deci R folosește acum H și știe
ce ar trebui să facă.
H va spune, ei bine,
vei accepta w
sau nu vei accepta w.
Asta se presupune că
poate face H.
Dar atunci ce va
face R după aceea?
R va face opusul a ceea ce
spune H că va face.
Deci, dacă H spune, R acceptă w,
atunci R va respinge w.
Dacă H spune că R nu acceptă w-- îl
respinge prin loop sau
oprire, nu contează--
H spune doar că respinge, atunci
doar va accepta.
Deci orice ar spune H, R va
arăta că H este greșit.
Deci asta e o contradicție.
Se spune că H nu poate
decide ATM-ul.
Așa că, dacă dați un pas înapoi și vă gândiți
la ce este asta aici,
aceasta este întreaga
dovadă a diagonalizării
într-o singură linie.
Practic, am făcut această
dovadă într-un mod diferit,
deși există o oarecare
similitudine aici.
Nu vreau să spun că am
reinventat complet lucrurile
și am făcut asta
total diferit.
Dar într-un fel, într-
un fel,
ajunge la esența
diagonalizării
într-un anumit sens.
Dar oricum, îți oferă
o dovadă nouă, foarte scurtă,
că ATM-ul este indecidibil.
Cred că e
un lucru mișto.
Așa că de ce nu luăm
mica noastră pauză de cafea aici
și te poți simți liber să pui
întrebări în timpul pauzei.
O să-mi pornesc cronometrul.
Și ne vom întoarce, continuând
prelegerea în cinci minute.
OK, deci întrebări-- deci
primim câteva întrebări
despre când am spus, nu trebuie să ne facem
griji cu privire la ghilimele
atunci când rezolvăm
problema 6 pe Pset.
Cineva spune, putem spune doar
tipăriți A, B, C, în loc de
citați tipăriți, „A, B, C” și va
tipări A, B, C. Da, puteți...
nu vă faceți griji pentru ghilimele  .
Cred că este un fel de--
vei vedea o provocare
dacă vrei să încerci să
faci ghilimele să funcționeze.
Dar este și un fel de durere.
Așa că da, puteți să
ignorați ghilimele
și le voi cere elevilor să
dea notele complete acolo.
Așa că orice
interpretare rezonabilă va--
atâta timp cât înțelegeți
corect restul conceptului--
va fi bine.  Să vedem
, cineva întreabă,
În teorema recursiunii,
de ce T nu primește
descrierea lui T
în loc de descrierea lui R?
Pentru că mașina
care rulează
este R, în
diapozitivul anterior, acum două diapozitive.
Deci, dacă R ar obține T, nu ar
obține propria sa descriere.  Ar primi

descrierea
unei alte mașini.
Deci trebuie să vă gândiți
la ceea ce
trebuie să se întâmple de fapt aici în
demonstrarea teoremei recursiunii.
Dar trebuie să aibă R, nu T. Să
vedem dacă pot...
de ce face R
opusul a ceea ce spune H?
De ce face R
opusul a ceea ce spune H?  Ei
bine, în primul rând,
eu sunt cel care
ajunge să proiecteze R. Deci
iată arcul de cod.
Presupunem că
avem H. Voi
proiecta R pentru a face orice
vreau pentru a satisface dovada.
Și R aici este proiectat
să facă opusul lui H.
Așa că îl întreb pe R--
îl programez pe R
pentru a afla ce
prezice H că va face
și apoi să facă opusul.
Poate situația
este cam așa.  Să
presupunem că cineva spune,
am o minge de cristal, care
va fi ca rolul
lui H. Și tu spui, oh, într-adevăr?
E cam misto.
Nu te cred, dar
încă sună interesant.
Și persoana spune, da,
pot vedea viitorul.
Știu ce vei
face în cinci minute.
Și, de fapt, văd
că în cinci minute vei
spune, Bună.
Și poți spune, bine,
poți să te gândești, ei
bine, această persoană este nebună.
Nu am de gând să fac asta.
Doar că nu am de gând să spun Bună.
Și apoi geniul de acolo
cu globul de cristal
așteaptă cinci minute și
tu nu spui Bună.
Și apoi ai dovedit că
globul de cristal nu funcționează.
Este foarte asemănător.
Nu am de gând să explic cum
putem face combinarea în SINE.
Vreau doar să explic
la un nivel înalt.
O să fie dezordonat.
Pentru că am spus, aveam de gând
să ne combinăm cumva în SINE.
Permiteți-mi să las asta ca
un nivel conceptual.
OK, cum funcționează această idee
pentru mașinile Turing?
Nu prea
înțeleg întrebarea asta.
Cum funcționează această idee pentru
mașinile Turing sunt decidabile?
Va trebui să
retrimiteți asta pentru că
nu înțeleg întrebarea.
Pot să explic, să folosesc
propria descriere?
Deci, atunci când scrieți cod care
spune, obțineți propria descriere,
după ce se execută acel cod,
mașina Turing
apare pe bandă, ca prin
magie, descrierea
propriului cod.
Să spunem, stând lângă
intrarea în aparat,
deoarece aparatul poate avea
o intrare separată de aceasta.
Așa că mașina
primește în mod magic propriul cod.
Și demonstrația
teoremei recursiunii implementează asta,
deci nu este magie până la urmă.
Dar tot nu
înțeleg întrebarea.
Deci, pentru problema 6, este
suficient să atașezi codul?
Dacă aveți de gând să atașați
cod pentru problema 6, și asta este
suficient de bun.
Sau dacă poți explica,
e și bine, ca de obicei.  Ne facem
griji pentru
file și linii noi?
Nu.
OK, va trebui să
amânăm restul întrebărilor.
Nu uitați că avem
o grămadă de întrebări la
care nu am ajuns.
OK, ultimul aici - de ce
programarea R face
opusul lui H?
Este o contradicție?
Ei bine, H prezice că R
acceptă, dar R nu acceptă,
deci H greșește.
Avem puțin timp.
Lasă-mă să trec peste asta.
Poți să te uiți la
asta pe cont propriu.
Adică, asta demonstrează un
fel de fapt mișto că...
O voi spune doar
la un nivel înalt.
Dacă aveți o
transformare de program,
deci dacă am o
metodă de a transforma
un program într-un alt program,
dar se face prin algoritm.
Deci un mod algoritmic
care transformă un
program într-un alt program.
Întotdeauna va exista
un program al cărui comportament este
neschimbat de transformare.
Aceasta se numește
teorema punctului fix.
Deci există un program al
cărui comportament
nu se schimbă,
indiferent de modul în care încercați
două programe de transformare - o
demonstrație ușoară folosind
teorema recursiunii.
Puteți privi
diapozitivul offline
separat dacă doriți
să vedeți cum decurge.
Este destul de simplu.
Iată un alt exercițiu
al teoremei recursiei.
Deci, dacă am o-- să
presupunem că o
mașină Turing este minimă
dacă descrierea sa este cea
mai scurtă dintre toate
mașinile Turing care se comportă
așa cum o face,
care sunt echivalente cu ea.
Când eram universitar,
am luat un curs de programare.
Și unora dintre noi ne-a făcut
plăcere să scriem programe scurte
pentru a efectua exercițiile.
Probabil că în zilele noastre,
acest lucru este interzis
pentru că doar încurajează
stilul prost de programare.
Dar oricum, așa că ai
cam câștigat dacă ai
găsit cea mai scurtă soluție pentru
un anumit exercițiu de programare.  A
fost Heap Sort, îmi
amintesc, a fost unul dintre cei
pe care trebuia să le facem.
Deci asta e cam asemanator.  Vă
puteți imagina dacă oamenii ar încerca
să găsească cea mai scurtă
mașină Turing universală posibilă.
Atât de scurt este, în
sensul nostru, în ceea ce
privește
metoda de codificare pe care o avem în vedere,
o mașină este minimă dacă
nu există un program mai scurt care să
fie echivalent folosind
sistemul nostru de codare, oricare ar fi acesta.
Deci M este minim dacă ceva
care are o descriere mai scurtă
are o limbă diferită.
OK, deci să ne uităm la
colecția tuturor descrierilor
mașinilor Turing minime.
Și vreau să demonstrez că acel
limbaj este de nerecunoscut.  O
voi face folosind
teorema recursiunii.
Și este un fel de
exercițiu tare.
Și îl poți folosi de fapt pentru a
dovedi ceva mai puternic.
Dar să ne concentrăm pe
această teoremă deocamdată.
Așa că presupunem că avem...
și este, de asemenea, în micul
exercițiu frumos despre enumeratori.
Nu știu cât de confortabil
te-ai simțit vreodată cu enumeratorii.
Dar încerc să demonstrez că
acest limbaj
nu este recunoscut.
Așadar, amintiți-vă,
enumeratori,
puteți enumera exact toate
limbile recunoscute.
Așa că voi presupune că am
un enumerator pentru acest limbaj,
care doar imprimă toate
mașinile Turing minime.
Deci am un enumerator.
Este un program care
tipărește descrierile tuturor
minimelor - cele
mai scurte
mașini Turing posibile.
Și acum o să
am o contradicție.
Deci vom construi
această mașină Turing, R,
care primește propria sa descriere.
Și apoi, va
porni enumeratorul până...
deci uitându-ne la șirurile pe
care le produce enumeratorul.
Deci, acest enumerator produce
aceste mașini Turing minime,
una după alta - bucată,
bucată, bucată, bucată, bucățică.
Toate aceste mașini Turing minime
apar.
Și continui să te uiți la acelea
până când găsești una dintre ele
care este mai mare decât tine.
Și de unde știi tu cât de
mare ești?
Din descrierea pe care o
oferă teorema recursiunii.
Așa că continui să imprimi
aceste mașini Turing
până când găsești una
mai mare decât tine.
Și atunci, ce
faci cu asta?
Simulezi asta.
Deci acum, ce?  Ei
bine, ideea este
că vei
fi mai mic decât acea
mașină pe care o simulezi.
Pentru că ai așteptat
să găsești o mașină pe
care a produs enumeratorul,
care este mai mare decât tine.
Deci vei
simula acea mașină care este
mai mare decât tine.
Și așa, veți face
exact ceea ce face mașina aceea
la fiecare intrare,
pentru că veți simula întotdeauna

aceeași mașină la fiecare intrare.
Și așa, vei fi
echivalent cu acea mașină mai mare
.
Dar acea mașină mai mare
ar trebui să fie minimă,
deoarece E o produce.
Dar aici,
expuneți o mașină
care este mai mică decât atât -
acea mașină presupusă minimă
nu ar putea fi minimă.
Asta e contradicția.
Deci limbajul lui R, această
mașină pe care tocmai am produs-o, este
egal cu limbajul lui B.
Pentru că R ajunge să simuleze B.
Dar R este mai mic
decât B pentru că R
a așteptat până a găsit o mașină mai mare,
care este mai mare decât ea.
Deci B nu putea fi minim,
dar B a fost una dintre mașinile
pe care le-a produs enumeratorul.
Asta e o contradicție.
Așa că lasă-mă să verific asta.
Mă aștept că acest lucru va
cauza unora dintre voi arsuri la stomac,
dar haideți să facem tot ce puteți.
Să presupunem că am această colecție
de mașini Turing minime
și iau un
subset infinit din asta.
Așa că acum nu cer
să am toate
mașinile Turing minime.
Am doar o infinitate de
mașini Turing minime.
Este posibil ca acel
subset, oricare ar fi el,
să fie recunoscut de Turing?
Acum, gândește-te la asta.
Acum, puteți avea
limbi care
nu sunt
recunoscute de Turing, care
au
subseturi infinite de recunoaștere de Turing.
Ar putea fi pentru această limbă?
Și poate vă voi oferi o...
vă va fi de ajutor să
înțelegeți și poate să aplicați
metodologia pe care
v-am dat-o în această dovadă aici.
Și asta ar putea fi de
ajutor pentru tine.
Dar văd că acest lucru nu este...
acesta este un pic o luptă.
OK, hai să terminăm.
Două secunde,
alege doar ceva.
Deci majoritatea are
răspunsul corect aici.
Deci, de fapt, această
dovadă ar
funcționa în continuare dacă enumeratorul ar
enumera un subset infinit
de mașini Turing minime.
Pentru că tot ce ai nevoie
este să aștepți până când
apare unul mai mare decât tine.
Și tot ce
trebuie să facă R este să aștepte
până când apare unul care este
mai mare decât R,
ceea ce cu siguranță se va
întâmpla în cele din urmă
dacă submulțimea este infinită.
Și apoi R simulează acea mașină mai mare
și acționează în același mod,
demonstrând astfel că
nu ar putea fi minimă.
Deci, este exact aceeași dovadă care
arată că răspunsul aici
este Nu.
Și este un fel de curiozitate.
Nu este neapărat atât de
ușor să construiești
limbaje care nu numai că
nu sunt recunoscute,
dar nu au
submulțimi recunoscute -
subseturi infinite.
Evident, o
submulțime finită va
fi recunoscută pentru că
ar fi și decidabilă.
Deci oricum, hai să mergem mai departe.
Alte
aplicații -- deci mai întâi,
o aplicație din lumea reală --
cineva cere
un exemplu
de limbaj dintr-un
subset de recunoscut al
unei limbi nerecunoscute.
Așa că începem cu ceva
care nu este de recunoscut
și putem veni
cu o rapidă...
Deci, iată, nu știu
dacă asta te va ajuta.
Deci întrebarea este,
pot da un exemplu
de limbaj nerecunoscut
care are un subset de recunoscut?
Deci nu am pregătit asta, dar
lasă-mă să văd dacă asta te ajută.
Deci, să luăm complementul ATM.
Am arătat deja că
complementul ATM nu este de recunoscut.
Deci acestea sunt mulțimile
de perechi, M și w,
unde M nu acceptă w.
Deci, dacă mă concentrez doar pe acele
M, care sunt automate finite,
care sunt o subclasă
de mașini Turing,
atunci pot obține
răspunsul pentru acele M.
Deci, pentru infinitele cazuri în care
mașina Turing nu
scrie niciodată pe bandă,
devine chiar decidabilă.
Deci nu știu
dacă este util,
dar cu
siguranță puteți găsi cazuri în care există

limbi indecidabile care
au submulțimi decidabile,
limbi de nerecunoscut care
au
subseturi infinite recognoscibile.
Dar există un exemplu
în care nu este adevărat,
în diapozitivul anterior.
OK, o mulțime de întrebări
apar aici.
Da, văd și
alte propuneri aici.
Dacă luați
complement ATM și vă uniți
cu orice
șiruri vechi de 1,
doar o stea, presupunând
că o stea -
doar șirurile de
1 nu vor
codifica niciodată pentru o mașină Turing -
asta va
fi încă de nerecunoscut.
Dar apoi puteți
doar să aruncați toate
acele șiruri
de 1 și
veți obține un subset infinit.
Oh, stai un minut.
Este încă de nerecunoscut.
Nu e bine.
Oh, nu, da, am
aruncat lucrurile greșite.
Arunci descrierile
mașinilor Turing
și îți mai
rămân doar șirurile de o stea.
Și așa, asta devine
decidebil, chiar obișnuit.
Oricum, nu sunt sigur că
te ajut.
Să trecem la
alte aplicații.
Deci, aceasta este un fel de
aplicație curioasă care
se află de fapt în lumea reală,
unde o mașină ar putea dori
să obțină o copie a ei însăși și
apoi să facă ceva poate
chiar nefast cu o
copie a propriului cod.
Și acesta ar fi
un virus de computer.
Virușii informatici fac
copii ale ei înșiși
și apoi le propagă prin
internet, sau pe orice media pe care o
aveți, pentru a infecta
alte computere.
Și sunt sigur că
cunoaștem cu toții virușii informatici.  Ei
bine, trebuie să obțină
copii ale lor
pentru a face infecția.
Cum fac asta?
Mulți dintre ei funcționează într-un mod în
care fie într-o limbă, fie
într-un sistem, în care
pot face referire
la propriul cod, fie
uitându-se la codul mașinii,
fie prin orice
acces direct la propriul cod.
Există limbi și
sisteme care permit acest lucru.
Dar nu sunt un expert
în virușii informatici.  Aș
fi șocat dacă
nu sunt alți viruși care
au acces la propriul cod
folosind ceva în același --
folosind practic metoda
teoremei recursiunii.
Nu am făcut un
studiu sistematic.
Dar sunt sigur că, dacă
nu vă puteți accesa
propriul cod direct
folosind un mecanism de sistem de operare
, unele primitive,
singura altă modalitate
este practic să faceți metoda pe
care tocmai am descris-o.
OK, deci o altă aplicație
este într-o ramură a matematicii
numită logică matematică.
Unde, îmi imaginez că mulți
dintre voi ați auzit de opera
lui Godel de la începutul secolului
al XX-lea,
unde arată că
puteți veni --
este posibil să demonstrați
că există
afirmații matematice adevărate, dar
care nu pot fi dovedite.  fi
adevărat.
Deci dovadă -- ar putea exista
ceva de genul poate chiar și
întrebări care ne interesează,
cum ar fi întrebarea P versus NP,
pe care, la un moment dat, le vom
analiza în câteva săptămâni -
de fapt, da, poate peste două
sau trei săptămâni de acum înainte  .
Există multe
probleme matematice nerezolvate.
Și oamenii se întreabă,
poate pur și simplu
nu există nicio modalitate de a le dovedi într-
un fel sau altul.
Așa că în anii 1930, când
Godel și-a făcut munca, a
șocat
comunitatea matematică
arătând că dovezile
nu funcționează pentru orice.
Pot exista lucruri care sunt
adevărate pe care nu le poți dovedi.
În Hilbert, în special,
din a 10-a problemă a lui Hilbert,
el a fost consternat de acest
rezultat.  Pentru că mai devreme
crezuse că orice
este adevărat poți dovedi.
Deci, oricum, să vedem doar cum...
Am să schițez cum
facem de fapt asta.
Pentru că acum avem un
fel de tehnică suficientă
pentru a vă oferi măcar
o idee despre cum să
demonstrați că există
afirmații adevărate, dar de nedemonstrat
și chiar să expuneți una.
OK, logica matematică
este studiul matematic
al matematicii în sine.
Prima teoremă de incompletitudine a lui Gödel
, așa cum am descris-o,
este că, în orice
sistem formal rezonabil
de
demonstrabilitate matematică, vor
exista niște
afirmații adevărate care
nu pot fi demonstrate.
Și pentru a obține un fel de
schiță a dovezii...
N-ar trebui să spun aici o dovadă.
Vom face o schiță de probă.
Vom folosi practic
două proprietăți ale sistemelor de dovezi formale
.
Unul este acel tip de
proprietate evidentă pe care te-ai aștepta să o aibă
toate sistemele de probabilitate
, este că poți
dovedi doar lucruri adevărate.
Deci, dacă se
dovedește ceva, va fi adevărat.
Nu poți dovedi nimic fals.
Dacă poți dovedi lucruri false,
sistemul tău de demonstrabilitate
este prost.
Și celălalt lucru
este că dovezile
sunt verificate de mașină.
Deci, dacă scrieți-- faceți-
vă sistemul într-un mod formal
și aveți această
noțiune formală de demonstrații,
care stă la baza tuturor
raționamentului matematic, de altfel.
Acest lucru este complet
bine acceptat.
Ambele proprietăți sunt
acceptate de matematicieni.
Apoi, în principiu, puteți
converti orice demonstrație matematică
într-o formă pe care
o puteți verifica pe computer.  Ar
putea deveni mult mai lung.
Dar, în principiu, puteți
pune dovada într-o formă în
care un computer
ar putea verifica dovada.
Și modul în care vom
încadra asta în modul în care am
vorbit
despre lucruri este
că limbajul
tuturor perechilor de dovezi,
declarația virgulă fiind dovedită -
deci unde pi este o dovadă
a afirmației phi -
aceasta este o  lucru decidabil.
Deci, puteți verifica, de către
mașină, dacă pi
este o dovadă validă a phi.
Deci, verificatorul dvs. de dovezi poate spune:
Da, este valid, Nu, nu este valid.
Și asta e ceva ce
poți face prin algoritm.
Deci, acestea sunt cele două
presupuneri pe care le vom
face despre
sistemul nostru de dovezi.
Și asta e tot ce vom avea
nevoie.
Acum, prima
concluzie, care este,
cred, un fel de
mic exercițiu
despre tipul de gândire pe care l-am
făcut în acest curs.
Numărul 2, verificabilitatea
implică faptul că setul
de afirmații demonstrabile
este recunoscut.
De ce?
Să presupunem că vă dau o
afirmație care are o dovadă...
o afirmație demonstrabilă.
Nu spun că este o
afirmație adevărată, neapărat.
Aceasta va fi poate o
clasă mai mare de afirmații.
Dar afirmația
care are dovezi,
este un limbaj de recunoscut.
Pentru că, dacă îți dau
o declarație,
recunoaștetorul tău va
lua acea declarație
și va începe să caute prin
toate dovezile posibile.  Va
privi șir
după șir ca o
dovadă candidată, una după alta.
Unele șiruri, desigur, majoritatea
șirurilor vor fi vechi.
Dar din când în când, o
dovadă va apărea.  Va
fi un șir care
este o dovadă validă a ceva.
Și apoi vei
verifica, oh,
lasă-mă să văd dacă
asta e o dovadă validă.
Și dacă demonstrează
afirmația pe care o am în minte
și dacă este, atunci
accept acea afirmație.
Și trece prin
declarație prin...
intrarea este o
declarație matematică.
Și asta va fi acceptat
dacă mașina, căutând
prin toate
dovezile posibile, găsește una
și apoi acceptă
acea afirmație.
Deci, colecția
tuturor afirmațiilor
care au o dovadă,
este de recunoscut.
Deci, în mod similar, dacă luați
declarații de forma
M și w este în
complementul ATM.
Deci M nu acceptă w.
Dacă luați toate declarațiile
de acea formă în care M nu
acceptă w, sau M, w este în
complementul ATM,
unele dintre aceste declarații pot
avea dovezi în sistemul dvs.
Unele dintre ele pot să
nu aibă dovezi.
Dacă toate ar
avea dovezi, dacă
poți dovedi fiecare
afirmație a acestei forme
atunci când se întâmplă să fie adevărată --
evident, nu le poți dovedi pe
cele care nu sunt adevărate.
Dar dacă puteți dovedi toate
afirmațiile adevărate de acest fel,
atunci complementul ATM ar
fi recunoscut de Turing.
Pentru că poți trece prin, doar
din același motiv ca mai sus.
Dar știm că este fals.
Deci trebuie să existe o
afirmație de acest fel care este
adevărată, dar nu are o dovadă.
Pentru că altfel,
complementul ATM
ar fi recunoscut.
Deci am făcut de fapt prima
jumătate a teoremei de incompletitudine a lui Godel
.
A doua jumătate, pe care, din
păcate,
nu vom avea timp s-o terminăm, dar permiteți-mi
doar să vă dau schița,
este că putem folosi
teorema recursiunii pentru a o da în mod specific -
vedeți, ceea ce am arătat
aici este că
există  o afirmație de această formă
care este adevărată, dar nedemonstrabilă.
Nu prezintă
unul anume.
Acum teorema recursiunii
vă permite să dați una anume.
Iar cel,
practic, implementează
așa-numita
declarație Godel sau
sensul Godel care spune: „Această
afirmație este de nedemonstrat”.
Și puteți oficializa
asta exact.
Și atunci acea afirmație
devine adevărată, dar de nedemonstrat.  Să
spunem doar de ce.
Pentru că dacă
afirmația ar fi falsă, să
presupunem că
afirmația ar fi falsă,
atunci, ei bine, atunci
ar fi demonstratabilă.
Pentru că adevărul spune că
nu este demonstrat.
Dar dacă afirmația
ar fi dovedibilă,
atunci trebuie să fie
adevărată, ceea ce ar
însemna că ar fi nedemonstrabilă.
Deci singurul rezultat viabil
aici este că afirmația
este de nedemonstrat.
Și adică,
așadar, este adevărat că
este de nedemonstrat.
Deci aceasta este
o afirmație adevărată,
dar nu are nicio dovadă.
Și lăsați-mă să nu trec prin
asta pentru că din nou,
din păcate, avem
scurt timp.
Dar puteți implementa acest lucru folosind
teorema recursiunii pentru a face
o anumită mașină, R, în care
nu puteți demonstra că R
nu acceptă, să zicem, un șir 0.
Deci puteți găsi un anumit
R folosind
teorema recursiei, unde este
imposibil de demonstrat
că R nu acceptă 0.
Chiar dacă, prin construcție,
R nu acceptă 0.
Deci este
puțin alunecos acolo
pentru că trebuie să
înțelegem ce
înțelegem prin demonstrație în cadrul
sistemului formal
față de forma noastră externă
de raționament,
dar luând  noi un
pic mai departe.
Așa că pentru cei cărora le pasă,
sper că această mică digresiune
a fost interesantă.
După cum am menționat la
început, pentru cei
dintre voi cărora nu le pasă,
nu trebuie să vă faceți griji.
Nu va fi la
jumătatea trimestrului sau la examenul final.
Nu vei fi
responsabil pentru ultimele cinci
minute sau cam asa ceva ale prelegerii.
Dar am crezut că este
o aplicație interesantă
a teoremei recursiunii la
o problemă din afara
informaticii în logica matematică.
OK, deci aici este din nou întregul
raționament.
Te invit să te uiți
la asta pe slide-ul
pe care l-am postat dacă ești curios.
Deci, oricum, o scurtă
trecere în revistă a zilei de astăzi
este că am trecut prin
auto-referință
și teorema recursiunii.  Am dat
câteva aplicații.
Și am făcut o schiță a
primei teoreme de incompletitudine a lui Godel
în logica matematică.
OK, așa că asta e tot ce voi
avea pentru tine astăzi.  Am
epuizat timpul.
Și voi răspunde la orice întrebări.
Deci, revenind la
exemplul mașinii MIN Turing,
cineva întreabă, de
unde știu că există
o mașină Turing care este
mai lungă decât mașina, R, pe
care o construiesc?  Ei
bine, există infinit de
mașini în MIN TM
sau în
submulțimea infinită a MIN TM.
Deci, în cele din urmă, unul
dintre ele va
trebui să fie mai lung decât
mașina pe care o construiesc.
Pentru că aceasta este o mașină
de o dimensiune foarte specifică
și, în cele din urmă, va
trebui să apară una mai mare
.
Deci aceasta poate fi o
întrebare similară.
Acum, o altă întrebare similară
este despre, cât de mare este R?
Și dimensiunea lui R din
acel lucru anterior aici...
Nu știu dacă vrem
să trecem prin asta.
Dar, OK, să ne
uităm repede la asta.
Această mașină, R, are o
dimensiune fixă, predeterminată.
Mărimea sa nu depinde de B.
Depinde de E pentru că
va simula E.
Dar E ar putea produce
șiruri foarte, foarte lungi.
În cele din urmă, va fi.
Deci E este fix.
Și apoi, dimensiunea lui R este fixă.
Deci, în cele din urmă, R
va găsi o mașină
care este mai mare decât este.
Dar să ne uităm la...
corect, deci aceasta este
o întrebare bună.
Mă întrebam dacă voi
primi întrebări de acest gen.
Aceasta este revenirea la
întrebarea în logică
aici, la sfârșit.
Da, pentru că am spus că această
afirmație aici este de nedemonstrat.
Dar, într-un fel, am dovedit-o.
Pentru că de unde știu că este adevărat?
Și ți-am dat un
argument pentru asta.
Deci, trebuie să faceți
diferența
între raționamentul pe
care îl oferim
și sistemul formal despre care
raționăm.
Și sistemul formal despre
care raționăm
nu este capabil să demonstreze acest lucru.
Dar suntem în afara
acestui sistem formal,
astfel încât să putem raționa
despre sistemul formal.
Știu că
pare puțin pervers.
Și logica matematică
este puțin complicată
pentru că trebuie să se ocupe
de astfel de probleme.
Dar aceasta este o argumentare în cadrul
oricărui sistem formal
de probabilitate, acesta
va fi adevărat.
Dar asta este un fel de
aproximare
a propriului nostru proces de gândire.
Deci e alunecos, sunt de acord.
Deci, o întrebare bună aici,
teorema lui Godel ar mai
păstra sisteme informale în care
nu solicităm ca dovezile
afirmațiilor să fie decidabile?
Deci nu spun că
dovezile sunt decidabile.
Că poți...
dovezile pot fi verificate.
Deci puteți testa dacă
o dovadă este o dovadă.
Dacă nu poți testa dacă
o dovadă este o dovadă,
nu cunosc oameni care să
fi studiat această situație.
Deci, acesta este
un caz puțin mai complicat.
Nu sunt sigur ce
să spun despre asta.
Pot da un exemplu de două
mașini Turing echivalente
în care una are o descriere mai scurtă
decât cealaltă?
Cum definim
lungimea descrierii?  Ei
bine, nu am
definit niciodată cu adevărat sistemul nostru de codificare.
Dar orice
sistem de codificare pe care doriți să îl utilizați,
va reprezenta
mașinile Turing ca șiruri.
Și acele șiruri
vor avea o lungime.
Și așa, nu
contează cu adevărat ce
sistem de codare vei
folosi, deoarece afirmația nu
va fi adevărată în niciunul dintre ele.
Am putea trece prin
exercițiul de definire a
unui anumit sistem de codare.  Va
fi destul de
obositor să faci asta.
Dar vă puteți imagina doar că scrieți
stările,
funcția de tranziție și cetera, și cetera,
ca acest șir mare și lung.
Și acesta va fi
sistemul nostru de codificare.
Și apoi vor
fi niște mașini lungi.
Unele mașini vor avea
reprezentări lungi,
iar alte mașini care
au reprezentări scurte.
Și va
exista o mașină în care
puteți introduce o
grămadă de stări inutile
care nu sunt niciodată accesate.
Deci, puteți extinde -
puteți să adăugați un fel de
nedorit la descrierea
mașinii, care
nu va face nimic.
Dar va face
descrierea mașinii să fie
inutil de lungă
în comparație
cu o altă
descriere, care
va calcula același
lucru, dar va fi mult mai scurtă.
Deci puteți
găsi cu siguranță exemple
de perechi de mașini care
fac același lucru, unde una
este mult mai lungă decât cealaltă.
Deci voi închide
sesiunea aici.
Și voi fi în curând
pe link-ul orelor de birou
și voi vedea pe câțiva dintre voi acolo.