Quiero determinar si este problema de decisión es decidible. He intentado establecer reducciones de Alto y "Acepta cadena vacía", pero aún no he encontrado una solución.
¿Alguien me puede ayudar?
computability
turing-machines
undecidability
Shuzheng
fuente
fuente
Respuestas:
Yo diría que es decidible.
Si entendí correctamente, esto es lo que pienso.
En primer lugar, una TM comienza desde algún estado inicials0 0 . ¿Cómo puede cambiar el estado? En tu función de transición tienes algo como(s0 0, x ) → (syo, y, M ) dónde syo es un estado y X , y son símbolos y metro es el movimiento de la cabeza (izquierda derecha o quedarse). Entonces, si sale del estado inicial, debería haber una transición de(s0 0, _ ) a algún estado no s0 0 . Es fácil ver que es si y solo si. Por lo tanto, puede construir otra máquina de Turing que tenga la entrada como TM en alguna codificación, pase por la función de transición y verifique la condición anterior, y el problema es decidible.
fuente
Trivialmente decidible. Dado que la cinta está realmente en blanco, entonces T en estados0 0 debe cambiar la celda de cinta actualmente escaneada y hacer una de tres cosas: (1) Transición a un estado diferente y moverse hacia la izquierda o hacia la derecha (o detener); (2) Transición de regreso as0 0 y mover una celda a la izquierda; (3) Transición de regreso as0 0 y mover una celda a la derecha. Para ambos (2) y (3) el cabezal TM se ha alejado de la celda de cinta original y ahora está escaneando una celda en blanco; por lo tanto, ahora está en la misma situación en la que comenzó y actuará de la misma manera. Entonces, para (2) o (3) el comportamiento de TM en una cinta en blanco es moverse para siempre en una dirección, dejando un rastro de (probablemente) células alteradas. Por lo tanto, esta propiedad se puede verificar inspeccionando el contenido de una sola fila del 'programa' de TM (es decir, la regla de transición paras0 0 escaneo en blanco) - si el nuevo estado NO es s0 0 (incluyendo 'paradas') la respuesta es SÍ, de lo contrario la respuesta es NO.
También estoy razonablemente seguro de que el problema aún es decidible dada la entrada arbitraria: solo debe prestar más atención a la dirección en la que se mueve el cabezal de la cinta dependiendo del contenido actual de la celda.
fuente