PROBLEMA DE DETENER DE DETENER PARA LA MÁQUINA FIJATE Y ENTRADA FIJA

Question

Se sabe que el problema de detención no es indecidible incluso cuando nos arreglamos ya sea la máquina de Turing $ M $ o la entrada $ w $ .

¿Qué pasa si fijamos tanto la máquina y la entrada?Es decir, es decidible para cada máquina de turing fijo $ m_0 $ y cada entrada fija $ w_0 $ que $ M_0 $ se detendrá en $ w_0 $ como entrada?

Answer 1

Se sabe que el problema de detención no es indecidible incluso cuando nos arreglamos ya sea la máquina de Turing $ M $ o la entrada $ w $ .

Tienes que tener más cuidado con esta declaración. No es cierto para cualquier máquina de Turing fijo $ m $ que el problema de detención $ \ texto {halt} _m $ (Decidir sobre la entrada $ w $ si $ m $ se detiene en $ w $ ) es indecidible. Por ejemplo, si $ m $ es una máquina que siempre se detiene, podemos decidir fácilmente $ \ texto {halt} _m $ Simplemente mediante la salida "SÍ".

Lo que probablemente quise decir es los siguientes hechos, que son verdaderos:

1. Existe una máquina de Turing $ m $ de tal que el problema $ \ text {halt} _m $ (Decidir en la entrada $ w $ si $ m $ Se detiene en $ w $ ) es indecidible.

2. para todas las palabras palabras $ w $ , el problema $ \ texto { Halt} _W $ (Decisión de entrada $ m $ si $ m $ se detiene en < Span Class="Math-contenedor"> $ W $ ) es indecidible.

En particular, de hecho, podemos tomar $ m $ para ser la máquina de turing universal.

¿Qué pasa si fijamos tanto la máquina y la entrada? Es decir, es decidible para cada máquina de turing fijo $ m_0 $ y cada entrada fija $ w_0 $ que < Span Class="Math-Container"> $ M_0 $ se detendrá en $ w_0 $ como entrada?

Sí, el problema se vuelve trivialmente decidible. Definir el idioma $ \ texto {halt} _ {m_0, w_0} $ Para ser el problema de decidir si $ m_0 $ Detenerse en $ w_0 $ . Pero observe que este problema ya no tiene ningún ingreso de que la respuesta depende, como ambas cosas que la respuesta pueda depender de ( $ m_0 $ y $ W_0 $ ) ahora se fijan, es decir, parte de la definición de idioma, no parte de la entrada. Eso significa que la respuesta es solo "sí" o "no". Para que podamos decidir este problema utilizando un programa que siempre dice "sí", o un programa que siempre dice "no".

Esta es una trampa común sobre la decidabilidad: es útil preguntar si un problema es decidible o no cuando el número de entradas posibles es infinito. Si solo hay finamente muchas entradas posibles, entonces Todos los problemas se vuelven decidibles. Ha preguntado si un problema con solo 1 entrada posible (la entrada vacía) es decidible, y la respuesta a eso es siempre sí.