È un dizionario completo completo

Question

Con "Dizionario" intendo un array di coppie di tasti / valore con chiavi uniche. In caso contrario, perché? Se abbastanza a lungo, è possibile utilizzare la chiave come input e il valore come output e potrebbe avere la soluzione a tutti i problemi che desideri. Potrebbe "calcolare" qualsiasi cosa fintanto che è abbastanza lungo da contenere ogni possibile input. Che non avrebbe bisogno di essere infinito finché si stabilisce che l'input avrà una certa quantità di bit. Quindi, se siamo d'accordo sul fatto che l'input sarà X bit, allora avrai bisogno solo di un dizionario con 2^X elementi e hai ogni possibile macchina Turing che prenderà X bit come input.

Destra? Beh, immagino di non esserlo, ma perché?

Answer 1

Una semplice macchina Turing può aggiungere due numeri interi ... qualunque Due numeri interi. Un dizionario finito non può.

MODIFICARE:
(Sto modificando la mia risposta perché Soandos ha fatto un punto troppo bello per rispondere in una casella di commenti angusti.)

Buona domanda! Supponiamo di avere un dizionario infinito, elencando {chiave, valore} coppie in cui le chiavi sono tutte possibili combinazioni di macchine Turing e i loro input finiti (o equivalentemente, tutte le possibili sequenze di input finite a una macchina universale Turing), in ordine di dimensioni crescenti. I valori sono gli stati finali corrispondenti, con un bit principale per indicare [ferme, non si ferma]. Sostengo che questo è Turing-Complete. (L'atto di cercare una voce è banalmente semplice e non credo che dobbiamo discuterne).

L'insolvibilità del problema di arresto ha un equivalente nel dizionario di Jsoldi: se vogliamo essere in grado di cercare il po 'di interruzione di [Halt, non interrompere] alcuna voce al di sotto di una certa dimensione, abbiamo bisogno di solo una parte finita del dizionario. Ma per implementare quella gran parte del dizionario come macchina Turing, avremmo bisogno di una macchina più grande di quella dimensione limitante: la sua entrata non sarebbe in quella parte del dizionario. Per qualsiasi dimensione della macchina c'è una macchina in grado di rispondere alla domanda di arresto per tutte le macchine di quella dimensione: ma Quello La macchina è più grande, quindi non può rispondere alla domanda su se stessa. Allo stesso modo qualsiasi volume finito del dizionario viene completamente ripetuto in una voce da qualche parte (in effetti, infinitamente molte voci), ma quella voce non è in quel volume.

Answer 2

Una macchina Turing sarebbe in grado di calcolare qualsiasi tipo di input con qualsiasi tipo di programma e non deve essere input a lunghezza fissa. Un dizionario inoltre non avrebbe modo di selezionare quale coppia chiave/valore corrisponde all'input per un programma selezionato.

Inoltre, se hai un input di X bit, il tuo spazio chiave non sarà x^2, sarà 2^x. E questo sarà per un singolo programma.

In effetti, anche se avessi un dizionario con coppie chiave/valore infinite, scommetto che la logica richiesta per determinare quale chiave dovevi selezionare, probabilmente richiederebbe una macchina Turing o qualcosa di più complicato per selezionare la chiave.

Answer 3

La completezza di Turing ha a che fare con una serie di regole per fare qualcosa, non come vengono archiviati i dati. Vedere qui.