Quelle est la machine de Turing universelle à 2 états non controversée la plus simple?

Je veux encoder une simple machine de Turing dans les règles d'un jeu de cartes. Je voudrais en faire une machine de Turing universelle afin de prouver l'exhaustivité de Turing.

Jusqu'à présent, j'ai créé un état de jeu qui code pour la machine de Turing à 2 états et 3 symboles d'Alex Smith . Cependant, il semble (basé sur Wikipedia) qu'il existe une certaine controverse quant à savoir si la machine (2, 3) est réellement universelle.

Par souci de rigueur, j'aimerais que ma preuve présente une UTM "non controversée". Donc mes questions sont:

1. La machine (2,3) est-elle généralement considérée comme universelle, non universelle ou controversée? Je ne sais pas où trouver des endroits réputés pour trouver la réponse à cette question.

2. Si la machine (2,3) n'est pas largement acceptée comme universelle, quel est le plus petit N de sorte qu'une machine (2, N) soit acceptée de manière non controversée comme universelle?

Modifié pour ajouter: Il serait également utile de connaître toutes les exigences pour la bande infinie pour les machines mentionnées, si vous les connaissez. Il semble que la (2,3) machine nécessite un état initial de la bande qui n'est pas périodique, ce qui sera un peu difficile à simuler dans les règles d'un jeu de cartes.

Il y a eu de nouveaux résultats depuis les travaux cités dans les réponses précédentes. Cette enquête décrit l'état de l'art (voir figure 1). La taille de la plus petite machine de Turing universelle connue dépend des détails du modèle et voici deux résultats qui sont pertinents pour cette discussion:

• Il existe une machine universelle standard à 2 états et 18 symboles (Rogozhin 1996. TCS, 168 (2): 215-240). Ici, nous avons la notion habituelle de symbole vierge dans une ou les deux directions d'une même bande.
• Il existe une machine faiblement universelle à 2 états et 4 symboles (Neary, Woods 2009. FCT. Springer LNCS 5699: 262-273). Ici, nous avons une seule bande contenant l'entrée finie et un mot constant (indépendant de l'entrée) répété infiniment vers la droite, avec un autre mot constant répété infiniment vers la gauche. Cela améliore la machine faiblement universelle mentionnée par David Eppstein.$r$$l$

Il semble que le (2,18) vous soit le plus utile.

Notez qu'il est maintenant connu que toutes les plus petites machines universelles de Turing fonctionnent en temps polynomial. Cela implique que leur problème de prédiction (étant donné une machine , entrée w et temps lié t en unaire, M accepte w dans le temps t ?) Est P-complet. Si vous essayez de faire un jeu (à 1 joueur), cela peut être utile, par exemple pour montrer qu'il est difficile pour NP de trouver une configuration initiale (main de cartes) qui mène à une victoire en moins de t mouvements. Pour ces problèmes de complexité, nous ne nous soucions que d'une partie finie de la bande, ce qui rend les machines (extrêmement petites) faiblement universelles très utiles.$M$$w$$t$$M$$w$$t$

La figure montre les plus petites machines universelles connues pour une variété de modèles de machines Turing (tirées de Neary, Woods SOFSEM 2012), les références peuvent être trouvées ici .

Ce n'est pas une vraie réponse à votre question (je ne connais pas grand-chose au débat sur la machine (2,3)); mais je vous suggère le papier " Petites machines de Turing et compétition généralisée de castors occupés ". Je l'ai rapidement lu il y a quelque temps, et il a un joli graphique avec les limites entre les 4 types de petites MT:

• décidable
• problème de type Collatz ouvert
• $3x + 1$
• universel

(peut-être que certains résultats ont été améliorés).

La notion de MT utilisée dans le papier est la définition standard de la MT utilisée dans les papiers sur les petites machines universelles de Turing:

... Ils ont une bande unidimensionnelle unique infinie dans les deux directions et une tête de lecture-écriture bidirectionnelle unique. Il y a un symbole vierge noté 0. Initialement, un mot fini, l'entrée, est écrit sur la bande, les autres cellules contiennent le symbole vierge, la tête lit le symbole le plus à gauche de l'entrée et l'état est l'état initial. À chaque étape, selon l'état actuel de la machine et le symbole lu par la tête, le symbole est modifié, la tête se déplace vers la gauche ou la droite (et ne peut pas continuer à lire la même cellule), et l'état est modifié. Le calcul s'arrête lorsqu'un état d'arrêt spécial est atteint. ...

Il est également possible d'atteindre l'universalité avec 7 états et 2 symboles, bien que plusieurs des mêmes objections s'appliquent (conditions initiales non uniformes sur la bande infinie et conditions de terminaison inhabituelles). Voir http://11011110.livejournal.com/104656.html et http://www.complex-systems.com/abstracts/v15_i01_a01.html

Ceux-ci sont basés sur la simulation de l'automate cellulaire Rule 110, prouvé universel par Matthew Cook, et Cook a également trouvé une simulation à 2 états et 5 symboles de la règle 110, si vous êtes lié à la restriction qu'il n'y a que deux états.

$S$$0\leq s < S$$C$$0\leq c< C$$2$$\text{L}$$\text{R}$$C+4SC$

À tout moment, seule la cellule actuelle ou les deux cellules impliquées dans une transition peuvent avoir des couleurs améliorées: toutes les autres cellules ont leur vraie couleur. Nous voulons que notre machine se comporte comme suit: vérifiez la véritable transition à effectuer, déplacez les informations sur "l'état réel" de la cellule que nous voulons laisser vers la cellule cible (cela implique beaucoup de va-et-vient), nettoyez le cellule que nous avons quittée (en lui donnant une vraie couleur), répétez.

$(c,s)$$\text{L}$$\text{R}$$(c_{\text{new}}, s_{\text{new}}, \text{emit})$$\text{L}$

$c$$\text{L}$$c$$(c,0, \text{L},\text{receive})$$\text{R}$

Voici les transitions pour implémenter cela. Dans presque tous les cas, déplacez-vous dans la direction spécifiée par l'état actuel, puis inversez l'état

1. $c \to (c,0,\langle dir\rangle,\text{receive})$$\langle dir\rangle$

2. $(c,s) \to (c_{\text{new}},s_{\text{new}},\text{emit})$

3. $(c,s,\text{emit}) \to (c,s-1,\text{emit})$$s>0$

4. $(c,0,\text{emit}) \to c$

5. $(c,s, \langle dir\rangle, \text{receive}) \to (c, s+1, \langle dir\rangle, \text{receive})$$\langle dir\rangle$

6. $(c,s, \langle dir\rangle, \text{receive}) \to (c,s)$$\langle dir\rangle$

$C+3SC$

à moins que vous ne définissiez soigneusement «non controversé» d'une manière technique, il n'y a pas de réponse précise. voici une autre petite machine basée sur la règle 110 qui s'est avérée universelle dans un sens mais ma compréhension est qu'elle nécessite des formulations de bande d'entrée périodiques infinies (et également une extraction à la fin lorsque la machine s'arrête). je n'ai pas vu le problème de bande "périodique vs non périodique" décrit dans la littérature, bien qu'il ait été discuté, par exemple, sur les listes de diffusion mathématiques [Founding of Mathematics mailing list]

La preuve d'universalité Turing d'Alex Smith de la machine de Turing à 2 états et 3 symboles conjecturée par Wolfram n'est certainement pas controversée. La preuve d'universalité donnée (pas la machine) nécessite un motif infini sur la bande de Turing, et la question était de savoir si l'on devait autoriser de telles configurations (vous pouvez considérer la bande habituellement `` vierge '' comme un motif répétitif infini de symboles vierges aussi). La conclusion était que tant que la configuration sur la bande de la machine est fixe (c'est-à-dire qu'elle ne change pas après le début de votre calcul, et reste la même pour tout calcul), alors le calcul universel est effectué par la machine de Turing. Notez que cela n'est PAS controversé pour la règle 110 de Wolfram Elementary Cellular Automaton que Wolfram et Cook se sont révélés universels. La preuve d'universalité de la règle 110 nécessite également un motif infini sur la configuration initiale, différent de chaque côté, et il est donc de la même nature pour la machine de Turing à 2 états et 3 symboles. Une autre préoccupation était que peut-être un tel assouplissement de l'exigence de la condition initiale (vide) rendrait universels les automates universels non Turing acceptés, tels que les automates à états finis, linéaires ou poussés vers le bas pour citer quelques exemples, mais il ne le fait pas respecte la hiérarchie de Chomsky. Il est donc incontestable que la machine de Turing à 2 états et à 3 symboles est universelle, mais sa preuve d'universalité a nécessité une variation de ce qui est généralement considéré comme les cotants d'une bande de machine de Turing ordinaire. Soit dit en passant, cela n'implique pas directement que l'état à 2 états,