O introducere în teoria și complexitatea calculabilității

V-ați întrebat vreodată: care este exact dispozitivul pe care citiți acest articol? Ce e un calculator?

Știința computațională datează cu mult înainte ca aceste dispozitive de calcul moderne să fie chiar imaginate. Într-o industrie în care întrebările cele mai frecvent adresate gravitează în jurul limbajelor de programare, cadrelor și bibliotecilor, am luat deseori de la sine înțeles conceptele fundamentale care fac ca un computer să funcționeze.

Dar aceste computere, care par să posede un potențial nesfârșit, au ele vreo limită? Există probleme pentru care computerele nu pot fi rezolvate?

În acest articol, vom aborda aceste întrebări, renunțând la detaliile limbajelor de programare și arhitecturii computerelor. Înțelegând puterea și limitările computerelor și algoritmilor, putem îmbunătăți modul în care gândim și putem raționa mai bine despre diferite strategii.

Viziunea abstractă a calculatoarelor produce rezultate care au rezistat testului timpului, fiind la fel de valoroase pentru noi astăzi precum au fost atunci când au fost dezvoltate inițial în anii 1970.

Calculabilitate

Ce e un calculator? Ce este o problemă?

În școală, ni se învață adesea un model mental al problemelor și funcțiilor care arată cam așa:

O funcție este o procedură pe care o aplicați unei intrări x pentru a găsi o ieșire f(x).

Se pare că definiția matematică este diferită:

O funcție este un set de perechi ordonate astfel încât primul element al fiecărei perechi este dintr-o mulțime X (numit domeniu), al doilea element al fiecărei perechi este dintr-o mulțime Y (numit codomeniu sau interval) și fiecare element al domeniul este asociat cu exact un element al gamei.

Asta a fost destul de gura. Dar, ce înseamnă mai exact asta?

Această definiție ne spune că un computer este o mașină pentru calcularea funcțiilor.

De ce?

Deoarece computerele transformă intrarea arbitrară într-o ieșire. Cu alte cuvinte, ele rezolvă probleme. Cele două definiții ale funcțiilor, cea cu care suntem atât de familiari și cea formală, coincid în multe scopuri practice.

Cu toate acestea, definiția matematică ne permite să ajungem la concluzii interesante, cum ar fi existența unor funcții necalculabile (adică, probleme de nerezolvat):

Deoarece, nu orice funcție poate fi descrisă ca un algoritm.

Regulile jocului

Pentru a ne ajuta să ne argumentăm, să ne imaginăm computerele ca pe niște mașini care iau o anumită intrare, efectuează o secvență de operații și, după un timp, dă rezultate.

Vom numi intrarea alfabetul mașinii; adică un set de șiruri de caractere dintr-o mulțime finită. De exemplu, alfabetul mașinii poate fi binar (0 și 1) sau poate fi setul de caractere ASCII. Orice succesiune finită de caractere este un șir, de exemplu, „0110”.

Mai mult, vom reprezenta ieșirea unei mașini ca o decizie binară de acceptare-respingere, livrată odată ce mașina (sperăm) își termină calculul. Această abstractizare se potrivește bine cu definiția matematică a funcțiilor de mai devreme.

Având în vedere acești parametri, este important să se caracterizeze încă un tip: o colecție de șiruri. Poate ne pasă de setul de șiruri pe care le acceptă unele mașini, sau poate construim o mașină care acceptă șiruri într-un anumit set și nu altele, sau poate ne întrebăm dacă este chiar posibil să proiectăm o mașină care acceptă totul într-un anumit set. un anumit set și nu altele.

În toate aceste cazuri, un set de șiruri se numește limbaj - de exemplu, setul tuturor șirurilor binare care reprezintă numere pare sau setul de șiruri care au un număr par de caractere. Se pare că limbile, precum numerele, pot fi operate cu operatori precum concatenare, unire, intersecție și altele asemenea.

Un operator important este operatorul stea Kleene, care este folosit și cu expresiile regulate. Aceasta poate fi considerată ca unirea tuturor puterilor posibile ale limbii. De exemplu, dacă limba noastră A este setul de șiruri { '01', '1' }, atunci un membru al lui A* este șirul '0101111'.

Numărabilitatea

Ultima piesă a puzzle-ului înainte de a demonstra afirmația noastră că nu toate funcțiile sunt calculabile este conceptul de numărabilitate. Intuitiv, dovada noastră va arăta că există mai multe limbi; adică mai multe probleme decât există programe posibile care să le rezolve. Acest lucru funcționează deoarece întrebarea dacă un șir aparține unei limbi (Da/Nu) este în sine o problemă.

Mai precis, dovada noastră susține că setul de programe posibile este infinit infinit, în timp ce setul de limbi peste un alfabet este infinit infinit.

În acest moment, s-ar putea să vă gândiți: „Infinitul este o idee destul de ciudată în sine; acum trebuie să mă ocup de doi dintre ei!”

Ei bine, nu e chiar atât de rău. Un set numărabil infinit este unul care poate fi enumerat. Este posibil să spunem că acesta este primul element, acesta este al doilea element și așa mai departe, în cele din urmă atribuind un număr fiecărui element al mulțimii. Luați setul de numere pare, de exemplu. Putem spune că 2 este primul, 4 al doilea, 6 al treilea și așa mai departe. Astfel de mulțimi sunt numărabile infinite sau numărabile.

Cu unele seturi, totuși, cum ar fi numerele reale, nu contează cât de inteligent ești; pur și simplu nu există enumerare. Aceste seturi sunt infinit infinit sau nenumărabil.

Numărabil de multe programe

În primul rând, dorim să arătăm că setul de programe de calculator este numărabil. Pentru scopurile noastre, facem acest lucru observând că mulțimea tuturor șirurilor dintr-un alfabet finit este numărabilă. Acest lucru funcționează deoarece programele de calculator sunt ele însele șiruri finite.

Dovada este simplă și nu acoperim detaliile aici. Principala concluzie este că există tot atâtea programe de calculator câte numere naturale există, să zicem.

A reitera:

Setul de șiruri de caractere peste orice alfabet (de exemplu, setul tuturor programelor de calculator) este numărabil.

Nenumărate multe limbi

Având în vedere această concluzie, cum rămâne cu submulțimile acestor șiruri? Întrebat în alt mod, cum rămâne cu setul de toate limbile? Se pare că acest set este de nenumărat.

Setul tuturor limbilor de pe orice alfabet este de nenumărat.

Încă o dată, nu acoperim dovada aici.

Consecințe

Deși s-ar putea să nu fie imediat evidente, consecințele nenumărabilității limbilor și numărabilității setului tuturor programelor de calculator sunt profunde.

De ce?

Să presupunem că A este setul de caractere ASCII; Caracterele ASCII sunt doar cele necesare pentru a compune un program de calculator. Putem vedea că setul de șiruri de caractere care reprezintă, de exemplu, programe JavaScript, este un submult al lui A* (aici, * este operatorul stea Kleene). Alegerea JavaScript este arbitrară. Deoarece acest set de programe este un subset al unui set numărabil, avem că setul de programe JavaScript este numărabil.

În plus, să considerăm că pentru orice limbaj L , putem defini o funcție f care evaluează la 1 dacă un șir x este în L și 0 în caz contrar. Toate aceste funcții sunt distincte. Deoarece există o corespondență 1:1 cu setul tuturor limbilor și deoarece setul tuturor limbilor este nenumărabil, avem că setul tuturor acestor funcții este nenumărabil.

Iată punctul profund:

Deoarece setul tuturor programelor valide este numărabil, dar setul de funcții nu este, atunci trebuie să existe unele funcții pentru care pur și simplu nu putem scrie programe.

Încă nu știm cum arată aceste funcții sau probleme, dar știm că există. Aceasta este o realizare umilitoare, pentru că există unele probleme pentru care nu există nicio soluție. Considerăm că computerele sunt extrem de puternice și capabile, dar unele lucruri nu sunt chiar la îndemâna lor.

Acum întrebarea devine: „Cum arată aceste probleme?” Înainte de a continua să descriem astfel de probleme, trebuie să modelăm calculul într-un mod generalizat.

Mașini Turing

Unul dintre primele modele matematice ale unui computer a fost dezvoltat de Alan Turing. Acest model, numit mașina Turing, este un dispozitiv extrem de simplu care surprinde complet noțiunea noastră de calculabilitate.

Intrarea în mașină este o bandă pe care a fost scrisă intrarea. Folosind un cap de citire/scriere, aparatul transformă intrarea în ieșire printr-o serie de pași. La fiecare pas, se ia decizia dacă și ce să scrie pe bandă și dacă să o muți la dreapta sau la stânga. Această decizie se bazează pe exact două lucruri:

• Simbolul curent sub cap și

• Starea internă a mașinii, care este, de asemenea, actualizată pe măsură ce este scris simbolul

Asta e.

Universalitate

În 1926, Alan Turing nu numai că a dezvoltat mașina Turing, dar a avut și o serie de alte perspective majore asupra naturii calculului când a scris faimoasa sa lucrare, „Despre numerele calculabile”. Și-a dat seama că un program de calculator în sine ar putea fi considerat intrare într-un computer. Din acest punct de vedere, a avut ideea frumoasă că o mașină Turing ar putea simula sau executa acea intrare.

În timp ce luăm aceste idei de la sine înțeles astăzi, pe vremea lui Turing, ideea unei astfel de mașini universale a fost descoperirea majoră care i-a permis lui Turing să dezvolte probleme de nerezolvat.

Teza Church-Turing

Înainte de a continua, să examinăm un punct important: știm că mașina Turing este un model de calcul, dar este suficient de general? Pentru a răspunde la această întrebare, ne întoarcem la teza Church-Turing, care dă credibilitate următoarei afirmații:

Tot ce poate fi calculat este calculat de o mașină Turing.

În timp ce Turing a dezvoltat mașina Turing ca model de calcul, Alonzo Church a dezvoltat și un model de calcul cunoscut sub numele de calcul lambda. Aceste modele sunt puternice, deoarece ambele descriu calculul și fac acest lucru într-un mod egal cu oricare dintre computerele de astăzi sau, de altfel, orice computer vreodată. Aceasta înseamnă că putem folosi o mașină Turing pentru a descrie problemele de nerezolvat pe care le căutăm, știind că descoperirile noastre s-ar aplica tuturor computerelor posibile din trecut, prezent și dincolo.

Recunoaștere și decidebilitate

Trebuie să acoperim un pic mai mult context înainte de a descrie în mod concret o problemă de nerezolvat, și anume conceptele de recunoaștere a limbii și factori de decizie de limbă.

O limbă este recunoscută dacă există o mașină Turing care o recunoaște.

și

O limbă este decidabilă dacă există o mașină Turing care o decide.

Pentru a recunoaște o limbă, o mașină Turing trebuie să accepte fiecare șir din limbă și nu trebuie să accepte nimic care nu este în limbă. Poate respinge sau bucla astfel de șiruri. Pentru a fi un decident, o mașină Turing trebuie să se oprească întotdeauna la intrarea sa fie acceptând, fie respingând.

Aici, ideea de a opri intrarea este critică. De fapt, vedem că decidenții sunt mai puternici decât cei care recunosc. Mai mult, o problemă este rezolvabilă, sau altfel spus, o funcție este decidabilă numai dacă există o mașină Turing care decide limbajul descris de funcție.

Indecidibilitate

Dacă ați scris vreodată un program de calculator, cu siguranță trebuie să cunoașteți senzația de a sta acolo doar privind cum computerul își învârte roțile când programul este executat. Nu știi dacă programul durează doar mult timp sau dacă există o greșeală în cod care provoacă o buclă infinită. Poate v-ați întrebat chiar de ce compilatorul nu verifică codul pentru a vedea dacă acesta s-ar opri sau s-ar bucla pentru totdeauna atunci când este rulat.

Compilatorul nu are o astfel de verificare deoarece pur și simplu nu se poate face. Nu este că inginerii de compilare nu sunt suficient de inteligenți sau nu au resurse; este pur și simplu imposibil să verifici un program de calculator arbitrar pentru a determina dacă se oprește.

Putem demonstra acest lucru folosind mașina Turing. Mașinile Turing pot fi descrise ca șiruri, deci există un număr numărabil de ele. Să presupunem că M ₁ , M ₂ și așa mai departe alcătuiesc mulțimea tuturor mașinilor Turing. Să definim următoarea funcție:

Aici, <M> este sintaxa pentru „codificarea șirului de caractere a lui M”, iar această funcție reprezintă problema de ieșire a 1 dacă M _i se oprește acceptând M _j ca intrare și ieșind 0 în caz contrar. Rețineți că M _i trebuie să se oprească (adică să fie un decident). Acest lucru este necesar deoarece dorim să descriem o funcție indecidabilă (adică o problemă de nerezolvat).

Acum, să definim și un limbaj L care constă din codificări de șiruri ale mașinilor Turing care NU acceptă propriile descrieri:

De exemplu, o mașină _M1 poate scoate 0 pe intrarea < _M1 > în timp ce o altă mașină M2 poate scoate ₁ pe intrarea <M2 _> . Pentru a demonstra că acest limbaj este indecidibil, întrebăm ce face M _L , mașina care decide limbajul L, când i se dă propria sa descriere <M _L > ca intrare. Există două posibilități:

M _L acceptă <M _L >

sau

M _L respinge <M _L >

Dacă ML acceptă propria sa codificare, atunci aceasta înseamnă că < _{M L >} nu este în limbajul L; totuși, dacă acesta ar fi fost cazul, atunci _ML nu ar fi trebuit să accepte codificarea sa în primul rând. Pe de altă parte, dacă M _L nu acceptă propria sa codificare, atunci <M _L > este în limbajul L, deci M _L ar fi trebuit să accepte codificarea șirurilor sale.

În ambele cazuri, avem un paradox, sau în termeni matematici, o contradicție, care demonstrează că limbajul L este indecidibil; astfel, am descris prima noastră problemă de nerezolvat.

Problemă de oprire

Deși problema pe care tocmai am descris-o poate să nu pară relevantă, ea poate fi redusă la probleme suplimentare de importanță practică, de nerezolvat, în special problema opririi:

Limbajul codificărilor mașinilor Turing care se opresc pe șirul gol.

Problema opririi se aplică la întrebarea de ce compilatoarele nu pot detecta bucle infinite de mai devreme. Dacă nu putem determina dacă un program se termină pe șirul gol, atunci cum am putea determina dacă execuția lui ar avea ca rezultat o buclă infinită?

În acest moment, s-ar putea părea că doar ne-am agitat mâinile pentru a ajunge la o concluzie simplă; cu toate acestea, ne-am dat seama că nicio mașină Turing nu poate spune dacă un program de calculator se va opri sau rămâne într-o buclă pentru totdeauna. Aceasta este o problemă importantă cu aplicațiile practice și nu poate fi rezolvată pe o mașină Turing sau pe orice alt tip de computer. Un iPhone nu poate rezolva această problemă. Un desktop cu multe nuclee nu poate rezolva această problemă. Cloud-ul nu poate rezolva această problemă. Chiar dacă cineva ar inventa un computer cuantic, acesta tot nu ar fi capabil să rezolve problema opririi.

rezumat

În examinarea noastră a teoriei computabilității, am văzut cum există multe funcții care nu sunt calculabile în niciun sens obișnuit al cuvântului printr-un argument de numărare. Am definit exact ce înțelegem prin calcul, mergând până la inspirația lui Turing din propria experiență cu pixul și hârtia pentru a oficializa mașina Turing. Am văzut cum acest model poate calcula orice poate calcula orice computer de astăzi sau imaginat pentru mâine și am realizat o clasă de probleme care nu sunt deloc calculabile.

Totuși, calculabilitatea are un dezavantaj. Doar pentru că putem rezolva o problemă nu înseamnă că o putem rezolva rapid. La urma urmei, la ce folosește un computer dacă calculul său nu se va termina înainte ca soarele să devină nova pe noi zeci de milioane de ani în viitor?

Lăsând în urmă funcțiile și limbaje calculabile, discutăm acum despre complexitatea calculului, analizând calculul eficient și celebra problemă P vs. NP.

Complexitate

Încet vs. Rapid

Informaticii recunosc o varietate de clase de probleme, iar două clase de care ne pasă includ probleme pe care computerele le pot rezolva rapid sau eficient cunoscute sub numele de P și probleme ale căror soluții pot fi verificate rapid, dar nu pot fi obținute rapid cunoscute sub numele de NP .

De exemplu, să presupunem că sunteți responsabil pentru dezvoltarea algoritmilor pentru un serviciu de întâlniri online și cineva pune întrebarea: „Toată lumea poate obține o întâlnire?” Răspunsul se rezumă la împerecherea persoanelor compatibili, astfel încât toată lumea să fie asociată. Se pare că există algoritmi eficienți pentru rezolvarea acestei probleme. Această problemă este în mulțimea P .

Ei bine, ce se întâmplă dacă am dori să identificăm cea mai mare clică dintre utilizatorii noștri? Prin clică, înțelegem cea mai mare rețea de indivizi care sunt toți compatibili unul cu celălalt. Când numărul de utilizatori este scăzut, această problemă poate fi rezolvată rapid. Putem identifica cu ușurință, să zicem, o clică cu 3 utilizatori. Pe măsură ce începem să căutăm clicuri mai mari, însă, problema devine din ce în ce mai greu de rezolvat. Această problemă este în mulțimea NP .

Definiții formale

P este mulțimea de probleme care sunt rezolvabile în timp polinomial. Adică, numărul de pași de calcul este mărginit de o funcție polinomială în raport cu dimensiunea problemei. Știm că „Toată lumea poate obține o întâlnire?” întrebarea, cunoscută și ca problemă de potrivire bipartită, este în P .

NP este setul de probleme care sunt verificabile în timp polinomial. Aceasta include fiecare problemă din P, desigur; totuși, nu știm dacă această izolare este strictă. Cunoaștem probleme care sunt eficient verificabile, dar nu pot fi rezolvate eficient, dar nu știm dacă problema este cu adevărat insolubilă. Problema clicei este o astfel de problemă. Știm că putem verifica eficient soluția, dar nu știm sigur dacă putem rezolva problema eficient.

În cele din urmă, NP-complet este setul de probleme care sunt cele mai dificile probleme din NP . Ele sunt considerate cele mai grele deoarece orice problemă din NP poate fi transformată eficient în NPC . Ca rezultat, dacă cineva ar identifica o soluție eficientă pentru o problemă în NPC , atunci întreaga clasă de NP ar fi absorbită de P . Problema clicei este și în NPC .

Astfel, ajungem la problema lui P vs. NP . Mulți informaticieni și matematicieni cred cu tărie că P și NP nu sunt egale. Dacă ar fi, implicațiile ar fi dincolo de profunde. O mare parte din infrastructura digitală de astăzi se bazează pe faptul că există probleme în NP care nu sunt în P . Dacă nu ar fi așa, atunci metodele criptografice, de exemplu, s-ar prăbuși peste noapte, permițând unei persoane care deține o soluție eficientă la o problemă NPC să submineze chiar și cele mai stricte protocoale de securitate.

Subtilități de tratabilitate

Pentru începătorii în informatică, diferența dintre problemele de potrivire și de clicuri ar putea să nu pară mare lucru. De fapt, diferența dintre o problemă din P și o problemă din NP poate fi foarte subtilă. A fi capabil să facă diferența este important pentru oricine proiectează algoritmi în lumea reală.

Luați în considerare problema cu cea mai scurtă cale. Având în vedere două locații, obiectivul este de a identifica calea cea mai scurtă între ele. Un iPhone calculează acest lucru în câteva milisecunde. Aceasta este o problemă rezolvabilă din punct de vedere computațional.

Pe de altă parte, luați în considerare problema vânzătorului ambulant, în care obiectivul este de a vizita un subset de destinații posibile care se termină la origine în timp ce parcurgeți cea mai scurtă distanță posibilă. Această problemă este similară cu cea mai scurtă problemă, dar este NP-complet; de asemenea, explică de ce logistica lanțului de aprovizionare este o industrie de un miliard de dolari.

Putem fi de fapt și mai subtili. În loc să cerem calea cea mai scurtă (P), putem cere cea mai lungă cale fără cicluri. Se pare că problema cu cea mai lungă cale este, de asemenea, NP-completă.

Există mai multe exemple de această distincție subtilă, inclusiv identificarea acoperirilor de vârfuri în grafice bipartite vs. generale sau satisfacerea formulelor booleene cu doi vs. trei literali per clauză. Ideea este că nu este imediat evident dacă o problemă este în P sau NP și de aceea analiza timpului de rulare este o abilitate critică. Dacă algoritmul care trebuie proiectat este pentru o problemă din P, atunci știm că există o soluție eficientă. Dacă, pe de altă parte, problema este în NP, atunci avem un argument puternic împotriva urmăririi unei soluții, deoarece algoritmul, în general, ar dura prea mult pentru a rezolva problema.

rezumat

În această examinare a complexității, am definit clasele de probleme P și NP. P reprezintă în mod informal probleme care pot fi rezolvate eficient de un computer, în timp ce NP reprezintă cele care sunt verificabile eficient.

Nimeni nu a putut demonstra că P nu este egal cu NP. Dacă aceste două clase de probleme sunt echivalente este cunoscută ca problema P vs. NP, și este cea mai importantă problemă deschisă în informatica teoretică de astăzi, dacă nu în toată matematica. De fapt, în anul 2000, Clay Math Institute a numit problema P vs. NP drept una dintre cele mai importante șapte întrebări deschise din matematică și a oferit o recompensă de un milion de dolari pentru o dovadă care determină soluția acestei probleme.

Concluzie

În acest articol, am aprofundat în tărâmurile computabilității și complexității, răspunzând la întrebări mari precum „Ce este un computer?” Deși detaliile pot fi copleșitoare, există o serie de concluzii profunde care merită reținute:

• Există unele lucruri care pur și simplu nu pot fi calculate, cum ar fi problema opririi.

• Există unele lucruri care nu pot fi calculate eficient, cum ar fi problemele din NPC.

Mai importante decât detaliile sunt modalitățile de a gândi despre calcul și probleme de calcul. În viața noastră profesională și chiar în viața noastră de zi cu zi, este posibil să întâlnim probleme nemaivăzute până acum și putem folosi instrumente și tehnici încercate și adevărate pentru a determina cel mai bun curs de acțiune.

Citiți suplimentare pe blogul Toptal Engineering:

• Cum să abordați scrierea unui interpret de la zero