Algunas preguntas sobre la computabilidad de las máquinas de Turing.

Question

Estoy aprendiendo para una prueba y tengo algunas preguntas importantes sobre la computabilidad de las máquinas de Turing deterministas y deterministas.

Considere que tenemos las funciones parciales $ f, g, h, t: \ mathbb {n} \ righgarrow \ mathbb {n} $ con $ f $ es la máquina de Turing computable, $ g $ no turing máquina computable, $ H $ no está a la altura de Solvable y $ t $ es computable. ¿Son correctas las siguientes respuestas? ¿Y hay algo que cambie si tuviéramos un TM no determinista?

No hay pruebas para hacer las palabras están bien :)

1. es $ F \ Circ G $ Turing Machine computable?
2. es $ g \ circ f $ Turing Machine computable?
3. es $ t \ circ h $ mientras computable?
4. es $ h \ circ t $ mientras computable?

Mis respuestas:

En primer lugar, sabemos que la máquina de Turing= mientras que la computabilidad. (#)

1. Yo diría que no sabemos si es o no es TM computable, porque puede que puede manejar la salida de una función computable NO TM.

2. Yo diría que no, porque si lo que sea $ g $ toma, no será computable TM.

3. y 4. debido a (#) es lo mismo como 1. y 2.

podría ser correcto? Es para una prueba de opción múltiple y esas preguntas son complicadas.

Answer 1

La respuesta es "No sabemos sin más información" para los 4.

Supongamos $ f $ es la función de identidad $ f (x)= x $ . Luego $ F \ CIRG= G \ CIRF= G $ , que no es computable.

Por otro lado, supongamos que $ g $ es un total no computable (que es un caso especial de $ g $ siendo una función no computable no computable), y supongamos $ f $ es La función cero constante $ f (x)= 0 $ . En este caso:

• $ F \ Circ G $ es la función cero constante, que obviamente es computable.
• $ g \ circ f $ es también una función constante. No necesariamente no conocemos cuál es la constante , pero eso no importa; Cada función constante es computable. Vea ¿Cómo puede ser decidible? Ya sea $ \ pi $ tiene alguna secuencia de dígitos?

La máquina de Turing determinista vs. no determinista no afecta la respuesta, porque una máquina de Turing determinista puede simular la ejecución de una máquina de Turing no determinista (potencialmente con una desaceleración exponencial) por Docetailing .