Perché le funzioni totali non enumerabile?

Question

Abbiamo imparato a conoscere il concetto di enumerazioni di funzioni. In pratica, essi corrispondono a linguaggi di programmazione.

In un'osservazione di passaggio, il professore ricordato che la classe di tutte le funzioni totali (cioè le funzioni che terminano sempre per ogni ingresso) è non enumerable. Ciò significherebbe che non siamo in grado di elaborare un linguaggio di programmazione che ci permette di scrivere tutte le funzioni totali, ma non gli altri --- che sarebbe bello avere!

Così come è possibile che noi (apparentemente) dobbiamo accettare il rischio di non-terminazione se vogliamo potenza di calcolo decente?

Answer 1

A causa di diagonalizzazione. Se $ (f_e: e \ in \ mathbb {N}) $ è un'enumerazione computabile di tutte le funzioni computabili totale da $ \ mathbb {N} $ a $ \ mathbb {N} $, in modo tale che ogni $ f_e $ era totale, allora $ g (i) = f_i (i) + 1 $ sarebbe anche una funzione calcolabile totale, ma non sarebbe nell'enumerazione. Ciò sarebbe in contrasto con le ipotesi circa la sequenza. Così non computabile censimento di funzioni può essere costituito esattamente totali funzioni calcolabili.

Si supponga che pensiamo di un universale funzione calcolabile $ h (E, I) $, dove i mezzi "universali" $ h $ è una funzione binaria calcolabile e che per ogni calcolabile funzione unaria $ f (N) totale $ v'è una certa $ e $ tale che $ f (i) = h (e, i) $ per tutti i $ i $. Poi ci deve essere anche un po 'di $ e $ tale che $ g (n) = h (e, n) $ non è una funzione totale, a causa del paragrafo precedente. In caso contrario, $ h $ darebbe un'enumerazione computabile del totale delle funzioni calcolabili unari che include tutte le funzioni totali unari calcolabili.

Quindi il requisito che ogni funzione è un sistema di funzioni è totale è incompatibile con l'esistenza di una funzione universale in quel sistema. Per alcuni sistemi deboli, come le funzioni ricorsive primitive, ogni funzione è totale, ma non ci sono funzioni universali. sistemi più forti che hanno funzioni universali, come Turing computability, semplicemente devono avere funzioni parziali per consentire la funzione universale di esistere.

Answer 2

Giusto per essere chiari, abbiamo bisogno di distinguere le funzioni matematiche (io li funzioni di chiamata e spesso v'è numerabile molti di loro in modo che non sono affatto enumerabile) e le funzioni si può scrivere: io li programmi chiamerà o anche funzioni calcolabili .

Un sottoinsieme $ S $ di un insieme numerabile $ E $ è chiamato calcolabile se v'è un programma che, dato un elemento $ x $ di $ e $ risponde "sì", se $ x?S $ e "no" se $ x \ not?S $. (E lui deve sempre rispondere qualcosa) Un set è chiamato ricorsivamente enumerabile se il programma è autorizzato a non rispondere invece di dire "no". (È equivalente a richiedere che il programma deve stampare tutti gli elementi di $ S $ in qualsiasi ordine)

L'insieme di tutti i programmi che sono in totale su un insieme finito enumerabile perché è possibile scrivere un interprete che basta eseguire il programma su tutti gli elementi di un insieme finito e tornare "sì" se tutti termina. (Ma non può vedere se qualcuno di loro non lo fa)

Il professore ha detto che l'insieme di tutti i programmi che si trovano su un totale di insieme infinito non enumerabile perché non si può semplicemente eseguire il programma su un numero infinito di elementi.

Ma questo non significa che questo sia un male:

1. Per esempio il set, se tutti i programmi che sono dimostrabilmente totale è enumerabile perché è possibile enumerare tutte le prove e meccanicamente verificare se dimostrano il vostro programma è totale .

2. Anche un insieme enumerabile non sarebbe pratico, perché si potrebbe essere necessario attendere per sempre senza essere sicuri se la procedura dovrebbe terminare un giorno. Non vedo come utilizzare alcuni programmi che enumerare tutte le funzioni totali ...

Ci sono alcuni linguaggi di programmazione in cui tutto ciò che si scrive è garantita per terminare solo con tipizzazione statica! Ci sono anche alcuni che garanzie si polinomiale vincolati. Sono per lo più accademico, per ora, la scrittura in quelli probabilmente farà sentire i vincoli più che scrivere in Python, ma ci sono un sacco di ricercatori che lavorano su questo.

Quindi, per rispondere alla tua domanda: in un certo senso, sì. Potenziale non-terminazione è necessario essere Turing-complete (più alta potenza di calcolo per ora). Ma non trovo questo direttamente rilevanti per il fatto che le funzioni totali sono enumerabile o meno. È ancora possibile scrivere tutti i programmi totale!