Quelle est la plus petite machine de Turing où l'on ne sait pas si elle s'arrête ou non?

31

Je sais que le problème de l'arrêt est indécidable en général, mais il y a certaines machines Turing qui s'arrêtent évidemment et d'autres qui ne le sont évidemment pas. De toutes les machines de turing possibles, quelle est la plus petite où personne n'a de preuve qu'elle s'arrête ou non?

halting-problem Aaron
la source

10

La réponse dépend des spécificités du modèle de machine (nombre de symboles, etc.). Selon un article de Wikipédia sur Busy Beaver, il existe une machine à 2 symboles à 5 états qui ne sait pas si elle s'arrête ou non.

Kaveh

1

Notez que la question d'Aaron ne concerne pas la décidabilité d'une langue donnée, mais vraiment l'existence d'une preuve qu'une machine Turing spécifique s'arrête. Pour toute machine Turing, "son" problème d'arrêt (que cette machine s'arrête sur l'entrée vide) soit "décidable": c'est Oui ou Non, et les deux langues {Oui} et {Non} sont décidables. C'est très différent de savoir si l'on a une preuve que la machine s'arrête ou non. Aaron, si vous voulez dire "quel est le plus petit

tel que la langue

s'arrête sur

est indécidable", pouvez-vous modifier votre question?

M

$M$

{w ∣ M

$\{w \mid M$

w}

$w\}$

Michaël Cadilhac

1

@ MichaëlCadilhac Le problème d'arrêt est généralement interprété comme "étant donné une machine

et une entrée

,

s'arrête-t-il pour l'entrée

?" non "Étant donné une machine

,

s'arrête-t-il pour toutes les entrées?"

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

M

$M$

David Richerby

@DavidRicherby: Pour moi, le problème d'arrêt est le langage de la machine (codes) qui s'arrête sur l'entrée vide. Si ce n'est pas le sens voulu ici, je pense qu'il devrait être spécifié pour dissiper la confusion possible (ok, ma).

Michaël Cadilhac

plusieurs façons d'étudier le problème sont valides et interdépendantes et il y a en effet une subtilité à les distinguer, ce que le questionneur n'a pas fait.

vzn

38

Les plus grandes machines de Turing pour lesquelles le problème d'arrêt est décidable sont:

(où est l'ensemble des machines de Turing avec états et symboles). $TM(2,3), TM(2,2), TM(3,2)$ $TM(k,l)$ $k$ $l$

La décidabilité de et est à la frontière et elle est difficile à régler car elle dépend de la conjecture de Collatz qui est un problème ouvert. $TM(2,4)$ $TM(3,3)$

Voir aussi ma réponse sur cstheory about Collatz-like Turing machines and " Small Turing machines and generalized busy beaver competition " par P. Michel (2004) (dans lequel il est conjecturé que est également décidable). $TM(4,2)$

Le commentaire de Kaveh et la réponse de Mohammad sont corrects, donc pour une définition formelle des machines de Turing standard / non standard utilisées dans ce type de résultats, voir Turlough Neary et Damien Woods travaille sur de petites machines de Turing universelles, par exemple La complexité des petites machines de Turing universelles: une enquête (les règles 110 TM sont faiblement universelles).

Marzio De Biasi
la source

2

T M (4, 2)

$TM(4, 2)$

2

{⟨ M, x ⟩ ∣ M halts on x}

$\{\langle M,x \rangle \mid M \text{ halts on } x\}$

H A L T_{M} = {x ∣ M halts on x}

$HALT_M = \{ x \mid M \text{ halts on } x\}$

32

Je voudrais ajouter qu'il existe des machines de Turing pour lesquelles le problème de l'arrêt est indépendant de ZFC.

Par exemple, prenez une machine Turing qui cherche une preuve de contradiction dans ZFC. Ensuite, si ZFC est cohérent, il ne s'arrêtera pas, mais vous ne pouvez pas le prouver dans ZFC (en raison du deuxième théorème d'incomplétude de Gödel).

Il ne s'agit donc pas seulement de ne pas avoir encore trouvé de preuve, parfois il n'y a même pas de preuve.

Denis
la source

ZFC? Que signifie ZFC? Je ne peux tout simplement pas le comprendre à partir du contexte.

Acapulco

7

@Acapulco lmgtfy.com/?q=zfc&l=1

Sasho Nikolov

Lol! D'accord. Je me suis fait lmgtfy'ed. Touchè. Je ne pensais pas que ce serait des initiales qui se rapporteraient immédiatement et uniquement à ce sujet. En tout cas, je ne pense pas que cela fasse mal d'ajouter une courtoisie "ZFC (théorie des ensembles de Zermelo – Fraenkel)" la première fois qu'elle est mentionnée, également pour éviter toute ambiguïté en cas d'existence? :)

Acapulco

16

@Acapulco, veuillez consulter le centre de visite et d' aide . Tout informaticien théorique saurait ce que représente ZFC, il n'y a donc pas vraiment besoin de clarification.

Kaveh

1

2

$2$

5

Personne n'a la preuve que la machine Universal Turing s'arrête ou non. En fait, une telle preuve est impossible en raison de l'indécidabilité du problème de l'arrêt. La plus petite est une machine de Turing universelle à 2 états et 3 symboles qui a été trouvée par Alex Smith pour laquelle il a remporté un prix de 25 000 $.

Mohammad Al-Turkistany
la source

4

Notons cependant que, selon la page Wikipédia citée, la preuve d'universalité est contestée. De plus, ce n'est pas le modèle standard des machines Turing: la machine prétendument universelle n'a pas d'état d'arrêt et ne peut donc pas simuler une machine qui s'arrête, au moins dans le sens standard de ce que fait une machine Turing universelle.

David Richerby

2

@DavidRicherby: Je pense que la faible universalité de la règle 110 est tout à fait acceptée: elle nécessite deux mots différents répétés à gauche et à droite de l'entrée, et la condition d'arrêt est la génération d'un planeur spécial (généré si et seulement si la machine simulée s'arrête). Voir "L'universalité dans les automates cellulaires élémentaires" de Matthew Cook.

Marzio De Biasi

-4

une question générale mal formulée mais raisonnable qui peut être étudiée de plusieurs manières techniques particulières. il existe de nombreuses "petites" machines mesurées par des états / symboles où l'arrêt est inconnu mais aucune "plus petite" machine n'est possible à moins que l'on ne trouve une mesure justifiable / quantifiable de la complexité d'une MT qui prend en compte à la fois les états et les symboles (apparemment personne n'en a proposé jusqu'à présent).

$x \times y$ $x$ $y$

$x,y$

vzn
la source

2

Il n'est pas nécessaire d'établir une métrique prenant en compte les symboles et les états. Une fois qu'il y a deux symboles sur la bande, il est clair que le problème d'arrêt est indécidable pour presque tous les nombres d'états - si je me souviens bien, il est possible d'écrire une MT universelle avec seulement cinq états. Si nous connaissions la frontière exacte de la décidabilité, je suis sûr qu'il serait facile de décrire cette frontière en termes de (# états, # symboles) paires.

David Richerby

la recherche sur les castors occupés implique en effet de trouver des preuves pour savoir si les MT s'arrêtent pour les configurations initiales avec un petit nombre d'états, de symboles; il y a des cas résolvables. si l'on veut le "plus petit", il faut créer une métrique précise qui mesure le "petit". le point ci-dessus est qu'une métrique qui n'implique que des états ou des symboles seuls peut être considérée comme trompeuse dans la mesure où elle représente la frontière connue qui implique à la fois (et les machines qui ne sont pas connues pour être universelles). la limite d'indécidabilité dans cette recherche n'est pas "facile" à spécifier en termes de quoi que ce soit, c'est sa nature fondamentale ....

vzn

1

2 \leq i \leq 4

$2\leq i\leq 4$

k_{i}

$k_i$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

David Richerby

jusqu'à présent, personne n'a proposé de métrique. aucune frontière importante dans ce domaine n'est "triviale à décrire" et l'on pourrait s'attendre à ce qu'un scénario soit impossible via Rices thm. cela semble montrer un manque de familiarité avec la recherche et la référence citée qui s'intéressent à la résolvabilité des entrées pour des machines plus petites que celles connues pour être universelles (et supposées ne pas être universelles). vos commentaires semblent se concentrer sur les limites de machine universelles vs non universelles, ce qui n'est pas le même que les limites de décidabilité des castors occupés explorées, par exemple dans les références citées (à la fois ci-dessus et Marzio).

vzn

x

$x$

y

$y$

x

$x$

y

$y$

Quelle est la plus petite machine de Turing où l'on ne sait pas si elle s'arrête ou non?

Réponses: