[SCRÂȘIT] [FOSȘIT] [CLIC] PROFESORUL: Bine, de ce nu începem. Deci bine ai revenit. Mă bucur să vă văd pe toți. Și ce am făcut în teoria calculului? Am vorbit despre mașinile Turing și despre puterea mașinilor Turing. Am început de la început prin a arăta o grămadă de teoreme de decidebilitate care prezintă puterea mașinilor Turing de a calcula proprietățile automatelor finite, gramatici fără context și așa mai departe în unele cazuri. Și ultima prelegere, am vorbit despre limitările puterii mașinilor Turing prin demonstrarea teoremelor de indecidibilitate. Așa că am arătat că acest limbaj ATM, problema de acceptare pentru mașinile Turing în sine este o problemă indecidabilă. Aceasta a fost prima dintre multele probleme indecidabile pe care le vom întâlni. Și, deși am demonstrat indecizia ATM folosind metoda de diagonalizare, așa cum sperăm că vă amintiți, vom introduce o nouă metodă pe care am previzualizat-o data trecută, numită metoda reductibilității, care este modul în care sunt prezentate de obicei alte probleme. fi indecidabil. Și așa vom rămâne cu asta pentru această prelegere și, de asemenea, pentru următoarea prelegere. Vom vorbi despre indecizibilitate. Și cred că vor fi câteva discuții suplimentare după aceea. Dar aceasta este una dintre temele importante ale cursului este de a înțelege acel prag dintre decidebilitate și indecizibilitate, sau limitările de calcul, OK. Așa că astăzi, așa cum am menționat, vom vorbi despre metoda reductibilității pentru a dovedi problemele indecidabile și, de asemenea, pentru a dovedi problemele nerecunoscute, Turing de nerecunoscut. Vom introduce această noțiune de reductibilitate în general. Și vom vorbi, de asemenea, despre un tip foarte specific de reductibilitate numit reductibilitatea cartografierii. Așa că astăzi, așa cum am promis, vom vorbi despre utilizarea reducbilităților pentru a demonstra că problemele sunt indecidabile sau de nerecunoscut. Deci asta va fi metoda noastră generală, hopa, mă fac mai mic, mulțumesc. uit mereu. Mulțumesc pentru memento. Deci, folosirea reducebilităților pentru a demonstra că problemele sunt indecidabile sau de nerecunoscut, iar modul de bază care funcționează este că vom folosi o altă problemă pe care o știm deja că este indecidabilă sau de nerecunoscut pentru a demonstra că alte probleme sunt de nerecunoscut. Așa că ultima dată am făcut un exemplu rapid . Vom trece din nou peste acel exemplu doar pentru a pregăti scena. Și apoi vom vorbi despre asta mai detaliat. Deci, după cum vă amintiți de data trecută, am avut această problemă HALT TM, care este problema testării pentru o anumită mașină Turing și o intrare la acea mașină Turing, dacă mașina Turing se oprește, fie acceptând, fie respingând, dar doar dacă se oprește . Care este o problemă oarecum diferită , strâns legată, evident, dar oarecum diferită de problema ATM, care doar testează dacă mașina Turing acceptă. Am arătat deja că ATM este indecidabil. Acum, probabil, HALT TM ar putea fi decidabil. Știi, nu este exact aceeași problemă. Dar vom arăta că HALT TM este la fel de indecidabil. Am făcut asta ultima dată, dar o revăd din nou. De asemenea, voi arăta că HALT TM este indecidabil. Am putea să ne întoarcem la metoda de diagonalizare și să o facem de la zero. Dar, în general, nu asta se face. În general, ceea ce fac oamenii este că folosesc o reductibilitate dintr-o problemă cunoscută indecidabilă. Și așadar, ceea ce vom arăta este o dovadă prin contradicție care spune că dacă HALT TM ar fi decidabilă, atunci și A TM ar fi decidabilă. Și știm că nu este. Și asta în virtutea ceea ce numim o reductibilitate de la A TM la HALT TM. Și o să explic cu terminologia. Și vom avea șansa să ne jucăm cu conceptul pe tot parcursul prelegerii. Deci vom vedea tot felul de variații diferite. Așadar, așa cum am spus, vom presupune că HALT TM este decidabilă și vom folosi asta pentru a arăta că A TM este decidabilă, ceea ce știm că nu este adevărat. Așa că parcurgând-o rapid pentru că am făcut-o deja o dată înainte, vom presupune că HALT TM este decidabilă. Să presupunem că mașina Turing R este decisivă. Și acum vom arăta că ATM este decidabil prin construirea unei mașini Turing S, care folosește R pentru a decide ATM. Asta va fi contradicția noastră. Deci iată mașina S. Trebuie să țineți cont de care este scopul lui S. Vom proiecta S pentru a rezolva ATM, despre care știm că nu este decidabil. Așa că nu vă confundați cu asta. Ne propunem o contradicție. Deci vom folosi S ca de obicei... ei bine, ar putea exista și alte variații. Dar pentru moment, S va fi folosit pentru a decide ATM. Deci putem încerca să ne dăm seama cum putem decide ATM. Și modul în care o vom face este să folosim testerul nostru HALT TM pe care am presupus că îl avem. Și vom lua mai întâi M și w, unde încercăm să stabilim, acceptă M w? Și vom testa mai întâi dacă M se oprește pe w. Dacă nu, am terminat. Pentru că nu ar putea accepta w, M nu ar putea accepta w dacă nici măcar nu se oprește doar pe w. Deci, dacă rapoartele R nu sunt valabile, putem respinge imediat. Dar chiar dacă R spune că se oprește, suntem încă în formă, deoarece acum putem rula M pe w până la finalizare, deoarece R ne-a promis că se va opri. R este precizat. Și se presupune că R este corect. R se spune că M se oprește pe w, așa că acum nu trebuie să ne facem griji să intrăm într-o buclă, ceea ce nu avem voie să facem, deoarece luăm o decizie. Încercăm să decidem ATM aici. Dar acum le putem rula pe w până la finalizare. Putem afla ce face M pe w. Și atunci putem acționa în consecință. Deci folosim decizia HALT TM pentru a decide ATM. Acesta este numele jocului aici, bine? Și asta e o contradicție. Prin urmare, presupunerea noastră că HALT TM era decidabilă a trebuit să fie falsă. Deci este indecidabil. BINE? Este important să înțelegem acest lucru, deoarece acesta este un fel de prototip pentru toate celelalte dovezi de indecidibilitate pe care le vom face în continuare. OK, așa că putem să luăm câteva secunde aici. Dacă există ceva ce nu înțelegeți despre asta, este un moment bun să întrebați. Nu văd multe mesaje aici, sau niciunul, așa că de ce nu continuăm? Dar dacă întrebi, pot ajunge și la următorul diapozitiv, bine. Începem. Deci iată conceptul de reductibilitate. Și știu, am predat acest curs de multe ori. Știu unde sunt locurile accidentate în ceea ce privește oamenii care se luptă cu materialul. Conceptul de reducebilitate este puțin complicat. Așa că nu te simți rău dacă nu o primești imediat. Știi, de aceea voi încerca să merg încet în această prelegere pentru a mă asigura că suntem cu toții împreună pentru a înțelege cum funcționează reductibilitatea. OK, deci conceptul de reductibilitate este că spunem că o problemă este reductibilă la alta, să spunem A reductibilă la B. Înseamnă că poți folosi B pentru a rezolva A. Asta înseamnă ca A să fie reductibilă la B. OK, deci Voi da o grămadă de exemple informale în acest sens, sau exemple simple în acest sens. Și apoi vom începe să-l folosim cu adevărat. Deci, exemplul 1, acesta este un fel de material din afara cursului. Dar cred că este ceva ce poți aprecia. Știi, toată lumea știe că poți măsura aria unui dreptunghi măsurând lungimile celor două laturi, măsurând lungimea și lățimea dreptunghiului. Deci, cu alte cuvinte, dacă ai avea problema determinării zonei, ai putea reduce acea problemă la problema măsurării lungimii și lățimii dreptunghiului. Deci, aici, luăm o problemă și o reducem la o altă problemă. Știi, este de imaginat că măsurarea lungimii și lățimii este mai ușoară decât ar fi măsurarea directă a zonei acoperind cumva spațiul cu gresie, este o modalitate de a o măsura. Dar îți spune că nu trebuie să faci asta. Problema măsurării zonei este mai ușoară decât acoperirea cu gresie. Puteți măsura lungimea și lățimea și gata. Deci reductibilitatea este o modalitate de a face problemele mai ușoare prin traducerea lor într-o problemă mai ușoară. Deci, iată un alt exemplu pe care l-am văzut deja. Nu am numit-o reductibilitate. Dar dacă vă amintiți acum câteva săptămâni, vorbeam despre limbile A NFA și A DFA, problemele de acceptare pentru NFA și DFA. Și am oferit o modalitate de a rezolva problema A DFA. După cum vă amintiți, mașina Turing a simulat automatul finit. Și am rezolvat problema NFA nu făcând-o direct, ci transformând NFA într-un DFA și apoi folosind soluția pentru A DFA. De fapt, ceea ce făceam era să reducem problema A NFA la problema A DFA. Deci haideți să facem un alt exemplu. Iată o problemă. Iată un exemplu că, din nou, probabil că nu te-ai gândit la asta în acest fel. Dar din temele tale, am avut această problemă de împingere, problema de a determina dacă un automat de împingere împinge vreodată pe stiva lui pentru orice intrare. Știu că mulți dintre voi v-ați luptat cu acea problemă lucrând la ea, sperăm că o rezolvați într-un fel sau altul. Deci, există o modalitate de a o rezolva este prin reducerea problemei pusher la E CFG, golul pentru CFG, care este echivalentul golului pentru PDA-uri. Adică, aceasta este soluția pe care am avut-o în minte, care este o soluție deosebit de simplă și scurtă. Desigur, nu este singura soluție. Puteți să vă duceți automatul pushdown acolo unde încercați să determinați dacă împinge vreodată. Și poți lua statele care sunt pe cale să facă un impuls. Și în loc să- i faci să facă un impuls, îi faci să accepte stări. Și scapi de stările originale de acceptare. Așa că acum ați convertit acest automat într-unul care acceptă de fiecare dată când împingerea inițială a automatului . Și acceptă, și apoi trebuie să treacă la sfârșitul intrării, desigur. Deci intră într-o stare de acceptare și se mută la sfârșitul intrării. Deci, de fiecare dată când mașina originală era pe cale să împingă, noua mașină pe care tocmai o creați aici va intra într-o stare de acceptare la sfârșitul introducerii. Acum, pentru a testa dacă mașina originală folosește vreodată stiva, este suficient să testăm dacă noua mașină acceptă vreodată un șir S. OK, deci asta e o modalitate. Nu vreau să complic prea mult asta chiar aici și să te fac să te gândești din nou la teme. Dar aceasta este o modalitate de a reduce o problemă la alta. Și dacă nu îl înțelegi prea bine pe acesta, concentrează-te doar pe celelalte două exemple. Nu vreau să petrec timp cu setul de teme 2 chiar acum. Așa că putem aborda totul separat dacă doriți. Este, de asemenea, soluția care este scrisă în setul de soluții care este postat pe pagina de start, de altfel. OK, deci revenind să vedem, gândindu-ne la reducbilitate. Ceea ce am în minte, din nou, acesta este un fel de reformulare, dar încerc să-l pun cu ciocanul în sensul că, dacă A este reductibil la B, atunci rezolvarea lui B oferă o soluție pentru A. Pentru că asta se întâmplă în fiecare dintre aceste exemple. . Acum, cum vom folosi asta? Vom folosi asta în următoarele două moduri. Unul este de a observa că, dacă A este reductibil la B și B este o problemă ușoară, atunci A trebuie să fie și ușoară pentru că avem o modalitate de a converti problemele A în probleme B. Avem o modalitate de a rezolva A folosind B. Deci B este ușor. Atunci acum poți rezolva A prea ușor. Pentru că poți rezolva A folosind B, ceea ce este ușor. Poate că acest lucru este cel mai clar aici, în exemplul 1, unde măsurarea zonei ar putea părea dificilă la prima vedere. Ar putea fi nevoit să ieși peste toată zona. Dar nu este greu pentru că trebuie să măsori doar lungimea și lățimea. Deci faptul că B este ușor vă spune că A este ușor. Dar, de fapt, acesta nu este modul în care îl vom folosi cel mai adesea. O să- l folosim cel mai adesea în a doua versiune, care este puțin mai complicată. Dar acesta este modul în care va trebui să te obișnuiești cu asta. Deci, dacă A este reductibil la B și știi că A este greu, indecidabil, de nerecunoscut, indiferent de forma de hard care îți pasă, dacă știi că A este greu și A este reductibil la B, atunci asta îți spune că și B trebuie să fii greu. De ce? Pentru că dacă B ar fi ușor, atunci A ar fi ușor. Dar presupunem că A este greu. Așa că și B trebuie să fie greu. OK, deci inversez logica aici. Dar acest lucru este echivalent din punct de vedere logic. Deci trebuie să te gândești puțin la asta. Deci de ce nu te gândești la asta. Și permiteți-mi doar să răspund la câteva întrebări pe chat și să nu uitați că și AT sunt acolo. Așa că sunt bucuroși să vă răspundă la întrebări. Nu-i face să stea acolo singuri, bine. Deci cineva întreabă, este posibil ca A să fie reductibil la B și ca B să fie, de asemenea, reductibil la A? Deci asta e o întrebare bună. Asta se poate întâmpla cu siguranță. În acest caz, într-un anumit sens, A și B vor fi echivalente. Deci rezolvarea 1 va fi la fel de ușoară sau dificilă ca și rezolvarea celeilalte, OK? Deci vor fi echivalente din perspectiva dificultății de a le rezolva. Deci cineva întreabă - și aceasta este o confuzie perenă - așa că în slide-ul anterior aici, cred că voi reveni la el aici. Deci în ce direcție mergem? Reducem A TM la HALT TM sau HALT TM la A TM? Modul în care este scris pe diapozitiv este ceea ce am în minte. Aici reducem A TM la HALT TM deoarece folosim HALT TM pentru a rezolva ATM. Și asta înseamnă reducerea A TM la HALT TM. La fel ca aici, măsurarea ariei se poate reduce la măsurarea lungimii laturilor, folosim măsurarea lungimii laturilor pentru a rezolva zona. Deci reducem aria la lungimi, aria la lungimea laturilor. Dar știu că va trebui să te joci cu ea, să o digeri, să te obișnuiești. Bine, OK, deci hai să continuăm. OK, așa cum am spus, acesta din urmă, deoarece accentul pe acest curs este în principal pe limitările calculului. Așa că vom căuta modalități de a arăta probleme sau dificultăți. Ar putea fi dificil, în principiu, ca indecidabil. Sau ar putea fi dificil din punct de vedere al complexității, pe care ne vom concentra în a doua jumătate. Dar, în ambele cazuri, vom folosi conceptul de reductibilitate. Deci reductibilitatea va fi o temă. Trebuie să te simți confortabil cu reducbilitatea, OK. Așa că ne vom concentra mai mult pe ideea că, dacă reduceți A la B și știți că A este greu, asta vă spune că B este și greu. OK, așa că voi spune asta de câteva ori în cursul prelegerii de astăzi pentru a încerca să vă ajut să o obțineți. În regulă, iată un check-in. Un pic mai departe . Dar am crezut că a fost un check-in mai distractiv. Întrebarea este că unii oameni spun că biologia se poate reduce la fizică. Ei bine, poate totul se poate reduce la fizică, deoarece fizica vă spune despre legile universului. Iar biologia face parte din univers. Deci întrebarea mea pentru tine este, crezi? Și nu există un răspuns corect aici. Crezi, în opinia ta, biologia reductibilă la fizică? Poate că da, sau poate că există unele lucruri precum conștiința care nu pot fi reduse la fizică. Sau poate nu știm. Așa că sunt curios să vă cunosc părerile. Dar folosește într-un fel noțiunea de reductibil în spiritul a ceea ce am în minte aici. În sensul că, dacă ai putea înțelege pe deplin fizica, asta ți-ar permite să înțelegi pe deplin biologia? OK, iată-ne. Suntem aproape... interesanți, deși nu prea neaștepți presupun. Deci, cred că am terminat. 5 secunde, alege orice dacă vrei să obții credit pentru asta și nu ai selectat încă. Gata de plecare, se încheie sondajul. Iată rezultatele. Și așa cum am spus, nu există un răspuns corect aici. Dar dacă aș fi fost în clasă, aș fi ales B. Dar nu sunt surprins, mai ales într-o mulțime de MIT că A este câștigătorul, bine. Hai sa continuăm. OK, deci acum vom folosi din nou reductibilitatea. Acesta va fi încă un exemplu ca exemplul HALT TM , dar puțin mai greu. Și o să facem asta. Știi, următoarea prelegere, vom face mai multe reduceri, dar mult mai greu. Așa că trebuie să ne simțim confortabil, bine. Vreau să arăt ETM-uri. Deci E TM este problema golului pentru mașinile Turing. Este această limbă goală? O să-ți dau doar o mașinărie. Vreau să știu, este această limbă goală sau nu? Acceptă ceva sau acest limbaj este gol? Asta va fi indecidabil, nicio surpriză, dovadă prin contradicție. Și vom arăta că A TM este reductibilă la E TM. Deci aceste lucruri iau adesea o formă foarte asemănătoare. Și voi încerca să folosesc aceeași formă. Deci, dacă vă simțiți tremurând, cel puțin veți obține forma în care merge soluția și asta vă va ajuta, poate, la plug-in pentru a rezolva probleme, OK. Deci, dovadă prin contradicție, presupunem că E TM este decidabilă, opusă a ceea ce am încercat să arătăm. Și apoi arătați că ATM este decidabilă, ceea ce știți că este fals. Așa că vom spune că avem un decident pentru A TM, R, folosind aceleași litere intenționat aici doar pentru a încerca să obținem modelul pentru tine, așa că R hotărând E TM. Construiți S decizând A TM, OK. Așa că acum, hai să ne gândim împreună un minut înainte să-l pun acolo. Deci S, încerc să fac o decizie pentru ATM, folosind decizia mea pentru problema golului, OK? Deci avem R, care ne poate spune dacă limbajul lui M este gol. Așa că, de ce nu , pur și simplu, nu știu, să punem M în acel tester de gol și să vedem ce scrie? Nu spun că aceasta este soluția, dar așa s-ar putea gândi să găsești soluția. Deci esti cu mine? O să luăm M, avem un tester de gol. Să luăm M și să-l conectăm la R, să vedem ce spune R. R se va întoarce și ne va spune dacă limba lui M este goală sau nu. Acum, unul dintre aceste răspunsuri ne va face fericiți. De ce? Să presupunem că R ne spune că limbajul lui M este gol. De ce e bine? Cu asta, am terminat. Pentru că S încearcă să dea seama, noi încercăm să ne dăm seama exact, cineva mi-a spus răspunsul care este corect. Pentru că acum putem respinge. Dacă limba lui M este goală, este clar că nu acceptă w pentru că nu acceptă nimic. Deci, dacă R spune că limba lui M este goală, atunci suntem buni. Singura problemă este că spunem că limba lui M nu este goală. Și atunci ce știm? Ei bine, nu mult, nu prea mult care este util pentru a testa dacă M acceptă w. Știm doar că M acceptă ceva. Dar acel ceva poate fi sau nu w. OK, deci ce facem? Ei bine, problema este că M acceptă, posibil, tot felul de șiruri în afară de w, care cam îngrădesc lucrările. Ei interferează cu soluția care ne place. Am dori să putem folosi R pe M pentru a ne spune dacă M acceptă w. Dar M acceptă alte lucruri. Și asta complică imaginea. Deci ceea ce propun să facem, de ce nu modificăm M astfel încât să nu accepte niciodată nimic în afară de w? Primul lucru pe care M îl face în forma modificată este că se uită la intrarea sa și vede dacă este diferit de w. Dacă este diferit de w, respinge imediat. Acum luăm acea mașină modificată și o introducem în testerul de gol. Acum, testerul de goluri ne va oferi informațiile pe care le căutăm, deoarece dacă testerul de goluri spune că limbajul mașinilor modificate este gol, ei bine, știm că M nu acceptă w pentru că nu am schimbat modul în care M se comportă atunci când este dat w. Dar dacă R spune că limbajul lui M nu este gol , atunci trebuie să fie că M acceptă w. Pentru că am eliminat deja toate celelalte posibilități atunci când am modificat mașina. Așa că permiteți-mi să repet asta pe diapozitiv și să-l notez puțin mai formal. Deci ceea ce voi face este să transform M într-o nouă mașină Turing. O voi numi M sub w pentru a sublinia faptul că această nouă mașină depinde de W. De fapt, va avea w încorporat ca parte a regulilor mașinii. Deci, pentru un w diferit, vom ajunge cu o altă mașină aici. Deci aceasta este o mașină a cărei structură va depinde de cunoașterea lui w. Și acea mașină va fi foarte asemănătoare cu mașina originală M, cu excepția faptului că atunci când primește o intrare, să spunem că se numește X acum, acea mașină va compara X cu w și va respinge dacă nu este egală. În caz contrar, dacă X este egal cu w, va rula M pe w ca înainte. Deci nu va schimba comportamentul atunci când intrarea este w. Va schimba comportamentul doar atunci când intrarea este ceva diferit de w și apoi va fi respinsă, în regulă. Așa că mă voi uita la două aspecte ale acestui lucru. Mai întâi, să înțelegem limbajul acestei noi mașini. Și apoi vom vorbi și despre cum facem această transformare. Deci, în primul rând, doar pentru a sublinia, deci Mw funcționează la fel ca M. Are toate regulile lui M în el, cu excepția unor reguli suplimentare. Întotdeauna la primul pas, testează dacă X este egal cu w sau nu. Și dacă nu este egal cu, respinge. Nu este egal cu, respinge. Așadar, limbajul acelei noi mașini fie va fi doar șirul w atunci când M acceptă w, deoarece orice altceva este filtrat. Sau setul gol dacă M respinge ceva. Deci, este important să înțelegeți cel puțin comportamentul acestei noi mașini. Este la fel ca M, cu excepția filtrării tuturor intrărilor care nu sunt w. Acestea vor fi respinse automat. Deci este de asemenea important ca S să poată face această transformare. Dar susțin că va trebui să accepți asta dacă nu îl vezi în totalitate. Dar transformarea este pur și simplu să ia M și să adauge niște reguli noi, niște tranziții și stări noi, astfel încât primul lucru pe care îl face M sub w este să aibă doar o secvență de mișcări în care verifică dacă șirul de intrare este egal cu w sau nu. . Și dacă nu este egal cu w, doar respinge. Deci, este ușor să modificați M. Puteți scrie cu ușurință un program care să modifice stările și tranzițiile lui M pentru a face acest test la început. Așa că nu voi detalia astfel de lucruri în viitor. Dar doar pentru prima dată, vreau doar să mă asigur că înțelegeți că nu facem nimic rău aici. Acesta este un lucru complet legitim pe care S îl poate face. Deci S poate modifica M la această nouă mașină Mw, care filtrează acea nouă mașină, filtrează toate șirurile cu excepția lui w și le respinge. Deci S ia acea mașină nouă și ce va face cu ea? Va porni vreodată mașina aia? Nu. Această mașină nu este construită pentru funcționare. Această mașină este construită pentru alimentarea în R. Pentru că, după cum vă amintiți, alimentarea lui M în R a avut problema că M ar putea accepta lucruri în afară de w. Și asta încurcă rezultatul pe care îl obținem de la R în sensul că nu este util. Dar dacă introducem Mw în R, acum suntem buni pentru că dacă informația despre dacă limba lui Mw este goală de aici ne spune dacă M acceptă sau nu w. Dacă limbajul lui Mw nu este gol, atunci M acceptă w. Dacă limba lui M este goală, M respinge w. OK, așa că încep să primesc câteva întrebări bune aici. Lasă-mă să termin descrierea lui S. Deci cineva întreabă aici. Deci aceasta este o întrebare excelentă. De unde știm că Mw se oprește pe w, sau orice altceva? Noi nu. Mw poate să nu se oprească pe w. Nu ne pasă. Nu o să-l punem niciodată pe Mw pe nimic. Vom lua Mw ca o mașină și îl vom introduce în R ca descriere. Vom lua descrierea lui Mw și o vom introduce în R. Atunci este problema lui R. Dar s-a presupus că R răspunde testării de gol. Așa că tocmai am luat mașina originală, am modificat-o astfel încât singurul lucru posibil pe care l-ar putea accepta să fie w. Și acum introduceți-l în testerul de gol pentru a vedea dacă limbajul său este gol sau nu. Acum, dacă limbajul său nu este gol, trebuie să accepte w pentru că este construit pentru a nu accepta nimic altceva. Deci nu ne interesează dacă Mw ar putea ajunge să facă buclă. Nu vom conduce niciodată Mw. Recunosc, este un salt pentru mulți dintre voi. Deci va trebui să te gândești la asta. Deci vom folosi R pentru a testa dacă limbajul lui Mw este gol. Dacă da, înseamnă că M respinge w. Deci atunci vom respinge, dacă știm că limbajul lui Mw este gol, trebuie să fi fost faptul că M a respins w. Deci, acum, în calitate de decident A TM, care este ceea ce este S, S ar trebui să respingă, ceea ce avem aici în descriere. Și dacă nu, înseamnă că limba nu este goală. Deci M acceptă w și, prin urmare, acceptăm. Așa că există o mică întorsătură și aici. OK, deci hai să mai luăm câteva. Astept cateva intrebari aici. Așa că cineva întreabă, cum poți determina dacă limbajul este decidabil? Adică, asta facem. Puteți arăta că o limbă este decidabilă expunând o mașină Turing care o decide. Și puteți arăta că o limbă nu este decidabilă, ceea ce facem aici, demonstrând că nu este posibil ca o mașină Turing să o decidă. Știi, am făcut asta mai întâi cu ATM. Am obținut această contradicție prin diagonalizare. Și aici facem o reducere pentru a arăta ca metodă de demonstrare, bine. Hai sa continuăm. Așa că acum vom vorbi despre un tip special. Până acum am vorbit despre reductibilitate. Nu l-am definit într-un mod precis, deoarece există mai multe moduri diferite de a ajunge la noțiunea de reductibilitate precis. Și voi introduce o singură versiune, care este puțin mai restrictivă. Adică, un mod ceva mai restrictiv și puțin diferit de a privi lucrurile decât am făcut-o până acum. Dar urmau să existe unele beneficii în privința acestui tip particular de reductibilitate, pe care îl numim reducție de cartografiere. Va avea câteva beneficii pentru noi imediat și pe drum. Dar acest lucru este și puțin tehnic, așa că nu vă speriați. Ar putea părea complicat la început. Dar vom încerca să-l despachetăm pentru tine, OK. Deci, în primul rând, trebuie să vorbim în primul rând despre noțiunea de funcție computabilă. Deci, în general, când avem mașini Turing, ele fac da, nu. Acceptă, resping tot felul de lucruri. Deci este ca o funcție, doar un fel de calcul, un fel de funcție binară. Pentru aici, vom dori să vorbim despre mașinile Turing care calculează o funcție care convertește un șir în altul. Deci este maparea de la șiruri la șiruri. Și ar putea fi ca funcția care inversează șirul, de exemplu. Aceasta este o funcție posibilă pe care ați putea să o aveți aici. Dar, desigur, există miliarde de funcții posibile aici. Și vom vorbi despre funcțiile pe care le puteți calcula cu mașina Turing. Și asta înseamnă practic că oferiți intrarea funcției ca intrare către mașina Turing. Și ieșirea funcției, valoarea funcției iese ca ieșire a mașinii Turing, care să spunem doar că lasă acea valoare pe bandă atunci când se oprește. Se oprește cu valoarea funcției de pe bandă. Dar doar, ne gândim la algoritmi aici. Vino cu metoda ta preferată de a te gândi la algoritmi. Are o intrare și o ieșire. Și algoritmul doar calculează funcția luând ca intrare w, iar rezultatul este f din w. Nu trebuie să fie o mașină Turing. Orice algoritm care poate calcula ceva este suficient de bun. Toate sunt echivalente. Și acum vom folosi această noțiune de funcție pe care o puteți calcula pentru a defini un fel de reductibilitate numită reductibilitate de mapare. Voi spune că A este maparea reductibilă la B, scrisă cu acest simbol mai mic sau egal cu sub M. Și asta o să vezi mult. Apropo, este și la teme. Dacă există o funcție calculabilă așa cum tocmai am descris-o, unde ori de câte ori w este în A, f din w este în B. Și modul de a gândi la aceasta este cu această imagine. Deci A și B sunt limbi, scrise ca, aici este A și aici este B. Și acum există șiruri. Deci w ar putea fi în A. Ar putea fi din A. Și vă gândiți că încercați să rezolvați A. Încercați să decideți apartenența la A. Deci doriți să testați dacă w este în A sau nu. O mapare reductibilă este o funcție care mapează lucrurile din acest spațiu în acel spațiu astfel încât șirurile care sunt în A să fie mapate cu șirurile care sunt în B. Deci, dacă începeți cu w în A, f din w este în B. Și dacă w nu este în A, atunci f din w nu este în B. Din punct de vedere grafic, este o idee simplă. Va trebui să ne asigurăm că înțelegem de ce acest lucru se potrivește conceptului nostru de reducebilitate. Dar asta vom face. Dar oricum, să înțelegem mai întâi ce facem aici. Tocmai venim cu o funcție care poate face acest tip de mapare. Se traduce într-un fel problemele care intrări care pot fi sau nu în A în alte șiruri care pot fi sau nu în B. Dar un fel de menținere a aceleiași proprietăți de membru. Deci, dacă începi cu ceva în A, atunci când aplici f, vei ajunge cu ceva în B. Și invers, dacă nu ești în A, atunci nu vei fi în B, OK? Cineva întreabă, așa că doar câteva întrebări aici. Nu neapărat 1-la-1? Nu, deci funcția nu trebuie să fie 1-la-1. Ar putea exista mai multe lucruri care se mapează în același punct. Și există vreo restricție cu privire la alfabet? Nu. Așa că, înainte de a intra în exemplul, permiteți-mi să încerc să vă dau o idee despre de ce numim asta o reducere. Și motivul este, să presupunem că avem un astfel de f care poate face maparea așa cum am descris-o. Și avem, de asemenea, o modalitate de a decide apartenența la B. Deci, B este decidabil. Deci asta ne va spune imediat că A este decidabil. Pentru că dacă aveți o intrare și doriți să știți dacă este A sau nu, puteți acum să aplicați f și să testați dacă f din w este în B. Deci, testul lui w este în A, veți face testați dacă f din w este în B. Și presupunem că asta arată că A este reductibil la B. Deci, dacă ați putea rezolva problema B, asta vă oferă și o modalitate de a rezolva problema A. Deci, din nou, vom spune acest lucru de mai multe ori în mai multe moduri diferite. Așa că, dacă nu ați înțeles încă, nu vă panicați. Deci aici va fi un exemplu. Pe baza a ceea ce tocmai am arătat ultima dată în diapozitivul anterior, A TM, vom arăta cum A TM este de fapt maparea reductibilă la complementul E TM. Iar complementul este necesar aici. Funcția calculabilă pe care o vom oferi, care este, practic, funcția calculabilă va traduce problemele despre A TM în probleme despre E TM, deoarece mapam reducerea A TM la complementul lui E TM. Deci ceea ce facem aici este să mapam M și w la mașina Mw. Într-un fel, fierbem esența, ne reducem la esența dovezii pe care am dat-o în diapozitivul anterior. Acesta este cu adevărat miezul dovezii. Această traducere a lui Mw unde doriți să știți, este M acceptă w la o nouă mașină Mw în care testați dacă limba lui Mw este goală. Și așa amintește-ți Mw de înainte. Este mașina care filtrează toate non-w-urile și le respinge. Și motivul pentru care funcționează această funcție de reducere este că Mw este în A TM, dacă și numai dacă M sub w este în complementul lui A TM. Deci M acceptă w exact când limba lui Mw nu este goală, OK? Deci M acceptă w dacă și numai dacă limbajul lui Mw nu este gol. Așa că trebuie să te gândești puțin la asta pentru a-ți da seama că e... Știu că poate fi puțin complicat. Dar cred că ce vom face aici, cred că suntem la momentul pauzei. Așa că oh, nu, mai este un diapozitiv. Îmi cer scuze. Așa că hai să vorbim despre asta și apoi vom face o pauză de cafea. Deci, aceste proprietăți vor ajunge într-adevăr la ceea ce face ca reducția cartografiei să se potrivească cu înțelegerea noastră a ceea ce ar trebui să fie o reducție. Deci, dacă A este maparea reductibilă la B și B este decidabil, atunci la fel și A. Așa că se potrivește cu ceea ce ne dorim. Pentru că dacă A este reductibil la B și B este ușor, atunci A este ușor. Așa că aici ușor înseamnă decidebil. Și aici este dovada. Să luăm o mașină Turing care decide B și să construim o mașină Turing care decide A așa cum se spune, S funcționează așa. Își ia intrarea, calculează f din acea intrare, testează dacă f din w este în B folosind mașina R pe care am presupus-o. Avem R care decide B. Și dacă R se oprește, scoate același rezultat. Deci, dacă R acceptă, vom accepta. Dacă R se oprește și respinge, vom respinge. Și, desigur, vom rula în mod similar R. Deci, dacă R nu se va opri, nici nu vom ajunge să ne oprim. BINE? Așadar, corolarul este, și acesta este modul în care îl vom folosi , dacă A este reductibil la B și A este indecidibil, atunci la fel este și B. Așadar, așa cum am menționat, accentul pentru noi va fi asupra indecidibilitatii. Și poate doriți să vă gândiți că A este ca problema ATM despre care știm că este indecidabilă. Vom arăta că ATM-ul este mapare reductibilă la o altă problemă pentru a arăta că altă problemă este indecidabilă. Iar lucrul important despre cartografierea reductibilității este că se aplică și recunoașterilor. Deci, dacă A este maparea reductibilă la B și B este Turing recognoscibil, atunci la fel este și A. Deci, dacă reduceți A la o problemă de recunoscut, atunci A este de asemenea recognoscibil, aceeași dovadă. Pentru că vă puteți mapa w la f din w și îl puteți introduce în dispozitiv de recunoaștere. Asta vă va oferi un recunoaștere pentru limba originală. Și corolarul este că dacă A este maparea reductibilă la B și A este de nerecunoscut, atunci este și B. Deci aceasta este din nou acea logică inversată. Deci acum cred că suntem... hopa, am vrut să pun această poză mai devreme. OK, deci iată un check-in. Va fi mai mult un check-in pentru ca să văd cât de bine mă urmărești. Deci, acestea sunt câteva proprietăți-- așa că vă voi acorda un minut aici să vă gândiți la asta-- câteva proprietăți ale reductibilității cartografierii. Să presupunem că A este maparea reductibilă la B, ce putem concluziona? Înseamnă asta că îl putem întoarce? Dacă A este maparea reductibilă la B, înseamnă asta că B este maparea reductibilă la A? Ce zici de asta? Dacă A este maparea reductibilă la B, complementul lui A maparea este reductibil la complementul lui B, sau poate nici unul? Așa că puteți verifica tot ce se aplică, alegere multiplă, 5 secunde. Îmi pare rău că vă presăm, dar trebuie să mergem mai departe aici. Alege orice. Dacă nu știi, OK, 1, 2, 3, finalul, OK. Ei bine, majoritatea are dreptate. De fapt, este doar B. Acum, A chiar nu este în spiritul reductibilității. Pentru că, așa cum sugerează chiar și semnul de inegalitate de acolo, A fiind reductibil la B este într-adevăr un lucru destul de diferit decât B fiind reductibil la A. Deci asta e ceva. Nu vom demonstra asta chiar aici. Dar asta e ceva la care te-ai putea gândi. Dar partea B, cred, dacă te uiți aici doar la definiția reducebilității mapării, ea mapează șiruri înăuntru și ieșire către ieșire. Ei bine, asta se va întâmpla doar dacă schimbi înăuntru și ieși, așa cum faci când întorci complimente de ambele părți, este în continuare la fel și va funcționa în continuare ca o reducere de cartografiere, OK? Așa că acum suntem la pauza de cafea. Așa că vom lua cinci minute aici și voi răspunde cu plăcere la întrebări aici. Nu uitați de TA. Ei sunt aici pentru. BINE. OK, deci aceasta este o întrebare corectă aici. Știi, deci am avut această noțiune de reducere generală și de reducere cartografică. Nu sunt la fel. Deci, de fiecare dată când aveți o reducere de cartografiere, va fi un exemplu de reducere generală, dar nu invers. Deci, dacă te întorci și te uiți la reducerea pe care am oferit-o pentru HALT TM, unde am arătat că A TM se poate reduce la HALT TM de unde am început, de fapt nu este o reducere de cartografiere pentru că facem ceva mai complicat decât traducerea unei probleme ATM. la un HALT TM. Folosim decisorul HALT TM într-un mod mai complicat. Și există cazuri în care acest lucru este de fapt necesar. Deci nu vom discuta despre asta aici. Dar este de fapt un fel de problemă interesantă la teme pentru acasă , sau un fel de problemă la care să te gândești. Deci, mașinile Turing pentru f, nu este cu adevărat un decisiv, dar trebuie să fie... ei bine, cred că trebuie să fie un decisiv într-un fel. Întotdeauna se oprește. Mașinile Turing pentru f trebuie să se oprească întotdeauna. Trebuie să aibă întotdeauna o ieșire. Deci f pentru calcul, funcția trebuie să se oprească întotdeauna. Așa că cineva mă întreabă, pot explica afirmația că, dacă eroarea se oprește, atunci rezultă același rezultat? Vreau să spun doar că în acel slide anterior, sau în două diapozitive înapoi, dacă R acceptă, oprește și acceptă, atunci ne vom opri și accepta. Și dacă R se oprește și respinge, atunci ne oprim și respingem. Deci nu știu dacă aceasta este o idee bună, dar o putem retrage aici. Deci asta a fost afirmația aici. Dacă se oprește și scoate același rezultat, vreau să spun doar că S va face același lucru. Știi, traducem o problemă A într-o problemă B și apoi răspundem la problema B. Și vom da aceeași valoare, același răspuns acolo. Deci orice ar spune R, vom spune și noi, dacă asta este de ajutor, în regulă. Băiete, aceasta este o întrebare bună aici. Dacă A este reductibil la B, de ce nu putem obține B reductibil la A inversând funcția? E o întrebare grozavă. Îmi place întrebarea asta. Motivul este că funcția care se mapează pe B nu trebuie să fie pe, subiectiv cred. Deci, dacă ar fi fost pe, deci dacă ar acoperi tot B, atunci cred că atunci ai obține o funcție inversabilă. Și ați obține reducerea și în sens invers. Dar totuși, nu sunt sigur ce se întâmplă când ai. Nu contează dacă ai ciocniri. Se pare că asta nu va conta. Dar oricum, să nu ne complicăm prea mult aici. Dar problema cu inversarea lui este că nu este neapărat pe întreaga gamă a lui B. Așa că nu avem timp aici. Este A reductibil la A compliment? Lasă-mă să mă ocup de asta. Nu, nu neapărat. Este reductibil. A este reductibil la A complement, dar nu mapare reductibil la A compliment. Dar A este general reductibil la A compliment. Deci, de fapt, vom vorbi. Am un slide despre asta. Deci hai să mergem mai departe, ok? Cartografierea Cred că este de fapt această linie, cartografiere versus reductibilitatea generală. Așa că o să o contrastăm puțin. Deci cartografierea reductibilității, despre care tocmai am vorbit, are această imagine, care este, cred, o imagine foarte utilă de reținut. Și pentru că îmi place să mă gândesc la o reducere de cartografiere ca la un traducător de probleme. Problema ta este oarecum în domeniul A. Iar reducerea cartografierii vă permite să traduceți acea problemă în domeniul B. OK, și atunci dacă aveți o modalitate de a o rezolva în domeniul B, combinând asta cu reducerea, obțineți o soluție la problema în domeniul A. Deci, de aceea, dacă A este maparea reductibilă la B și B este rezolvabil, atunci A este și rezolvabil. Deci, reducerea cartografierii este un tip special de reductibilitate, spre deosebire de noțiunea generală de reductibilitate generală de unde am început. Și este deosebit de util să dovedești nerecunoscutul lui Turing. Deci, când doriți să dovediți nerecunoașterea lui Turing, așa cum vom vedea, reducția generală nu este suficient de bună într-un fel, nu diferențiază lucrurile la fel de bine ca reducbilitatea cartografierii. Și din acest motiv, nu va fi întotdeauna util să dovedești nerecunoscutul lui Turing. Este mai bine pentru a dovedi indecizia. Deci ceea ce numim reductibilitate sau reductibilitate generală este cazul în care folosim doar un solvent pentru B pentru a rezolva A într-un fel cât mai general posibil. Așa că scriu asta ca imagine aici. Dacă doriți să rezolvați A, veți folosi solutorul B ca subrutină pentru a rezolva A. Așa am făcut reducerea HALT TM la început. Dar nu am tradus neapărat o problemă ATM într-o problemă HALT TM. Este puțin diferit. Deci te poți întoarce și te uiți la asta. Așa că constat că oamenii se luptă mai mult cu conceptul de reducere a cartografierii. Și că reducția generală este ceea ce oamenii gravitează în mod natural. Și astfel, într-un anumit sens, este conceptual mai simplu. Și este util pentru a dovedi indecizia. Dar chiar trebuie să fii confortabil cu ambele. Și mai ales în partea de complexitate, ne vom concentra pe cartografierea reductibilității. Deci, o diferență demnă de remarcată aici, așa cum a fost prefigurată de persoana care a pus această întrebare, ceea ce este o întrebare bună, este că A se poate reduce folosind o reducere generală la A compliment, ceea ce are sens. Adică, dacă pot testa dacă lucrurile sunt în A compliment, ei bine, pot testa dacă lucrurile sunt în A. Doar inversați răspunsul. Dar A nu poate fi mapare reductibilă la A compliment pentru că există un tip foarte special de reducere. Și trebuie doar să traduci lucruri din limbă în lucruri din limbă și lucruri din afara limbii în lucruri din afara limbii. Și nu vă permit neapărat să faceți acea inversare. Deci, de exemplu, un complement TM nu este mapare reductibilă la A TM. Pentru că, așa cum am subliniat, orice se poate reduce la o limbă recunoscută va fi recunoscut. Orice mapare care se poate reduce la o limbă de recunoscut va fi recunoscut. Dar știm că complementul ATM nu este de recunoscut. Am arătat asta înainte. Deci nu ar putea fi mapare reductibilă la ATM. Vine puțin repede îmi dau seama. Va trebui să-l digerați. Deci iată ultimul check-in pentru azi. OK, am arătat că dacă A este maparea reductibilă la B și B este Turing recognoscibil, atunci la fel și A. Și, deci, să spunem asta din nou cu atenție. Dacă A este maparea reductibilă la B și B este Turing recognoscibil, atunci la fel este și A. Și iată accentul pus pe Turing recunoscut spre deosebire de decidebil. Este același lucru dacă folosim reductibilitatea generală în loc de cartografierea reductibilității? Deci ai inteles? Deci spunem că A este maparea reductibilă la B folosind această imagine de aici. Și vom presupune că B este Turing ușor de recunoscut, astfel încât să avem o mașină care oprește și acceptă atunci când ești în interiorul B și, știi, va respinge eventual o buclă atunci când nu ești în interiorul B. Acum , care vă permite să obțineți un dispozitiv de recunoaștere pentru A dacă aveți o reducere de cartografiere. Funcționează întotdeauna să vă ofere un dispozitiv de recunoaștere dacă aveți doar o reducere generală? Dacă ai acum, presupunând că ai un rezolvator B și vei construi un rezolvator A din asta. OK, gândiți-vă la asta în timp ce pun la punct chestia asta. Ei bine, răspunsul corect este câștigarea, dar nu cu mult. Presupun că nu ar trebui să râd despre asta. Dar știam că asta va fi o provocare. Deci cred că este genul de lucru la care va trebui să lucrezi. Deci, să vedem că aproape am terminat, mai sunt 5 secunde. Mai bine răspundeți la asta, vă văd pe câțiva, fie că ați părăsit camera, fie sunteți... OK, 2 secunde, 1, 2, 3. Cineva nu a răspuns. Iată-ne. Deci răspunsul corect este B. Nu este același lucru. Motivul este că, în general, vreau să spun, imaginea este chiar aici. Să vedem, cum explic asta? Deci știm că o limbă va fi... OK, dacă folosim dizabilitate generală și A este doar reductibil la B, știm că o limbă este întotdeauna reductibilă la complementul său în utilizarea reductibilității generale. Deci, dacă acest lucru ar fi adevărat, atunci am avea aici deci dacă acest lucru ar fi adevărat, când o limbă este reductibilă la complementul său, dacă complementul ar fi recognoscibil, limbajul ar fi și el recognoscibil. În mod clar, acest lucru nu va fi cazul, deoarece știți, complementul ATM este reductibil la ATM folosind reductibilitatea generală. Dar un complement TM nu este recunoscut chiar dacă A TM este recognoscibil. Deci avem o dovadă că trebuie să fie nu. Dar, după cum puteți vedea, chiar devin confuz. Deci trebuie să te uiți la el. Așa că lasă-mă să văd, putem încerca să răspundem la câteva întrebări, să vedem dacă pot lămuri confuzia oamenilor. Deci, de ce, din nou, este A reductibil la complementul său în sensul general? Așa că spun, dacă ai un rezolutor, dacă ai un decident pentru A compliment, îți dă un rezolvator pentru A. Îl întrebi pe rezolvator, șirul este în limbaj sau nu? Și acum dai doar răspunsul opus dacă vrei să rezolvi problema complementară. Deci, complementul A este general reductibil la A. Doar inversați răspunsul pentru orice face rezolvatorul pentru A. Dar nu puteți face doar acea inversare atunci când aveți o reducere de cartografiere. Este permisă o traducere mult mai specifică . Adică, diferența fundamentală dintre reductibilitatea generală și reductibilitatea cartografierii, încerc să o scot aici. Este doar o diferență în natura modului în care sunt folosite lucrurile. Reductibilitatea cartografierii este un tip special de reductibilitate generală. Deci, pentru a răspunde la întrebarea despre care este diferența fundamentală, cineva folosește problema ca subrutină și o folosește ca transformare. Oricum, cred că va trebui să trecem mai departe aici. Și voi avea câteva exemple care ar putea ajuta. Și apoi, sunt și ore de birou după prelegere. Bine, oh, da, așa că am vrut din nou să te ajut. Le pun pe acestea ca un fel de șabloane pentru cum folosiți reductibilitatea. Nu spun că ar trebui să aplici lucrurile orbește. Dar cred că uneori este bine doar să vezi modelul și apoi să înțelegi cum funcționează modelul. Deci, odată ce începi să înțelegi tiparul modului în care sunt folosite lucrurile. Deci pentru a arăta că o limbă este indecidabilă, pentru a demonstra că o limbă B este indecidabilă, arătați limbi indecidabile reductibile la B. Folosirea doar a unei reduceri generale va fi suficient de bună. Și șablonul pentru asta este să presupunem că avem R care decide B, pe care apoi îl puteți folosi ca subrutină atunci când faceți o mașină Turing S care decide A. Și asta va fi contradicția voastră. Dacă inițial s-a dovedit că A este cunoscut ca fiind indecidabil. Dar acum, pentru a dovedi ceva de nerecunoscut, acest tip de reducere nu este suficient de restrictiv, deoarece acest tip de reducere permite o completare care nu va fi satisfăcătoare atunci când încercați să dovediți că Turing este de nerecunoscut. Deci va trebui să interziceți completarea. Și acesta este într-adevăr unul dintre efectele reductibilității mapării dacă acest tip de ajunge la esența acesteia. Așa că veți arăta o nerecunoscută a unui A recognoscibil care este maparea reductibilă la B. Adesea, începeți cu complementul A TM, care este o limbă despre care știm că Turing este de nerecunoscut, așa cum am arătat mai înainte, OK, aici este șablonul. dați funcția de reducere f, acea funcție calculabilă, OK. Așadar, aici vor fi două exemple, unul care arată că E TM este Turing de nerecunoscut. Am arătat că este indecidabil înainte. Acum vom arăta că este chiar într-un fel mai rău. Nici măcar nu este de recunoscut. Și modul în care vom face asta este să reducem un limbaj cunoscut de nerecunoscut la E TM în limbajul gol. Deci, iată imaginea pe care o avem când facem reduceri de cartografiere. Vom mapa șiruri care sunt în complementul ATM, deci șiruri care sunt în afara ATM dacă doriți să șiruri în care limbajul este gol la mașini în care limbajul este gol. Și aici sunt șiruri de caractere care descriu mașini în care limbajul este gol. Și aici vom lua problemele ATM și le vom mapa pe mașini în care limbajul nu este gol. Și lucrul care va face truc va fi aceeași funcție de reducere pe care am văzut-o mai devreme. Vom lua acea mașină w de înainte, mașina care filtrează toate non-w-urile. Și o să luăm Mw, care este o problemă de compliment ATM . Deci, dacă M respinge w că este în complementul A TM și ar trebui să se mapeze la un șir, o mașină în care limbajul este gol, OK. Deci, dacă Mw este în complementul lui A TM, deci M respinge w, atunci limbajul lui Mw va fi gol, ceea ce doriți să se întâmple. Lasă-mă să trec la ultimul. Adică, acest exemplu este într-un fel similar cu cel pe care l-am făcut înainte. Și chiar vreau să ajung la ultimul exemplu aici. OK, așa că va trebui să vorbim despre asta, în loc să-l construim. Să luăm EQ TM. Aceasta este problema echivalenței pentru mașinile Turing. Recunosc ei aceeași limbă? Deci aceasta este o limbă de un tip nou pentru noi. Aceasta este o limbă în care nici ea, nici complementul său nu vor fi de recunoscut, Turing, de recunoscut. Așadar, modul în care obținem acest lucru este că modul în care arătăm că problemele nu sunt recunoscute este maparea reducerii unui limbaj nerecunoscut la complementul de obicei ATM. Deci, vom mapa reduce complementul A TM atât la EQ TM cât și la complementul EQ TM pentru a arăta că ambele nu sunt recunoscute. Și aici vom introduce o nouă mașină pe care o vom construi în cadrul funcției de reducere. Și asta va fi o mașină pe care o voi numi Tw. Și Tw este o mașină care se comportă întotdeauna așa cum se comportă M pe w pentru fiecare intrare. Deci, dacă M acceptă w, T va accepta totul. Dacă M respinge w, T va respinge totul. Deci, copiază comportamentul lui M pe w pe toate intrările. Și modul în care descriu acea mașină Tw este că îi ignoră intrarea. Oricare ar fi intrarea, doar simulează M pe w. Ai putea da cu ușurință un M și w, poți construi mașina Tw. Pur și simplu rulează întotdeauna M pe w, indiferent de intrarea pe care o primește. Și acum vom oferi o funcție care mapează problemele ATM care au forma Mw. Deci este o problemă de compliment ATM. Deci, acest lucru vrea să testeze dacă M acceptă w sau nu. Deci, aceasta este o problemă de tip compliment ATM. Și vreau să mapez asta la o problemă EQ TM cu formularul -- știi, problemele EQ TM repară mașina acum și unde se va testa echivalența. Deci încerc doar să vă dau forma rezultatului funcției de reducere f. Și mai precis, ceea ce va arăta este că atunci când avem f se procesează pe Mw, va produce două mașini. Unul dintre ele va fi Tw care se comportă întotdeauna în felul în care M se comportă pe w, dar extins la toate intrările, și apoi o mașină pe care o voi numi T reject, care este concepută doar să respingă totul. Acum, parcurgeți logica cu mine. Dacă M respinge w, Tw respinge totul. Și astfel vom fi echivalent cu mașina T respinge. Asta ne dorim. Dacă M respinge w, deci suntem în limbajul ATM compliment, atunci aceste două mașini pe care le produc pentru tine vor fi în linia EQ TM. Asta vreau să se întâmple pentru o reducere de la compliment ATM la EQ TM. În mod similar, pentru a face partea 2, voi face aici un f diferit, poate ar trebui să-l numesc f prim, bine, f1 și f2 pentru cele două părți diferite. Deci acestea sunt două f-uri diferite. O să fac f aici. În loc să generez Tw și T respingere, voi avea Tw și T să accepte, care este o mașină Turing care își acceptă întotdeauna intrarea. Acum, dacă M respinge w, este în compliment ATM, atunci Tw va respinge totul. Și va fi diferit de însoțitorul său de aici, accept. Și așa nu va fi în compliment EQ TM. Dar dacă M acceptă w, atunci Tw va accepta totul. Și va fi echivalent cu T accept. Și vei fi echivalent. Deci aici este locul în care luăm complimentul ATM și îl mapam cu complimentul, EQ TM. Prea multe complimente aici îmi dau seama. Complimentele sunt confuze. Dar oricum, de ce nu te gândești la asta. Și doar pentru a rezuma, OK, nu avem timp aici. Dar de ce folosim reducerea când vorbim despre reduceri? Pentru că atunci când reducem A la B, coborâm într-un fel dificultatea lui A la dificultatea lui B, de aici vine reducerea. Sau aducem dificultatea lui B la dificultatea lui A, pentru că într-adevăr este dificultatea lui A în raport cu B despre care vorbim atunci când reducem A la B. Deci, de aceea, termenul de reducere pare puțin deplasat atunci când dovedim lucruri indecidabile sau de nerecunoscut. Dar de aici vine. Oricum, trecere rapidă în revistă, am introdus metoda reductibilității. Am definit reductibilitatea cartografierii ca un tip special de reductibilitate. Am arătat E TM ca fiind indecidabil și de nerecunoscut. Și acel EQ TM este atât, cât și complementul său sunt de nerecunoscut. Deci nu avem timp. O să închid asta. Dar voi răspunde aici de fapt câteva întrebări. Voi rămâne pentru câteva întrebări. Și apoi mă voi muta în cealaltă cameră de chat pentru orele de birou, bine? Deci întrebare, treceți peste cazul pentru complementul EQ TM. Deci voi face asta. Deci asta este în acest slide aici. OK, deci aceasta este partea a 2-a dovadă pentru persoana care mi-a cerut să trec peste ea. Dar cred că este util pentru cei dintre voi care ar putea fi puțin șovăitori în privința asta. Vreau să reduc complementul A TM la complementul EQ TM. Apropo, nu știu dacă acest lucru va fi de ajutor. Dar, așa cum am subliniat în verificare cu ceva timp în urmă, aceasta este complet echivalentă cu o reducere a mapării de la ATM la EQ TM. Puteți completa ambele părți și obțineți o declarație echivalentă. Poate să rămânem cu complimentele aici, totuși. Sper că asta nu face prea confuz, OK. Încercăm să arătăm că complementul A TM este maparea reductibilă la complementul EQ TM. Ce înseamnă asta? Asta înseamnă că atunci când M respinge w, așa că ești în compliment, vrem ca cele două mașini Turing să fie inechivalente. Nu, da, deci suntem în complimentul EQ TM. Deci, cu alte cuvinte, când suntem în complementul lui A TM, dorim ca rezultatul lui f să fie în complementul lui EQ TM. Deci, cu alte cuvinte, când M respinge w, cele două mașini ar trebui să fie inechivalente. Dreapta? Când M acceptă w, cele două mașini ar trebui să fie echivalente. Pentru că atunci când nu suntem în această limbă, deci suntem în ATM, vrem să nu fim în limba respectivă. Deci ar trebui să fim în EQ TM. Deci, când M acceptă w, ar trebui să fim echivalenti. Când M respinge w, ar trebui să fim inechivalenți. Asta ne dorim. Să coborâm aici. Deci, dacă M acceptă w, vrem ca ele să-- deci atunci când M acceptă w, vrem ca acestea să fie echivalente. Deci, dacă M acceptă w, Tw acceptă totul. Și este echivalent cu T accept. Când M respinge w, Tw respinge totul. Și deci nu este echivalent cu mașina care acceptă totul. Așa că parcurgeți singur logica. Vei vedea de ce funcționează. Bine, deci, pa , pa, tuturor.