Infini alphabet Machine de Turing

Question

est une machine de Turing qui est autorisé à lire et à écrire des symboles d'un alphabet infini plus puissant qu'un TM régulier (qui est la seule différence, la machine a encore un nombre fini d'états)?

Intuition me dit pas, puisque vous avez besoin d'un nombre infini d'états pour différencier chaque symbole. Je pense donc que quelques-uns des symboles ou des transitions causées par les symboles (ou des sous-ensembles des transitions) doivent être équivalentes. Ainsi, vous pouvez effectivement simuler cette machine avec un TM régulier et un sous-ensemble borné de ces symboles ou des transitions.

Comment pourrais-je aborder une preuve formelle de cette situation?

Answer 1

Non, il serait plus puissant. La fonction de transition ne serait plus finie, et que vous permet d'acheter un lot de pouvoir.

Avec un alphabet infini, vous pouvez coder tout élément d'entrée d'un ensemble infini dans un symbole (bien que le jeu d'entrée ne peut pas être « plus infinie » que l'ensemble de l'alphabet, par exemple l'alphabet serait sans doute que dénombrable, donc éléments d'ensembles indénombrables comme les nombres réels ne pouvaient pas être représentés dans un symbole). Et de même pour la sortie.

Vous pouvez faire un à deux états (une première, on accepte)-alphabet-TM infini avec une seule transition qui se déplace vers l'acceptent état et change le symbole sous la tête de bande conformément à la fonction que vous essayez pour calculer. Cette recette vous permettra de calculer une correspondance entre des ensembles qui peuvent être mis dans une à une correspondance avec l'alphabet.

Donc, pour éviter ce genre dégénéré de la machine étant la réponse à tout, vous auriez besoin de limiter ce que la fonction de transition peut faire. Une évidente serait d'exiger que la fonction de transition lui-même être calculable (fonctions de transition TM ordinaires sont trivialement calculable après tout, car ils sont finis). Mais alors vous essayer d'utiliser les fonctions calculables pour définir votre modèle de fonctions calculables.

Answer 2

La réponse ci-dessus est correct, mais il y a un peu plus que l'on puisse dire alphabets infinis et calculabilité.

A Turing machine est décrite dans le document WP comme $ M = (Q, \ Gamma, b, \ Sigma, \ delta, Q_0, q_f) $ dans laquelle tous les jeux sont finis. Ainsi, la fonction de transition $$ \ delta: Q / F \ Temps de Gamma \ Q \ Temps de Gamma \ times \ {L, R \} $$ est nécessairement finie.

Dans une machine alphabet infini nous remplacer l'alphabet d'entrée $ \ Sigma $ par exemple $ \ Sigma ^ {inf} $ et ainsi de l'alphabet de bande par $ \ Gamma ^ {inf} $ et la fonction de transition par $ \ delta ^ {inf} $ nous devons respecter:

$$ \ ^ {delta} inf: Q / F \ times \ Gamma ^ {inf} \ rightarrow Q \ times \ gamma ^ {inf} \ times \ {L, R \} $$

$ \ delta ^ {} $ est inf nécessairement une fonction infinie. Comme le fait remarquer si cette fonction est d'être non calculable, alors ce qui précède n'est pas représentable finiment. Supposons que nous garderons $ \ delta ^ {inf} $ (partielle) récursive si possible. La question est de savoir si l'alphabet sera toujours permettre.

La question de base est qu'un alphabet fini est présenté dans son intégralité (afin que nous puissions choisir de définir nos fonctions récursive), mais un alphabet infini ne peut jamais être présenté dans son intégralité. Alors, quel mécanisme génère l'alphabet?

La façon la plus simple de considérer ceci est d'imaginer qu'il ya un alphabet "noyau" de fini, disons $ A = \ {a, b \} $. Ensuite, générer un langage $ L \ subset A ^ * $. Supposons que la chaîne Abaab $ \ en L $. Définissez ensuite $ \ alpha = \ in \ Gamma ^ {} $ inf. Ainsi, l'alphabet infini se compose d'ensembles de cordes de $ L $ concaténés en à symbole comme $ $.

Le plus simple comme alphabet est fondamentalement <1 *> , la langue régulière dans laquelle les deux symboles se distinguent en comptant le nombre de traits verticaux dans chaque symbole. Ce sera calculable avec un analyseur d'états finis (comme si LBA, non pas comme un automate fini). Türing plaidé en faveur d'un alphabet fini pour éviter toute apparence d'une opération non finie dans une opération de TM. Cependant, il est intéressant de noter que les 26 lettres de l'alphabet anglais ne suivent pas ce modèle de comptage: lettre z ne contient pas 26 coups ou des points ou quoi que ce soit. Ainsi, d'autres modèles sont possibles avec le plus de calcul général modèle qui repose sur un langage $ L récursivement énumérable (R.E.) $.

Le problème ici est que si la construction $ \ delta ^ {} $ inf ne sera pas possible à moins que la définition est expressément prévu $ L $. Ceci est en partie parce que l'équivalence des R.E. ensembles est indécidable et en partie parce que sinon nous ne jamais avoir un échantillon fini de travailler avec et ne peut pas déduire $ L $ de cela. Si nous avons la définition de $ L $ (et donc $ \ Gamma ^ {inf} $) alors si $ f $ est récursif $ \ Gamma ^ {inf} $, alors $ f $ est récursifs dans un ensemble fini, et donc $ f $ est absolument récursive et $ \ delta ^ {inf} $ peut être récursive.

Enfin, nous considérons le cas que $ L $ est pas R.E. avec deux exemples:

Example1 . $ \ in \ Gamma ^ {} $ inf ssi $ \ Phi_ {n} (n) $ prouvablement diverge. Dans ce cas, l'alphabet $ \ Gamma ^ {} $ inf aura évidemment pas une description finie - elle sera plutôt « grandir » au fil du temps (et être lui-même que dans une définition entièrement limite de calcul). Mais il est un alphabet infini qui ne peut être présenté à la fois dans tous les cas. Donc, si $ f $ est récursif $ \ Gamma ^ {} $ .inf, alors f est en $ \ Delta_2 ^ 0 $ - l'ensemble Enrayer. Alors $ \ delta ^ {} $ .inf ne peut pas être récursive.

Example2 . Un exemple plus géométrique considère Penrose comme Tiles . Laissez symbole $ S \ in \ Gamma ^ {} $ si inf $ S $ est une unité de N tuiles apériodiques démontrable peut paver le avion. Cet alphabet est infini car on ne peut construire, pour tout N, une unité N-tile de tuiles Penrose. carrelage Cependant, le plan lui-même est indécidable, de sorte que l'ensemble de S augmentera à mesure que plus de tuiles comme celui-ci sont découverts. Un possible $ f $ récursive en $ \ Gamma ^ {inf} $, mais pourrait absolument être récursive f (S) = nombre de tuiles en S.