Est un dictionnaire Turing complet

Question

avec "Dictionnaire" Je veux dire un éventail de paires de touches / de valeur avec des clés uniques.Sinon, pourquoi?Si suffisamment longtemps, vous pouvez utiliser la clé comme entrée et la valeur en tant que sortie et que cela pourrait avoir la solution autant de problèmes que vous le souhaitez.Il pourrait «calculer» quelque chose aussi longtemps qu'il est suffisamment long pour tenir chaque entrée possible.Ce qui n'aurait pas besoin d'être infini aussi longtemps que l'intrant aura une certaine quantité de bits.Donc, si nous acceptons que l'entrée sera X bits, vous n'aurez plus besoin d'un dictionnaire avec 2 ^ x et vous disposez de chaque machine de Turing possible qui prendra X bits comme une entrée.

Droite?Eh bien, je suppose que je ne suis pas mais pourquoi?

Answer 1

Une simple machine Turing peut ajouter deux entiers-- tous les entiers deux entiers. Un dictionnaire fini ne peut pas.

EDIT:
(Je modifie ma réponse parce que Soandos a fait un point trop beau pour répondre dans une boîte de commentaire à crampes.)

bonne question! Supposons que nous ayons un dictionnaire infini, la liste {Key, la valeur} paires où les touches sont toutes des combinaisons possibles de machines de Turing et de leurs entrées finies (ou de manière équivalente, toutes les séquences d'entrée finies possibles à une machine à turing universelle), par ordre croissant. Les valeurs sont les états finaux correspondants, avec un bit de premier plan pour indiquer [les arrêts, ne s'arrêtent pas]. Je soutiens que ce est Turing-complet. (L'acte de regarder une entrée est trivialement simple et je ne pense pas que nous devons nous disputer à ce sujet).

L'insolution du problème d'arrêt a un équivalent dans le dictionnaire JSOLDI: si nous voulons pouvoir rechercher le [HALT, ne pas arrêter de mettre fin à] un peu d'entrée sous une certaine taille, nous n'avons besoin que d'une partie finie de la dictionnaire. Mais pour mettre en œuvre une grande partie du dictionnaire en tant que machine de Turing, nous aurions besoin d'une machine plus grande que cette taille limitante-- L'entrée ne serait pas dans cette partie du dictionnaire. Pour toute taille de machine, une machine peut répondre à la question d'arrêt pour toutes les machines de cette taille ... mais que la machine est plus grande, elle ne peut donc pas répondre à la question de lui-même. De même, tout volume fini du dictionnaire est complètement répété dans une entrée quelque part (en fait, infiniment de nombreuses entrées), mais cette entrée n'est pas dans ce volume.

Answer 2

Une machine de Turing serait capable de calculer tout type d'entrée avec tout type de programme, et il ne doit pas nécessairement être une entrée de longueur fixe.Un dictionnaire n'aurait plus aucun moyen de sélectionner quelle paire de clé / valeur correspond à l'entrée pour un programme sélectionné.

En outre, si vous avez une entrée de x bits, votre espace clé ne sera pas x ^ 2, il sera 2 ^ x.Et ce sera pour un seul programme.

En fait, même si vous aviez un dictionnaire avec des paires de clé / valeur infiniment, je parie que la logique requise pour déterminer quelle clé à sélectionner serait probablement nécessité une machine de Turing ou quelque chose de plus compliqué pour sélectionner la clé.

Answer 3

La complétude de Turcy a à voir avec un ensemble de règles pour faire quelque chose et non comment les données sont stockées.Voir ici .