Un'introduzione alla teoria e alla complessità della calcolabilità

Ti sei mai chiesto: qual è esattamente il dispositivo su cui stai leggendo questo articolo? Cos'è un computer?

La scienza computazionale risale a molto tempo prima che questi moderni dispositivi informatici fossero persino immaginati. In un settore in cui le domande più frequenti ruotano attorno a linguaggi di programmazione, framework e librerie, spesso diamo per scontati i concetti fondamentali che fanno funzionare un computer.

Ma questi computer, che sembrano possedere un potenziale infinito, hanno dei limiti? Ci sono problemi che i computer non possono risolvere?

In questo articolo, affronteremo queste domande allontanandoci dai dettagli dei linguaggi di programmazione e delle architetture dei computer. Comprendendo il potere e i limiti dei computer e degli algoritmi, possiamo migliorare il modo in cui pensiamo e ragionare meglio su diverse strategie.

La visione astratta dell'informatica produce risultati che hanno resistito alla prova del tempo, essendo preziosi per noi oggi come lo erano quando furono sviluppati inizialmente negli anni '70.

Calcolabilità

Cos'è un computer? Che cos'è un problema?

A scuola, ci viene spesso insegnato un modello mentale di problemi e funzioni che assomiglia a questo:

Una funzione è una procedura che si applica a un input x per trovare un output f(x).

Si scopre che la definizione matematica è diversa:

Una funzione è un insieme di coppie ordinate tale che il primo elemento di ogni coppia provenga da un insieme X (chiamato dominio), il secondo elemento di ogni coppia provenga da un insieme Y (chiamato codominio o intervallo) e ogni elemento di il dominio è accoppiato esattamente con un elemento dell'intervallo.

Era proprio il boccone. Ma cosa significa quello esattamente?

Questa definizione ci dice che un computer è una macchina per funzioni di calcolo.

Come mai?

Perché i computer trasformano l'input arbitrario in un output. In altre parole, risolvono i problemi. Le due definizioni di funzioni, quella che ci è tanto familiare e quella formale, coincidono per molti scopi pratici.

Tuttavia, la definizione matematica permette di trarre conclusioni interessanti come l'esistenza di funzioni non calcolabili (cioè problemi irrisolvibili):

Perché non tutte le funzioni possono essere descritte come algoritmi.

Le regole del gioco

Per aiutare a sostenere le nostre argomentazioni, immaginiamo i computer come macchine che prendono input, eseguono una sequenza di operazioni e, dopo un po', forniscono output.

Chiameremo l'input alfabeto della macchina; cioè un insieme di stringhe di caratteri da un insieme finito. Ad esempio, l'alfabeto della macchina può essere binario (0 e 1) o potrebbe essere il set di caratteri ASCII. Qualsiasi sequenza finita di caratteri è una stringa, ad esempio "0110".

Inoltre, rappresenteremo l'output di una macchina come una decisione binaria di accettazione-rifiuto, consegnata una volta che la macchina (si spera) avrà terminato il suo calcolo. Questa astrazione si adatta bene alla definizione matematica delle funzioni di prima.

Dati questi parametri, è importante caratterizzare un altro tipo: una raccolta di stringhe. Forse ci interessa l'insieme di stringhe che alcune macchine accettano, o forse stiamo costruendo una macchina che accetta stringhe in un certo insieme e nessun altro, o forse ci stiamo chiedendo se è anche possibile progettare una macchina che accetti tutto in alcuni insieme particolare e non altri.

In tutti questi casi, un insieme di stringhe è chiamato lingua, ad esempio l'insieme di tutte le stringhe binarie che rappresentano numeri pari o l'insieme di stringhe che hanno un numero pari di caratteri. Si scopre che le lingue, come i numeri, possono essere utilizzate con operatori come concatenazione, unione, intersezione e simili.

Un operatore importante è l'operatore stella di Kleene, utilizzato anche con le espressioni regolari. Questo può essere pensato come l'unione di tutti i possibili poteri della lingua. Ad esempio, se la nostra lingua A è l'insieme di stringhe { '01', '1' }, un membro di A* è la stringa '0101111'.

numerabilità

L'ultimo pezzo del puzzle prima di dimostrare la nostra affermazione che non tutte le funzioni sono calcolabili è il concetto di numerabilità. Intuitivamente, la nostra dimostrazione mostrerà che ci sono più lingue; cioè, più problemi di quanti siano possibili programmi per risolverli. Questo funziona perché la domanda se una stringa appartenga a una lingua (Sì/No) è di per sé un problema.

Più precisamente, la nostra dimostrazione afferma che l'insieme dei possibili programmi è numerabilmente infinito mentre l'insieme delle lingue su un alfabeto è infinitamente infinito.

A questo punto, potresti pensare: "L'infinito è un'idea abbastanza strana di per sé; ora devo fare i conti con due di loro!”

Beh, non è così male. Un insieme numerabile infinito è un insieme che può essere enumerato. Si può dire che questo è il primo elemento, questo è il secondo elemento e così via, eventualmente assegnando un numero a ogni elemento dell'insieme. Prendi l'insieme dei numeri pari, per esempio. Possiamo dire che 2 è il primo, 4 il secondo, 6 il terzo e così via. Tali insiemi sono numerabili infiniti o numerabili.

Con alcuni set però, come i numeri reali, non importa quanto tu sia intelligente; semplicemente non c'è enumerazione. Questi insiemi sono infinitamente infiniti o non numerabili.

Numerosi programmi

Innanzitutto, vogliamo mostrare che l'insieme dei programmi per computer è numerabile. Per i nostri scopi, lo facciamo osservando che l'insieme di tutte le stringhe su un alfabeto finito è numerabile. Questo funziona perché i programmi per computer sono essi stessi stringhe finite.

La dimostrazione è semplice e qui non trattiamo i dettagli. Il punto chiave è che ci sono tanti programmi per computer là fuori quanti sono, diciamo, i numeri naturali.

Reiterare:

L'insieme di tutte le stringhe su qualsiasi alfabeto (ad esempio, l'insieme di tutti i programmi per computer) è numerabile.

Innumerevoli lingue

Data questa conclusione, che dire dei sottoinsiemi di queste stringhe? Alla domanda in un altro modo, che dire dell'insieme di tutte le lingue? Si scopre che questo set non è numerabile.

L'insieme di tutte le lingue su qualsiasi alfabeto non è numerabile.

Ancora una volta, non copriamo la prova qui.

Conseguenze

Sebbene possano non essere immediatamente evidenti, le conseguenze dell'innumerevolezza delle lingue e della numerabilità dell'insieme di tutti i programmi per computer sono profonde.

Come mai?

Supponiamo che A sia l'insieme di caratteri ASCII; I caratteri ASCII sono solo quelli necessari per comporre un programma per computer. Possiamo vedere che l'insieme di stringhe che rappresentano, diciamo, programmi JavaScript, è un sottoinsieme di A* (qui, * è l'operatore stella di Kleene). La scelta di JavaScript è arbitraria. Poiché questo insieme di programmi è un sottoinsieme di un insieme numerabile, abbiamo che l'insieme di programmi JavaScript è numerabile.

Inoltre, consideriamo che per qualsiasi linguaggio L , possiamo definire una funzione f che valuti 1 se una stringa x è in L e 0 altrimenti. Tutte queste funzioni sono distinte. Poiché esiste una corrispondenza 1:1 con l'insieme di tutte le lingue e poiché l'insieme di tutte le lingue non è numerabile, abbiamo che l'insieme di tutte queste funzioni non è numerabile.

Ecco il punto profondo:

Poiché l'insieme di tutti i programmi validi è numerabile ma l'insieme delle funzioni no, allora devono esserci alcune funzioni per le quali semplicemente non possiamo scrivere programmi.

Non sappiamo ancora che aspetto abbiano queste funzioni o problemi, ma sappiamo che esistono. Questa è una realizzazione umiliante, perché ci sono alcuni problemi là fuori per i quali non esiste una soluzione. Consideriamo i computer estremamente potenti e capaci, eppure alcune cose sono fuori dalla loro portata.

Ora la domanda diventa: "Che aspetto hanno questi problemi?" Prima di continuare a descrivere tali problemi, dobbiamo prima modellare il calcolo in modo generalizzato.

Macchine di Turing

Uno dei primissimi modelli matematici di un computer è stato sviluppato da Alan Turing. Questo modello, chiamato macchina di Turing, è un dispositivo estremamente semplice che cattura completamente la nostra nozione di computabilità.

L'input alla macchina è un nastro su cui è stato scritto l'input. Utilizzando una testina di lettura/scrittura, la macchina trasforma l'input in output attraverso una serie di passaggi. Ad ogni passaggio, si decide se e cosa scrivere sul nastro e se spostarlo a destra oa sinistra. Questa decisione si basa esattamente su due cose:

• Il simbolo attuale sotto la testa, e

• Lo stato interno della macchina, che viene anche aggiornato man mano che viene scritto il simbolo

Questo è tutto.

Universalità

Nel 1926, Alan Turing non solo sviluppò la macchina di Turing, ma ebbe anche una serie di altre importanti intuizioni sulla natura del calcolo quando scrisse il suo famoso articolo, "Sui numeri calcolabili". Si rese conto che un programma per computer stesso poteva essere considerato input per un computer. Da questo punto di vista, ha avuto la bella idea che una macchina di Turing potesse simulare o eseguire quell'input.

Anche se oggi diamo per scontate queste idee, ai tempi di Turing, l'idea di una macchina così universale è stata la svolta principale che ha permesso a Turing di sviluppare problemi irrisolvibili.

Tesi di Church-Turing

Prima di continuare, esaminiamo un punto importante: sappiamo che la macchina di Turing è un modello di calcolo, ma è abbastanza generale? Per rispondere a questa domanda, ci rivolgiamo alla tesi di Church-Turing, che dà credito alla seguente affermazione:

Tutto ciò che è calcolabile è calcolabile da una macchina di Turing.

Mentre Turing ha sviluppato la macchina di Turing come modello di calcolo, Alonzo Church ha anche sviluppato un modello di calcolo noto come lambda-calculus. Questi modelli sono potenti, perché entrambi descrivono il calcolo e lo fanno in un modo uguale a qualsiasi computer di oggi o, se è per questo, a qualsiasi computer di sempre. Ciò significa che possiamo usare una macchina di Turing per descrivere i problemi irrisolvibili che cerchiamo, sapendo che le nostre scoperte si applicherebbero a tutti i possibili computer passati, presenti e oltre.

Riconoscibilità e Decidibilità

Dobbiamo coprire un po' più di sfondo prima di descrivere concretamente un problema irrisolvibile, vale a dire i concetti di riconoscitori linguistici e decisori linguistici.

Una lingua è riconoscibile se esiste una macchina di Turing che la riconosce.

e

Una lingua è decidibile se c'è una macchina di Turing che la decide.

Per essere un riconoscitore di una lingua, una macchina di Turing deve accettare ogni stringa nella lingua e non deve accettare nulla che non sia nella lingua. Può rifiutare o eseguire il loop su tali stringhe. Per essere un decisore, una macchina di Turing deve sempre fermare il suo input accettando o rifiutando.

Qui, l'idea di fermare l'input è fondamentale. In effetti, vediamo che i decisori sono più potenti dei riconoscitori. Inoltre, un problema è risolvibile, o in altre parole, una funzione è decidibile solo se esiste una macchina di Turing che decide il linguaggio descritto dalla funzione.

Indecidibilità

Se hai mai scritto un programma per computer, sicuramente devi conoscere la sensazione di stare seduto lì a guardare il computer girare le ruote quando il programma viene eseguito. Non sai se il programma sta impiegando molto tempo o se c'è qualche errore nel codice che causa un ciclo infinito. Potresti anche esserti chiesto perché il compilatore non controlla il codice per vedere se si fermerebbe o si ripeterebbe per sempre durante l'esecuzione.

Il compilatore non ha un tale controllo perché semplicemente non può essere fatto. Non è che gli ingegneri dei compilatori non siano abbastanza intelligenti o non abbiano le risorse; è semplicemente impossibile controllare un programma per computer arbitrario per determinare se si interrompe.

Possiamo dimostrarlo usando la macchina di Turing. Le macchine di Turing possono essere descritte come stringhe, quindi ce n'è un numero numerabile. Supponiamo che M ₁ , M ₂ e così via costituiscano l'insieme di tutte le macchine di Turing. Definiamo la seguente funzione:

Qui, <M> è la sintassi per "codifica di stringa di M" e questa funzione rappresenta il problema di emettere 1 se M _i si interrompe accettando M _j come input e emettendo 0 in caso contrario. Nota che M devo fermarsi ( _cioè essere un decisore). Ciò è necessario poiché si vuole descrivere una funzione indecidibile (cioè un problema irrisolvibile).

Ora definiamo anche un linguaggio L che consiste in codifiche di stringhe di macchine di Turing che NON accettano le proprie descrizioni:

Ad esempio, una macchina M ₁ può emettere 0 sull'ingresso <M ₁ > mentre un'altra macchina M ₂ può emettere 1 sull'ingresso <M ₂ >. Per dimostrare che questo linguaggio è indecidibile, chiediamo cosa fa M _L , la macchina che decide il linguaggio L, quando gli viene data la propria descrizione <M _L > come input. Ci sono due possibilità:

M _L accetta <M _L >

o

M _L rifiuta <M _L >

Se M _L accetta la propria codifica, significa che <M _L > non è nella lingua L; tuttavia, se così fosse, M _L non avrebbe dovuto accettare la sua codifica in primo luogo. D'altra parte, se M _L non accetta la propria codifica, allora <M _L > è nel linguaggio L, quindi M _L avrebbe dovuto accettare la sua codifica di stringa.

In entrambi i casi abbiamo un paradosso, o in termini matematici, una contraddizione, a dimostrazione dell'indecidibilità del linguaggio L; quindi, abbiamo descritto il nostro primo problema irrisolvibile.

Problema di arresto

Sebbene il problema appena descritto possa non sembrare rilevante, può essere ridotto a ulteriori problemi irrisolvibili di importanza pratica, in particolare il problema dell'arresto:

Il linguaggio delle codifiche delle macchine di Turing che si fermano sulla stringa vuota.

Il problema dell'arresto si applica alla domanda sul perché i compilatori non siano in grado di rilevare cicli infiniti da prima. Se non siamo in grado di determinare se un programma termina sulla stringa vuota, come potremmo determinare se la sua esecuzione risulterebbe in un ciclo infinito?

A questo punto, potrebbe sembrare che abbiamo appena agitato le mani per raggiungere una semplice conclusione; tuttavia, ci siamo effettivamente resi conto che nessuna macchina di Turing può dire se un programma per computer si fermerà o rimarrà in loop per sempre. Questo è un problema importante con le applicazioni pratiche e non può essere risolto su una macchina di Turing o qualsiasi altro tipo di computer. Un iPhone non può risolvere questo problema. Un desktop con molti core non può risolvere questo problema. Il cloud non può risolvere questo problema. Anche se qualcuno dovesse inventare un computer quantistico, non sarebbe comunque in grado di risolvere il problema dell'arresto.

Sommario

Nel nostro esame della teoria della computabilità, abbiamo visto come ci siano molte funzioni che non sono calcolabili nel senso ordinario della parola mediante un argomento di conteggio. Abbiamo definito con precisione cosa intendiamo per calcolo, risalendo all'ispirazione di Turing dalla sua esperienza con carta e penna per formalizzare la macchina di Turing. Abbiamo visto come questo modello può calcolare tutto ciò che può fare qualsiasi computer oggi o previsto per domani, e abbiamo realizzato una classe di problemi che non sono affatto calcolabili.

Tuttavia, la computabilità ha un aspetto negativo. Solo perché possiamo risolvere un problema non significa che possiamo risolverlo rapidamente. Dopotutto, a che serve un computer se il suo calcolo non finisce prima che il sole diventi nova su di noi decine di milioni di anni nel futuro?

Lasciandoci alle spalle le funzioni e i linguaggi calcolabili, discutiamo ora la complessità del calcolo, il rilevamento del calcolo efficiente e il famoso problema P vs. NP.

Complessità

Lento vs veloce

Gli informatici riconoscono una varietà di classi di problemi e due classi a cui teniamo includono problemi che i computer possono risolvere rapidamente o in modo efficiente noti come P e problemi le cui soluzioni possono essere verificate rapidamente ma non possono essere ottenute rapidamente noti come NP .

Ad esempio, supponiamo che tu sia responsabile dello sviluppo di algoritmi per un servizio di appuntamenti online e che qualcuno chieda: "Tutti possono avere un appuntamento?" La risposta si riduce all'associazione di individui compatibili in modo tale che tutti siano accoppiati. Risulta che ci sono algoritmi efficienti per risolvere questo problema. Questo problema è nell'insieme P .

E se volessimo identificare la cricca più numerosa tra i nostri utenti? Per cricca intendiamo la più grande rete di individui che sono tutti compatibili tra loro. Quando il numero di utenti è basso, questo problema può essere risolto rapidamente. Possiamo facilmente identificare, diciamo, una cricca con 3 utenti. Quando iniziamo a cercare cricche più grandi, tuttavia, il problema diventa sempre più difficile da risolvere. Questo problema è nell'insieme NP .

Definizioni formali

P è l'insieme dei problemi risolvibili in tempo polinomiale. Cioè, il numero di passi di calcolo è limitato da una funzione polinomiale rispetto alla dimensione del problema. Sappiamo che il "Possono tutti avere un appuntamento?" domanda, nota anche come problema di corrispondenza bipartita, è in P .

NP è l'insieme dei problemi verificabili in tempo polinomiale. Questo include ogni problema in P, ovviamente; tuttavia, non sappiamo se questo contenimento sia rigoroso. Conosciamo problemi che sono verificabili in modo efficiente ma non risolvibili in modo efficiente, ma non sappiamo se il problema è veramente intrattabile. Il problema della cricca è uno di questi problemi. Sappiamo di poter verificare la soluzione in modo efficiente, ma non sappiamo con certezza se siamo in grado di risolvere il problema in modo efficiente.

Infine, NP-completo è l'insieme di problemi che sono i problemi più difficili in NP . Sono indicati come i più difficili perché qualsiasi problema in NP può essere efficacemente trasformato in NPC . Di conseguenza, se qualcuno dovesse identificare una soluzione efficiente a un problema in NPC , l'intera classe di NP verrebbe assorbita da P . Il problema della cricca è anche in NPC .

Quindi, arriviamo al problema di P vs. NP . Molti informatici e matematici credono fermamente che P e NP non siano uguali. Se lo fossero, le implicazioni sarebbero oltre il profondo. Gran parte dell'infrastruttura digitale odierna si basa sul fatto che ci sono problemi in NP che non sono in P . Se così non fosse, i metodi crittografici, ad esempio, crolleranno dall'oggi al domani, consentendo a una persona in possesso di una soluzione efficiente a un problema di NPC di sovvertire anche i protocolli di sicurezza più severi.

Sottigliezze di trattabilità

Per i principianti dell'informatica, la differenza tra i problemi di corrispondenza e di cricca potrebbe non sembrare un grosso problema. In effetti, la differenza tra un problema in P e un problema in NP può essere molto sottile. Essere in grado di distinguere la differenza è importante per chiunque progetti algoritmi nel mondo reale.

Considera il problema del percorso più breve. Date due posizioni, l'obiettivo è identificare il percorso più breve tra di loro. Un iPhone lo calcola in pochi millisecondi. Questo è un problema trattabile computazionalmente.

Consideriamo invece il problema del commesso viaggiatore, in cui l'obiettivo è visitare un sottoinsieme di possibili destinazioni che terminano all'origine percorrendo la distanza più breve possibile. Questo problema è simile al problema del percorso più breve ma è NP-completo; spiega anche perché la logistica della catena di approvvigionamento è un'industria da miliardi di dollari.

In realtà possiamo essere ancora più sottili. Invece di chiedere il percorso più breve (P), possiamo chiedere il percorso più lungo senza cicli. Risulta che anche il problema del percorso più lungo è NP-completo.

Ci sono molti altri esempi di questa sottile distinzione, inclusa l'identificazione delle coperture dei vertici nei grafici bipartiti rispetto a quelli generali o la soddisfazione di formule booleane con due contro tre letterali per clausola. Il punto è che non è immediatamente ovvio se un problema è in P o NP, ed è per questo che l'analisi del tempo di esecuzione è un'abilità fondamentale. Se l'algoritmo da progettare è per un problema in P, allora sappiamo che esiste una soluzione efficiente. Se d'altra parte il problema è in NP, allora abbiamo una valida argomentazione contro la ricerca di una soluzione, perché l'algoritmo, generalmente, impiegherebbe semplicemente troppo tempo per risolvere il problema.

Sommario

In questo esame di complessità, abbiamo definito le classi di problemi P e NP. P rappresenta informalmente i problemi che possono essere risolti in modo efficiente da un computer mentre NP rappresenta quelli che sono verificabili in modo efficiente.

Nessuno è stato in grado di dimostrare che P non è uguale a NP. Se queste due classi di problemi siano equivalenti è noto come problema P vs. NP, ed è il problema aperto più importante nell'informatica teorica oggi, se non in tutta la matematica. Infatti, nell'anno 2000, il Clay Math Institute ha nominato il problema P vs. NP come una delle sette domande aperte più importanti in matematica e ha offerto una taglia di un milione di dollari per una dimostrazione che determina la soluzione a questo problema.

Conclusione

In questo articolo, abbiamo approfondito i regni della computabilità e della complessità, rispondendo a grandi domande come "Cos'è un computer?" Sebbene i dettagli possano essere travolgenti, ci sono una serie di spunti profondi che vale la pena ricordare:

• Ci sono alcune cose che semplicemente non possono essere calcolate, come il problema dell'arresto.

• Ci sono alcune cose che non possono essere calcolate in modo efficiente, come i problemi in NPC.

Più importanti dei dettagli sono i modi di pensare ai problemi di calcolo e computazionali. Nella nostra vita professionale e anche nella nostra quotidianità, potremmo imbatterci in problemi mai visti prima e possiamo utilizzare strumenti e tecniche collaudati per determinare la migliore linea d'azione.

Ulteriori letture sul blog di Toptal Engineering:

• Come avvicinarsi alla scrittura di un interprete da zero