Un "innumerables" Máquina de Turing?

Question

Una prueba de la insolubilidad de la detención problema es una de diagonalización, que estoy seguro que la mayoría de ustedes han visto. No estoy muy familiarizado con la teoría de conjuntos, pero se me ocurre que es similar a la de Cantor de la prueba de la falta de bijection entre los reales y los números naturales.

Puede esta analogía se estira? Si pudiéramos diseñar una máquina que aceptó que "más" entradas, podría resolver la suspensión problema (para los contables TMs)?

Si es así, ¿por qué permitimos que los TMs con entradas contables para definir lo que es computable?

Answer 1

Se hicieron dos preguntas. La primera es si una máquina con "más entradas" podrían ser capaces de resolver la paralización problema para el clásico de máquinas de Turing. Que es un poco vago, pero la consecuencia vaga respuesta es no. Para "resolver" la detención problema significa para calcular una función de$\mathbb{N}$$\mathbb{N}$. Sólo el comportamiento de la persona en estos insumos relevantes; si el solucionador también podría aceptar otros insumos, es difícil ver cómo afectaría a nada. Con el fin de resolver la paralización problema en un número finito de pasos, un solucionador de necesidades, en un sentido informal, para tener una cantidad infinita de información almacenada en su interior. Las entradas, al ser números naturales, de manera informal llevar sólo una cantidad finita de información de cada uno. Podría cambiar el sistema para permitir que un número infinito de pasos. Entonces usted podría resolver la suspensión problema, pero no natural-número de entradas no ser relevante.

La segunda pregunta es ¿por qué utilizamos máquinas de Turing para definir la computabilidad en lugar de definir de manera más amplia. Por un lado, sólo utilizamos máquinas de Turing para definir lo que yo llamaría clásica de la computabilidad: la computabilidad en $\mathbb{N}$. El hecho de que el uso de máquinas de Turing para definir clásica de la computabilidad es sólo tautologous. Es como preguntar por qué usamos la palabra "alemán" para referirse a la lengua en Alemania.

Pero hay muchas razones para el estudio de la computabilidad en $\mathbb{N}$, al igual que hay muchas razones para el estudio de otras propiedades de los números naturales, incluso aunque a mayor número de sistemas de existir. La razón principal es que los clásicos de la computabilidad coincide exactamente lo que una persona podría hacer, en principio, dado el tiempo ilimitado, bolígrafos y papel.

Answer 2

En realidad todo tipo de personas han intentado desarrollar modelos de cálculo que puede hacer más que una Máquina de Turing puede. Sólo un pequeño problema: no se puede construir.

Si usted averiguar cómo construir uno, y eres realmente buena con los litigios sobre patentes, acuerdos de confidencialidad y la creación de empresas en general, vas a ser un hombre rico. Si usted averiguar cómo construir uno, y no eres muy bueno con esas cosas, alguien más va a ser un hombre rico.

Pero de cualquier manera, el truco no está en el hecho de imaginar parte. El truco está en hacer parte.

No hay ninguna "prueba" de que no hay un más potente modelo computacional, pero, de acuerdo con lo anterior, la Tesis de Church-Turing, que las reclamaciones no la hay. La Tesis de Church-Turing se llama una "tesis" porque no es algo que pueda ser probada. Pero la gente ha estado tratando de encontrar una excepción por un largo tiempo, y no ha podido. Todas las propuestas incluyen cosas como 'infinitamente rápido cálculo', y 'la computación sobre los reales', 'oráculos -- que acaba de pasar a conocer las respuestas a algunas de las principales incomputable resultados", etc. Todos los cuales implican fenómenos no-físicos, también conocido como magic (de ahí, por cierto, el término de oracle).

Es modestamente sorprendente que la de Turing modelo de cálculo es tan poderosa, y hay una tendencia natural a que 'se quiere hacer mejor". Si ya eres rico, tener en ella. Si usted tiene que trabajar para vivir... probablemente la mejor manera de encontrar un problema más fácil.