Turing reconnaissable => énumérable

10

J'obtiens la preuve de passer d'un énumérateur à une machine de Turing (continuez à exécuter l'énumérateur et voyez si cela correspond à l'entrée) mais je ne vois pas comment fonctionne l'autre sens.

Selon mes notes et le livre (Intro to the Theory of Computation - Sipser), pour obtenir l'énumérateur Turing à partir d'une machine Turing, nous écrivons essentiellement toutes les combinaisons de l'alphabet. Vous exécutez ensuite la MT sur cette entrée, si elle accepte de l'imprimer, remplacez-la par une nouvelle chaîne répétée à l'infini.

Le problème que j'ai est sûrement que cela nécessite que la langue soit décidable. Sinon, il pourrait rester bloqué sur le troisième mot dans une boucle infinie vouée à ne jamais accepter ou rejeter et certainement pas à imprimer la langue entière.

Qu'est-ce que je rate?

T. Kiley
la source

Réponses:

9

MMMM

w1,S1##wn,SnwiSiMwinMwi

Exécutez maintenant la boucle suivante

  1. wΣSM#w,S
  2. M
  3. MM
  4. MM
  5. Passez à l'étape 1.

wΣM

Dave Clarke
la source
4
alias "queue d'aronde".
Kaveh