alfabeto infinita máquina de Turing

Question

es una máquina de Turing que se le permite leer y escribir símbolos de un alfabeto infinita más potente que un TM regular (que es la única diferencia, la máquina todavía tiene un número finito de estados)?

La intuición me dice que no, ya que se necesita un número infinito de estados para diferenciar cada símbolo. Así que creo que algunos de los símbolos o las transiciones provocadas por los símbolos (o algunos subconjuntos de las transiciones) tienen que ser equivalentes. Así que en realidad se puede simular su máquina con una TM regular y un subconjunto acotado de tales símbolos o transiciones.

¿Cómo podría acercarse a una prueba formal de esto?

Answer 1

No, sería más potente. La función de transición ya no sería finito, y que te compra una gran cantidad de energía.

Con un alfabeto infinita, se puede codificar cualquier elemento de entrada de un conjunto infinito en un símbolo (aunque el conjunto de entrada no puede ser "más infinito" que el conjunto de alfabeto, por ejemplo, el alfabeto sería presumiblemente única infinito numerable, por lo elementos del conjunto no numerable gustan los números reales no podían ser representados en un símbolo). Y lo mismo para la salida.

Así que usted puede hacer una de dos estados (uno inicial, se aceptan) infinita-alfabeto-TM con una única transición que se mueve a la aceptan estado y cambia el símbolo debajo de la cabeza de la cinta de acuerdo con la función que está intentando computar. Esta receta le permitiría calcular ninguna asignación entre los conjuntos que se pueden poner en una correspondencia uno-a-uno con el alfabeto.

Así que para evitar ese tipo degenerado de la máquina es la respuesta a todo, que había necesidad de restringir lo que la función de transición puede hacer. Una obvia sería exigir la función de transición en sí para ser computable (funciones de transición de TM ordinaria son trivialmente computable después de todo, ya que son finitos). Pero entonces usted estaría intentando utilizar las funciones computables para definir su modelo de funciones computables.

Answer 2

La respuesta anterior es correcta, pero hay un poco más de lo que puede decirse acerca de los alfabetos infinitos y computabilidad.

Una máquina de Turing se describe en el documento WP como $ M = (Q, \ Gamma, b, \ sigma, \ delta, q_0, q_f) $ en la que todos los conjuntos son finitos. Por lo tanto la función de transición $$ \ delta: Q / F \ veces \ Gamma \ rightarrow Q \ veces \ Gamma \ veces \ {L, R \} $$ es necesariamente finita.

En una máquina alfabeto infinita nos reemplazar el alfabeto de entrada $ \ sigma $ por ejemplo $ \ Sigma ^ {inf} $ y así el alfabeto de cinta por $ \ Gamma ^ {inf} $ y la función de transición por $ \ delta ^ {inf} $ obedecer:

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

Así que $ \ delta ^ {inf} $ es necesariamente una función infinita. Como se señalaba si esta función es ser no computables, a continuación, lo anterior no es representable finito. Supongamos que vamos a mantener $ \ delta ^ {inf} $ recursiva (parcial) si es posible. La pregunta es si el alfabeto siempre va a permitir esto.

La cuestión básica es que un alfabeto finito se presenta en su totalidad (por lo que podemos optar por definir nuestras funciones de forma recursiva), pero un alfabeto infinita nunca puede ser presentado en su totalidad. Entonces, ¿qué mecanismo está generando el alfabeto?

La forma más sencilla de considerar esto es imaginar que hay un alfabeto finito "núcleo", por ejemplo, $ A = \ {a, b \} $. A continuación, generar un lenguaje $ L \ subconjunto A ^ * $. Supongamos que la cadena abaab $ \ in L $. A continuación, defina $ \ alpha = \ in \ Gamma ^ {inf} $. Por lo que el alfabeto infinita consiste en juegos de cuerdas de $ L $ concatenados en un solo símbolo como $ $.

El más simple, tales alfabeto es básicamente <1 *> , el lenguaje ordinario en el que cualquiera de los dos símbolos se distinguen por contar el número de trazos verticales en cada símbolo. Esta será computable con un analizador de estados finitos (como LBA sin embargo, no como autómatas finitos). Turing abogado por un alfabeto finito para evitar cualquier apariencia de una operación no finito en una operación de TM. Sin embargo vale la pena señalar que las 26 letras del alfabeto Inglés no siguen este patrón de conteo: letra z no contiene 26 trazos o puntos ni nada. Así otros patrones son posibles con el modelo computacional en general más que en base a una recursivamente numerable (R. E.) idioma $ L $.

El problema aquí es que aunque la construcción de $ \ delta ^ {inf} $ no será posible a menos que se proporciona explícitamente la definición de $ L $. Esto es en parte debido a la equivalencia de R.E. conjuntos es indecidible y en parte porque de lo contrario sólo tenga una muestra finita de trabajar y no podemos inferir $ L $ de eso. Si tenemos la definición de $ L $ (y por lo tanto $ \ Gamma ^ {inf} $) entonces si $ f $ es recursivo en $ \ Gamma ^ {inf} $ entonces $ f $ es recursiva en un finito, por lo que $ f $ es absolutamente recursiva y $ \ delta ^ {inf} $ puede ser recursiva.

Finalmente se considera el caso de que $ L $ no es R. E. con dos ejemplos:

Ejemplo 1 . $ \ in \ Gamma ^ {inf} $ si y sólo si $ \ phi_ {n} (n) $ demostrablemente diverge. En este caso el alfabeto $ \ Gamma ^ {inf} $, obviamente, no tiene una descripción finita - en vez de eso se "crecer" con el tiempo (y sólo ser plenamente definida en un límite de cómputo). Pero entonces es un alfabeto infinita que no puede ser presentada a la vez en cualquier caso. Así que si $ f $ es recursivo en $ \ Gamma ^ {inf} $, entonces f es de $ \ Delta_2 ^ $ 0 - Detener el conjunto. Así que $ \ delta ^ {inf} $ no puede ser recursiva.

Ejemplo 2 . Un ejemplo más geométrico considera Penrose-como Tiles . Dejar que el símbolo $ S \ in \ Gamma ^ {inf} $ si $ S $ es una unidad de N azulejos aperiódicas, que demostrablemente puede embaldosar el plano. Este alfabeto es infinito ya que uno puede construir, para cualquier N, una unidad de N-teja de baldosas de Penrose. Sin embargo embaldosado el avión en sí es indecidible, por lo que el conjunto de S crecerá a medida que más fichas como este se descubren. Una posible $ f $ recursiva en $ \ Gamma ^ {inf} $ pero no absolutamente recursiva podría ser f (S) = número de fichas en S.