révéler l'existence de TM qui accepte la langue suivante

Question

J'ai une idée de la façon d'aborder le problème, mais je ne suis pas sûr de cela. Compte tenu d'une machine de Turing, je peux vérifier le nombre d'états que la machine a, et par le nombre d'états de savoir si la course utilise des cellules sans fin de la bande. Cependant, je ne sais pas comment je peux utiliser le nombre d'états et ce que je devrais vérifier. Ce qui me confond est que la saisie d'une boucle sans fin ne nécessite pas nécessairement l'utilisation de cellules sans fin du film.

$ l_k={ |\, M \, \, \, est \, \, a \, \, tm \, \, \, \, utilise \, \, \, \, la plupart \, \, k \, \, k \, \, k \, \, ruban adhésif\, \, cellules \, \, \, quand \, \, \, exécutant \, \, \, \, \, \ \, \, \ epsilon \} $

prouver que: $ l ^ *=bigcup \ limites_ {k \, \ in \, \ mathbb {n}} l_k \, \ in \, \, \, re \ setminus r $

Answer 1

la langue $ l ^ * $ se compose de toutes les machines Turing $ M $ éventuellement arrêtéou répétez une configuration.Pour chaque machine $ M $ , en simulant la machine, vous pouvez facilement observer que l'une de ces possibilités est arrivée.