Problemas de la máquina universal de Turing

Question

Si tengo una máquina, lo llaman la máquina 1, que es capaz de resolver un problema: es sólo una máquina, no es per se una máquina de Turing. Se puede resolver un problema específico. Si este mismo problema puede ser resuelto en una máquina universal de Turing, pues, es mi máquina original, 1, una máquina universal de Turing también?

Esto no se sostiene para todos los problemas, que ya está ansered. ¿Hay problemas que tienen esta propiedad se describen en absoluto? Si no es absolutamente cierto, entonces ¿por qué?

Puede alguien dar un ejemplo de un problema que hay que resolver. Si este problema se resuelve por mi máquina original, 1, definitivamente hace que esta máquina de torneado universal? ¿O es que no existe un problema de este tipo? Si no existe, ¿por qué?

Me interesa mucho, pero no puedo entenderlo ... Gracias.

Editar:. Hizo la pregunta más clara

Answer 1

El punto del torneado universal de la máquina (UTM) es que para cualquier máquina de Turing (TM) se puede tomar que la MT y crear una codificación por ello que describe el funcionamiento de la TM y tienen que codificar son de otro TM.

El UTM es un TM que tiene una definición suficientemente potente de tal manera que cualquier otra definición TM podría ser reescrita en ella.

Piense en la UTM como intérprete. El TM es una tarea específica.

A menos que la TM es también en la clase de los intérpretes, entonces no es una UTM también. (Debido a que un UTM es también un TM tarea específica).

Así que para responder a la segunda pregunta: si usted puede demostrar que la UTM y TM son equivalentes, entonces usted ha demostrado que TM es también una UTM. Para ello, tiene que ser capaz de mostrar cómo un programa codificado para la UTM se puede cambiar en un programa equivalente para la TM.

Answer 2

Una máquina universal de Turing puede resolver cualquiera de una gran clase de problemas.

Si la máquina (1) puede resolver 1 + 1, eso no quiere decir que puede resolver cualquiera de la enorme clase. Por lo tanto, no puede ser un universal máquina de Turing.

Answer 3

Los lógicos diferencian entre condiciones "neccessary" "suficiente" y. Tomemos, por ejemplo, la sentencia

  

El cielo es azul.

(vamos a asumir que siempre es cierto). Lo que sabe ahora es la siguiente:

  

Cuando nos fijamos en el cielo, se ve el color azul.

Lo que No saber es lo siguiente:

  

Cuando vea el color azul, que está mirando al cielo.

-. Que también podría estar buscando en el coche de su vecino

En términos lógicos, el color azul es neccessary para el cielo, pero no es suficiente.

Lo mismo es cierto para su caso: Máquina (1) no resolver su problema, por lo que es de hecho un problema solucionable. Por lo tanto, ser capaz de resolver el problema es un neccessary condición para una UTM, pero no suficiente, porque un UTM debe ser capaz de resolver cualquier problema (que es solucionable en todos), no sólo por esta sola.

Answer 4

Una máquina universal de Turing puede resolver cualquier código que cualquier máquina de Turing puede resolver específica.

Así que su máquina universal de Turing (2) puede resolver el problema de que su máquina de Turing original (1) fue diseñado para resolver.

La máquina de Turing original (1), sin embargo sólo se puede resolver ese problema exacto y no puede resolver cualquier otro problema (incluido el "problema" de ser una máquina universal de Turing).

Así que no, la máquina de Turing original no es una máquina de Turing universal de acuerdo a su descripción. (Podría ser si el usted lo define, pero eso es algo de trampa).

Answer 5

  

Puede alguien dar un ejemplo de un problema que hay que resolver.

Claro:. Dado codificado máquina y datos de torneado, ¿cuál es el resultado :) Si su máquina puede resolver este problema, es sin duda UTM

¿Usted sabe la línea de razonamiento por qué esos problemas están en diferentes NP? Al igual que 'puedo solucionar el problema 3-sat cuando tengo una máquina que resuelve el problema de Hamilton? Seguramente se puede utilizar el mismo para responder a su pregunta.

Answer 6

La demostración de la Turing completo de un sistema en particular no es trivial, a menos que usted puede fácilmente demostrar que es equivalente / isomorfo a otro sistema que se conoce para ser Turing completo. Así que la respuesta corta: no existe una prueba sencilla que se puede poner la máquina a través de comprobar si es Turing completo. Hay que analizar y mostrar las propiedades del sistema en su conjunto.

Si desea obtener más información sobre este tema, lea estos artículos sobre Turing integridad y teoría de la computabilidad .

Answer 7

Imagine un UTM como si ¿cómo proceder si usted tiene que escribir un código (de alto nivel) para simular el machine.You turing requerirá lo siguiente: 1.Array para mantener los símbolos de entrada y la materia que Yiu haría en él. array 2.An (posible 2-d) para mantener la función de transición que va a solicitar al usuario. algoritmo 3.An que leer las entradas del usuario de funciones de transición y simula que en la matriz de 1. las variables 4.Few que su programa tendrá que realizar un seguimiento de su propio estado.

Si cree que de esta manera, si se llega a un código perfecto estado de funcionamiento se termina con un UTM perfecto. Sin embargo, el problema es no importa qué tan eficiente que el código no se puede dejar que el usuario entre en funciones de transición que puede hacer que su código se ejecute forever.So habrá ciertos problemas para los que se producirá un error UTM, y entonces se dice que para esos problemas no podemos desarrollar una máquina de ensayos de miembros. (aunque aviso de una máquina de verificación de miembro es siempre posible)