Chaque langage récursif est-il reconnu par une machine mortelle de Turing?

Nous disons qu'une Turing Machine est mortelle si s'arrête pour chaque configuration de départ (en particulier, le contenu de la bande et l'état initial peuvent être arbitraires). Chaque langage récursif est-il reconnu par une machine de Turing mortelle? (c'est-à-dire s'il y a une MT qui accepte , il y a aussi une TM mortelle qui accepte ) $M$ $M$ $L$ $L$

computability Marcin Kotowski
la source

Pouvez-vous faire référence à la Mortal Turing Machines? Merci :)

Tayfun Pay

Comment se fait-il que l'état initial puisse être arbitraire? Une machine de Turing mortelle n'est-elle pas juste une MT qui s'arrête à chaque entrée?

Philip White

@Marcin: êtes-vous intéressé par les machines qui s'arrêtent sur toutes les configurations, y compris infinies, ou simplement celles qui s'arrêtent sur toutes les configurations finies ?

Joshua Grochow

Je pense qu'il veut dire des configurations de départ finies. Droite?

Philip White

@Philip: Imaginez simplement la machine dans un état et une configuration arbitraires, puis exécutez le calcul vers l'avant à partir de ce point en suivant les règles habituelles.

Joshua Grochow

Réponses:

Voici deux résultats cités dans Charles E. Hughes "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators" :

Théorème 3 : La classe des machines de Turing mortelles est exactement la classe des machines de Turing à temps de fonctionnement constant.

st pour toutes les configurations initiales , s'arrête en pas plus de étapes $ConstT = \{ M \mid \exists s$ $C$ $M$ $s$ $\}$

Je pense donc que nous pouvons déduire ce qui suit: étant donné une machine de Turing mortelle , soit le temps constant TM correspondant et son temps de fonctionnement. La langue reconnue par sur l'alphabet est exactement: $M$ $M', s$ $M$ $\Sigma = \{0,1\}$

{X y ∣ | X | \leq s \land M^{'} accepte X en pas plus de s étapes, y \in {0, 1}^{*}}

$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$

Ainsi, la classe des langues reconnues par les machines mortelles de Turing est un sous-ensemble approprié de la classe des langues régulières. Par exemple, vous pouvez utiliser pour tromper chaque temps constant TM. $L = \{(0|1)^*1^*\}$

Les choses deviennent intéressantes lorsque nous essayons de décider si une machine de Turing est mortelle parce que nous devons faire face à une bande et à un état arbitraires (finis) initiaux.

Théorème 4 : l'ensemble des machines mortelles de Turing est récursivement énumérable.

Marzio De Biasi
la source

Je pense que oui. Nous devons faire pour chaque L un M qui l'accepte de telle manière que tous ses mouvements soient enregistrés sur une bande et après chaque "étape principale" il vérifie si toutes ses étapes jusqu'à ce point étaient vraiment valables. Ci-dessous, je donne un aperçu de la façon dont une telle machine devrait être fabriquée (qui pourrait contenir quelques erreurs mineures mais l'idée principale devrait être bonne).

Désignons une machine qui accepte L par T. Maintenant, nous décrivons M. Premièrement, nous copions x sur une bande de mémoire séparée. Ensuite, chaque fois que T ferait un mouvement, nous l'écrivons sur cette bande mémoire, après x. Après cela, nous copions tout le contenu des bandes de T dans des bandes de travail supplémentaires et vérifions si, à partir de la configuration de départ, T atteindrait vraiment son état actuel après les étapes enregistrées sur la bande de mémoire. Sinon, nous nous arrêtons. Si oui, nous continuons.

domotorp
la source

en écrivant ma réponse, j'ai lu la vôtre ... qui dit le contraire :-) ... peut-être que j'interprète à tort ce qu'est une chaîne acceptée par une machine mortelle de Turing?

Marzio De Biasi

@MarzioDeBiasi: La notion de mortel considérée dans ce document nécessite un arrêt de la machine en un nombre fini d'étapes même si elle est démarrée avec une quantité infinie de données arbitraires sur sa bande. Mais je pense que la construction de domotorp fonctionne pour la plupart des configurations finies. Par exemple, dans une configuration avec une entrée de longueur infinie, le M de domotorp est pris dans une séquence infinie de copie de l'entrée de longueur infinie sur la bande de mémoire séparée ...

Joshua Grochow

Oui, la différence est que je supposais que chaque contenu de bande est fini et nous savons où sont les limites. Sinon, les MT mortelles sont juste constantes, comme vous écrivez.

domotorp