¿Es una máquina de Turing sin la capacidad de escribir en celdas en blanco menos potente que Turing estándar?

¿Es una máquina de Turing sin la capacidad de escribir en celdas en blanco menos potente que Turing estándar?

Creo que la respuesta es sí, pero no puedo encontrar un cálculo que la máquina estándar de Turing pueda hacer, pero esta máquina no.

¿Algunas ideas?

En otras palabras, " ¿sería una computadora con memoria limitada menos poderosa que una computadora con memoria ilimitada "?

Nat

Respuestas:

El tipo de máquina de Turing que describe es un autómata lineal (solo puede escribir en las partes de la cinta que contiene la entrada). Los LBA son los que aceptan los lenguajes sensibles al contexto, por lo que para encontrar un ejemplo específico de un problema que no se pueda resolver con esta restricción pero que se pueda resolver en general con una máquina de Turing, solo necesita un lenguaje que sea decidible pero no contextual. sensible.

El ejemplo dado en Wikipedia es:

Un ejemplo de lenguaje recursivo que no es sensible al contexto es cualquier lenguaje recursivo cuya decisión es un problema difícil de EXPSPACE, por ejemplo, el conjunto de pares de expresiones regulares equivalentes con exponenciación.

Para obtener más ejemplos, consulte ¿Hay un ejemplo de un lenguaje recursivo que no sea sensible al contexto?

roctothorpe
fuente

$\textsf{DSPACE}(O(n))$

ordenación rápida
fuente

¿No puede simplemente proporcionar un sufijo suficientemente largo, para cualquier problema dado, de símbolos especiales al final de la cinta que pueden usarse como espacios en blanco?

gen

@gen No en general. En el caso más general, solo tenga en cuenta que conocer un sufijo tan largo haría que el problema de detención sea decidible. En consecuencia, calcular un prefijo suficientemente largo puede ser indecidible, en general, por lo que no es razonable suponer que se proporciona dicho sufijo.

chi

¿Sería exacto interpretar esta respuesta como: " Las máquinas de Turing con memoria limitada no tendrán suficiente memoria para ejecutar ningún programa arbitrario, ya que algunos programas pueden requerir más memoria de lo que sea que tengan "?

Nat

@Nat: Yo lo expresaría como "la cantidad de memoria que puede requerir un programa es generalmente desconocida hasta que se ejecuta el programa". Lo curioso (una gran paradoja matemática) es que para cualquier triplete entero X, Y, Z, existe un límite superior para la cantidad de celdas de cinta necesarias para los programas que terminarán y que contienen en la mayoría de los estados X, en cintas que pueden contener en la mayoría de los tipos de símbolos Y, y se inicializan con símbolos Z en la cinta, pero ningún límite superior es demostrable, excepto los valores triviales de X, Y y Z.

supercat