Teoria della computabilità

A partire dalla teoria degli insiemi ricorsivi e delle funzioni sopra descritte, il campo della teoria della ricorsione è cresciuto fino a includere lo studio di molti argomenti strettamente correlati. Queste non sono aree di ricerca indipendenti: ognuna di queste aree trae idee e risultati dalle altre, e la maggior parte dei teorici della ricorsione ha familiarità con la maggior parte di esse.

Computabilità relativa e gradi di Turingmodifica

La teoria della ricorsione nella logica matematica si è tradizionalmente focalizzata sulla computabilità relativa, una generalizzazione della computabilità di Turing definita usando macchine oracle Turing, introdotta da Turing (1939). Una macchina di Turing oracle è un dispositivo ipotetico che, oltre a eseguire le azioni di una normale macchina di Turing, è in grado di porre domande a un oracolo, che è un particolare insieme di numeri naturali. La macchina oracle può solo porre domande del modulo ” Is n nel set oracle?”. Ogni domanda riceverà immediatamente una risposta corretta, anche se il set oracle non è computabile. Quindi una macchina oracle con un oracle noncomputable sarà in grado di calcolare set che una macchina di Turing senza un oracle non può.

Informalmente, un insieme di numeri naturali A è Turing riducibile a un insieme B se c’è una macchina oracle che dice correttamente se i numeri sono in A quando vengono eseguiti con B come set oracle (in questo caso, l’insieme A è anche detto di essere (relativamente) computabile da B e ricorsivo in B). Se un insieme A è Turing riducibile ad un insieme B e B è Turing riducibile ad A allora si dice che gli insiemi abbiano lo stesso grado di Turing (chiamato anche grado di irrisolvibilità). Il grado di Turing di un insieme fornisce una misura precisa di quanto non sia calcolabile l’insieme.

Gli esempi naturali di set non calcolabili, inclusi molti set diversi che codificano le varianti del problema di arresto, hanno due proprietà in comune:

1. Sono ricorsivamente enumerabili e
2. Ciascuno può essere tradotto in qualsiasi altro tramite una riduzione di molti. Cioè, dati tali insiemi A e B, esiste una funzione computabile totale f tale che A = {x: f (x)} B}. Si dice che questi insiemi siano molti-uno equivalenti (o m-equivalenti).

Le riduzioni di molti-uno sono “più forti” delle riduzioni di Turing: se un insieme A è molti-uno riducibile a un insieme B, allora A è Turing riducibile a B, ma il contrario non sempre regge. Sebbene gli esempi naturali di insiemi non modificabili siano tutti equivalenti a molti, è possibile costruire insiemi enumerabili ricorsivamente A e B in modo tale che A sia Turing riducibile a B ma non molti-uno riducibile a B. Si può dimostrare che ogni insieme ricorsivamente enumerabile è molti-uno riducibile al problema di arresto, e quindi il problema di arresto è l’insieme ricorsivamente enumerabile più complicato rispetto alla riducibilità di molti-uno e rispetto alla riducibilità di Turing. Post (1944) ha chiesto se ogni insieme ricorsivamente enumerabile sia computabile o Turing equivalente al problema di arresto, cioè se non esiste un insieme ricorsivamente enumerabile con un grado di Turing intermedio tra questi due.

Come risultati intermedi, i tipi naturali post definiti di insiemi ricorsivamente enumerabili come gli insiemi semplici, ipersimple e iperipersimple. Post ha mostrato che questi insiemi sono strettamente tra gli insiemi computabili e il problema di arresto rispetto alla riducibilità di molti-uno. Post ha anche dimostrato che alcuni di essi sono strettamente intermedi sotto altre nozioni di riducibilità più forti della riducibilità di Turing. Ma Post lasciò aperto il problema principale dell’esistenza di insiemi ricorsivamente enumerabili di grado di Turing intermedio; questo problema divenne noto come problema di Post. Dopo dieci anni, Kleene e Post mostrarono nel 1954 che ci sono gradi di Turing intermedi tra quelli degli insiemi computabili e il problema di arresto, ma non riuscirono a dimostrare che uno di questi gradi contiene un insieme ricorsivamente enumerabile. Molto presto, Friedberg e Muchnik risolsero indipendentemente il problema di Post stabilendo l’esistenza di insiemi ricorsivamente enumerabili di grado intermedio. Questo risultato innovativo ha aperto un ampio studio dei gradi di Turing degli insiemi ricorsivamente enumerabili che si è rivelato possedere una struttura molto complicata e non banale.

Ci sono innumerevoli insiemi che non sono ricorsivamente enumerabili e l’indagine dei gradi di Turing di tutti gli insiemi è centrale nella teoria della ricorsione quanto l’indagine dei gradi di Turing ricorsivamente enumerabili. Sono stati costruiti molti gradi con proprietà speciali: gradi senza iperimmune in cui ogni funzione computabile rispetto a quel grado è maggiorata da una funzione computabile (non lativizzata) ; alti gradi rispetto ai quali si può calcolare una funzione f che domina ogni funzione computabile g nel senso che esiste una costante c a seconda di g tale che g(x) < f(x) per tutti x > c; gradi casuali contenenti insiemi algoritmicamente casuali; gradi 1-generici di insiemi 1-generici; e i gradi al di sotto del problema di arresto degli insiemi limite-ricorsivi.

Lo studio di gradi di Turing arbitrari (non necessariamente ricorsivamente enumerabili) comporta lo studio del salto di Turing. Dato un insieme A, l’Turing salto di a è Un insieme di numeri naturali che codifica per una soluzione al problema della terminazione per oracle macchine di Turing in esecuzione con oracle A. Turing salto di qualsiasi serie è sempre più alto grado di Turing quelli originali, e un teorema di Friedburg mostra che ogni insieme che calcola il problema della terminazione può essere ottenuta come Turing salto di un altro. Il teorema di Post stabilisce una stretta relazione tra l’operazione di salto di Turing e la gerarchia aritmetica, che è una classificazione di alcuni sottoinsiemi dei numeri naturali in base alla loro definibilità in aritmetica.

Molte ricerche recenti sui gradi di Turing si sono concentrate sulla struttura complessiva dell’insieme di gradi di Turing e dell’insieme di gradi di Turing contenenti insiemi ricorsivamente enumerabili. Un teorema profondo di Shore e Slaman (1999) afferma che la funzione che mappa un grado x al grado del suo salto di Turing è definibile nell’ordine parziale dei gradi di Turing. Una recente indagine di Ambos-Spies e Fejer (2006) fornisce una panoramica di questa ricerca e della sua progressione storica.

Altre riduzionimodifica

Un’area di ricerca in corso nella teoria della ricorsione studia le relazioni di riducibilità diverse dalla riducibilità di Turing. Post (1944) introdusse diverse forti riducibilità, così chiamate perché implicano la riducibilità della tabella di verità. Una macchina di Turing che implementa una forte riducibilità calcolerà una funzione totale indipendentemente da quale oracle viene presentato. Le riducibilità deboli sono quelle in cui un processo di riduzione non può terminare per tutti gli oracoli; la riducibilità di Turing è un esempio.

Le forti riducibilità includono:

Riducibilità one-one A è riducibile one-one (o 1-riducibile) a B se esiste una funzione iniettiva computabile totale f tale che ogni n è in A se e solo se f(n) è in B. Riducibilità Many-one Questa è essenzialmente una riducibilità one-one senza il vincolo che f sia iniettiva. A è molti-uno riducibile (o m-riducibile) a B se esiste una funzione computabile totale f tale che ogni n è in A se e solo se f (n) è in B. Riducibilità della tabella di verità A è riducibile a B se A è riducibile a B tramite una macchina oracle Turing che calcola una funzione totale indipendentemente dall’oracolo che viene fornito. A causa della compattezza dello spazio Cantor, ciò equivale a dire che la riduzione presenta un singolo elenco di domande (a seconda solo dell’input) all’oracolo contemporaneamente, e quindi avendo visto le loro risposte è in grado di produrre un output senza porre ulteriori domande indipendentemente dalla risposta dell’oracolo alle query iniziali. Sono state studiate anche molte varianti di riducibilità della tabella di verità.

Ulteriori riducibilità (positivo, disgiuntivo, congiuntivo, lineare e le loro versioni deboli e limitate) sono discusse nell’articolo Riduzione (teoria della ricorsione).

La principale ricerca sulle forti riducibilità è stata quella di confrontare le loro teorie, sia per la classe di tutti gli insiemi ricorsivamente enumerabili, sia per la classe di tutti i sottoinsiemi dei numeri naturali. Inoltre, sono state studiate le relazioni tra le riducibilità. Ad esempio, è noto che ogni grado di Turing è un grado di tabella della verità o è l’unione di infiniti gradi di tabella della verità.

Sono state studiate anche riducibilità più deboli della riducibilità di Turing (cioè riducibilità implicite nella riducibilità di Turing). Le più note sono la riducibilità aritmetica e la riducibilità iperaritmica. Queste riducibilità sono strettamente connesse alla definibilità rispetto al modello standard dell’aritmetica.

Il teorema di Rice e la gerarchia aritmeticamodifica

Rice ha mostrato che per ogni classe non banale C (che contiene alcuni ma non tutti gli insiemi r.e.) l’indice set E = {e: l’eth r. e. set We is in C} ha la proprietà che il problema di arresto o il suo complemento è molti-uno riducibile a E, cioè, può essere mappato usando una riduzione molti-uno a E (vedi il teorema di Rice per maggiori dettagli). Ma molti di questi set di indici sono ancora più complicati del problema di arresto. Questi tipi di insiemi possono essere classificati usando la gerarchia aritmetica. Ad esempio, l’indice impostato FIN di classe di tutti gli insiemi finiti è sul livello Σ2, l’indice impostato REC della classe di tutti gli insiemi ricorsivi è sul livello Σ3, l’indice impostato COFIN di tutti gli insiemi cofiniti è anche sul livello Σ3 e l’indice impostato COMP della classe di tutti gli insiemi completi di Turing Σ4. Questi livelli gerarchici sono definiti induttivamente, Σn + 1 contiene solo tutti gli insiemi che sono ricorsivamente enumerabili rispetto a Σn; Σ1 contiene gli insiemi ricorsivamente enumerabili. I set di indici qui riportati sono persino completi per i loro livelli, cioè tutti i set in questi livelli possono essere molti-uno ridotto ai set di indici dati.

Matematica inversamodiFica

Il programma di matematica inversa chiede quali assiomi di set-esistenza sono necessari per dimostrare particolari teoremi della matematica nei sottosistemi dell’aritmetica del secondo ordine. Questo studio è stato avviato da Harvey Friedman ed è stato studiato in dettaglio da Stephen Simpson e altri; Simpson (1999) fornisce una discussione dettagliata del programma. Gli assiomi dell’insieme-esistenza in questione corrispondono informalmente agli assiomi che dicono che il powerset dei numeri naturali è chiuso sotto varie nozioni di riducibilità. Il più debole assioma studiato in matematica inversa è la comprensione ricorsiva, che afferma che il powerset dei naturali è chiuso sotto la riducibilità di Turing.

NumberingsEdit

Una numerazione è un’enumerazione di funzioni; ha due parametri, e e x e emette il valore della funzione e-esima nella numerazione sull’ingresso x. I numeri possono essere ricorsivi parziali anche se alcuni dei suoi membri sono ricorsivi totali, cioè funzioni computabili. I numeri ammissibili sono quelli in cui tutti gli altri possono essere tradotti. Una numerazione Friedberg (dal nome del suo scopritore) è una numerazione uno-uno di tutte le funzioni ricorsive parziali; non è necessariamente una numerazione ammissibile. La ricerca successiva si è occupata anche di numerazioni di altre classi come classi di insiemi ricorsivamente enumerabili. Goncharov ha scoperto ad esempio una classe di insiemi ricorsivamente enumerabili per i quali i numeri rientrano esattamente in due classi rispetto agli isomorfismi ricorsivi.

Il metodo di prioritàedit

Per ulteriori spiegazioni, vedere la sezione Problema del post e il metodo di priorità nell’articolo Turing degree.

Il problema di Post è stato risolto con un metodo chiamato metodo di priorità; una dimostrazione che utilizza questo metodo è chiamata argomento di priorità. Questo metodo viene utilizzato principalmente per costruire set enumerabili ricorsivamente con proprietà particolari. Per utilizzare questo metodo, le proprietà desiderate dell’insieme da costruire sono suddivise in un elenco infinito di obiettivi, noti come requisiti, in modo che soddisfare tutti i requisiti faccia sì che l’insieme costruito abbia le proprietà desiderate. Ogni requisito è assegnato a un numero naturale che rappresenta la priorità del requisito; quindi 0 è assegnato alla priorità più importante, 1 alla seconda più importante e così via. Il set viene quindi costruito in fasi, ogni fase tenta di soddisfare uno dei requisiti aggiungendo numeri al set o vietando i numeri dal set in modo che il set finale soddisfi il requisito. Può accadere che soddisfare un requisito causerà un altro a diventare insoddisfatto; l’ordine di priorità viene utilizzato per decidere cosa fare in un tale evento.

Gli argomenti prioritari sono stati impiegati per risolvere molti problemi nella teoria della ricorsione e sono stati classificati in una gerarchia basata sulla loro complessità (Soare 1987). Poiché argomenti di priorità complessi possono essere tecnici e difficili da seguire, è stato tradizionalmente considerato auspicabile dimostrare risultati senza argomenti di priorità, o vedere se i risultati dimostrati con argomenti di priorità possono essere dimostrati anche senza di essi. Ad esempio, Kummer ha pubblicato un documento su una prova per l’esistenza di numeri Friedberg senza utilizzare il metodo di priorità.

Il reticolo di setsedit ricorsivamente enumerabili

Quando Post ha definito la nozione di un set semplice come un set di r.e. con un complemento infinito che non contiene alcun r. e infinito. set, ha iniziato a studiare la struttura degli insiemi ricorsivamente enumerabili sotto inclusione. Questo reticolo divenne una struttura ben studiata. Gli insiemi ricorsivi possono essere definiti in questa struttura dal risultato di base che un insieme è ricorsivo se e solo se l’insieme e il suo complemento sono entrambi ricorsivamente enumerabili. Gli insiemi r.e. infiniti hanno sempre sottoinsiemi ricorsivi infiniti; ma d’altra parte, esistono insiemi semplici ma non hanno un superset ricorsivo coinfinito. Post (1944) introdusse già insiemi ipersimple e iperipersimple; in seguito furono costruiti insiemi massimi che sono insiemi r.e. tali che ogni r.e. superset è una variante finita dell’insieme massimo dato o è co-finito. La motivazione originale di Post nello studio di questo reticolo era di trovare una nozione strutturale tale che ogni insieme che soddisfa questa proprietà non è né nel grado di Turing degli insiemi ricorsivi né nel grado di Turing del problema di arresto. Post non ha trovato una tale proprietà e la soluzione al suo problema ha applicato invece metodi prioritari; Harrington e Soare (1991) hanno trovato alla fine una tale proprietà.

Problemi di automorfismomodifica

Un’altra questione importante è l’esistenza di automorfismi nelle strutture teoriche di ricorsione. Una di queste strutture è che uno degli insiemi ricorsivamente enumerabili sotto inclusione modulo differenza finita; in questa struttura, A è inferiore a B se e solo se la differenza impostata B − A è finita. Gli insiemi massimi (come definiti nel paragrafo precedente) hanno la proprietà che non possono essere automorfici a insiemi non massimi, cioè se esiste un automorfismo degli insiemi enumerabili ricorsivi sotto la struttura appena menzionata, allora ogni set massimo viene mappato su un altro set massimo. Soare (1974) ha mostrato che anche le prese converse, cioè ogni due insiemi massimi sono automorfiche. Quindi gli insiemi massimi formano un’orbita, cioè ogni automorfismo conserva la massimalità e due insiemi massimi sono trasformati l’uno nell’altro da qualche automorfismo. Harrington ha dato un ulteriore esempio di una proprietà automorfica: quella dei set creativi, i set che sono molti-uno equivalente al problema di arresto.

Oltre al reticolo di insiemi ricorsivamente enumerabili, gli automorfismi sono studiati anche per la struttura dei gradi di Turing di tutti gli insiemi e per la struttura dei gradi di Turing degli insiemi r.e. In entrambi i casi, Cooper afferma di aver costruito automorfismi non banali che mappano alcuni gradi ad altri gradi; questa costruzione, tuttavia, non è stata verificata e alcuni colleghi ritengono che la costruzione contenga errori e che la questione se esista un automorfismo non banale dei gradi di Turing sia ancora una delle principali questioni irrisolte in questo settore (Slaman e Woodin 1986, Ambos-Spies e Fejer 2006).

Kolmogorov Complessitàmodifica

Il campo della complessità di Kolmogorov e della casualità algoritmica è stato sviluppato durante gli anni 1960 e 1970 da Chaitin, Kolmogorov, Levin, Martin-Löf e Solomonoff (i nomi sono riportati qui in ordine alfabetico; gran parte della ricerca era indipendente e l’unità del concetto di casualità non era compresa al momento). L’idea principale è considerare una macchina di Turing universale U e misurare la complessità di un numero (o stringa) x come la lunghezza dell’ingresso più breve p tale che U(p) emetta x. Questo approccio ha rivoluzionato i modi precedenti per determinare quando una sequenza infinita (equivalentemente, funzione caratteristica di un sottoinsieme dei numeri naturali) è casuale o meno invocando una nozione di casualità per oggetti finiti. La complessità di Kolmogorov è diventata non solo oggetto di studio indipendente, ma viene applicata anche ad altri soggetti come strumento per ottenere prove.Ci sono ancora molti problemi aperti in questo settore. Per questo motivo, una recente conferenza di ricerca in questo settore si è tenuta nel gennaio 2007 e un elenco di problemi aperti è mantenuto da Joseph Miller e Andre Nies.

Calcolo della frequenzamodifica

Questo ramo della teoria della ricorsione ha analizzato la seguente domanda: Per m e n fissi con 0 < m < n, per le quali funzioni A è possibile calcolare per qualsiasi diverso n input x1, x2, …,xn una tupla di n numeri y1, y2,…, yn tale che almeno m delle equazioni A (xk) = yk sono vere. Tali insiemi sono noti come (m, n)-insiemi ricorsivi. Il primo risultato importante in questo ramo della Teoria della Ricorsione è il risultato di Trakhtenbrot che un insieme è computabile se è (m, n)-ricorsivo per alcuni m, n con 2m > n. D’altra parte, gli insiemi semirecorsivi di Jockusch (che erano già noti informalmente prima che Jockusch li introducesse nel 1968) sono esempi di un insieme che è (m, n)-ricorsivo se e solo se 2m < n + 1. Ci sono innumerevoli di questi set e anche alcuni set ricorsivamente enumerabili ma non modificabili di questo tipo. Successivamente, Degtev ha stabilito una gerarchia di insiemi ricorsivamente enumerabili che sono (1, n + 1)-ricorsivi ma non (1, n)-ricorsivi. Dopo una lunga fase di ricerca da parte di scienziati russi, questo argomento è stato ripopolato in occidente dalla tesi di Beigel sulle query limitate, che collegava il calcolo della frequenza alle riducibilità limitate sopra menzionate e ad altre nozioni correlate. Uno dei risultati principali è stata la teoria della cardinalità di Kummer che afferma che un insieme A è computabile se e solo se esiste un n tale che alcuni algoritmi enumerano per ogni tupla di n numeri diversi fino a n molte possibili scelte della cardinalità di questo insieme di n numeri intersecati con A; queste scelte devono contenere la cardinalità vera ma tralasciarne almeno una falsa.

Inferenza induttivamodifica

Questo è il ramo teorico-ricorsivo della teoria dell’apprendimento. Si basa sul modello di apprendimento nel limite di E. Mark Gold dal 1967 e da allora ha sviluppato sempre più modelli di apprendimento. Lo scenario generale è il seguente: Data una classe S di funzioni computabili, esiste uno studente (cioè funzionale ricorsivo) che emette per qualsiasi input del modulo (f(0), f(1),…, f (n)) un’ipotesi. Uno studente M impara una funzione f se quasi tutte le ipotesi sono lo stesso indice e di f rispetto ad una precedentemente concordato accettabile numerazione di tutte le funzioni computabili; M impara a S se M impara ogni f in S. i risultati di Base è che tutti ricorsivamente enumerabile classi di funzioni sono learnable mentre la classe REC di tutte le funzioni computabili non è learnable. Molti modelli correlati sono stati considerati e anche l’apprendimento di classi di insiemi ricorsivamente enumerabili da dati positivi è un argomento studiato dal documento pionieristico di Gold in 1967 in poi.

Generalizzazioni della computabilità di Turingedit

La teoria della ricorsione include lo studio di nozioni generalizzate di questo campo come la riducibilità aritmetica, la riducibilità iperaritmetica e la teoria della ricorsione α, come descritto da Sacks (1990). Queste nozioni generalizzate includono riducibilità che non possono essere eseguite dalle macchine di Turing ma sono comunque generalizzazioni naturali della riducibilità di Turing. Questi studi includono approcci per indagare la gerarchia analitica che differisce dalla gerarchia aritmetica consentendo la quantificazione su insiemi di numeri naturali oltre alla quantificazione su singoli numeri. Queste aree sono collegate alle teorie degli ordini e degli alberi; ad esempio l’insieme di tutti gli indici di alberi ricorsivi (non binari) senza rami infiniti è completo per il livello Π 1 1 {\displaystyle \Pi _{1}^{1}}

della gerarchia analitica. Sia la riducibilità di Turing che la riducibilità iperaritmetica sono importanti nel campo della teoria degli insiemi descrittiva efficace. La nozione ancora più generale di gradi di costruibilità è studiata nella teoria degli insiemi.

Teoria della computabilità continuamodifica

La teoria della computabilità per il calcolo digitale è ben sviluppata. La teoria della computabilità è meno sviluppata per il calcolo analogico che si verifica nei computer analogici, nell’elaborazione del segnale analogico, nell’elettronica analogica, nelle reti neurali e nella teoria del controllo del tempo continuo, modellata da equazioni differenziali e sistemi dinamici continui (Orponen 1997; Moore 1996).