Estaba tratando de explicarle a alguien que C es Turing completo, y me di cuenta de que en realidad no sé si es, de hecho, técnicamente Turing completo. (C como en la semántica abstracta, no como en una implementación real).
La respuesta "obvia" (más o menos: puede abordar una cantidad arbitraria de memoria, por lo que puede emular una máquina RAM, por lo que es Turing completo) no es realmente correcta, por lo que puedo decir, como si el estándar C permitiera para que size_t sea arbitrariamente grande, debe fijarse a cierta longitud, y no importa en qué longitud se fije, todavía es finito. (En otras palabras, aunque podría, dada una máquina de Turing de detención arbitraria, elegir una longitud de tamaño_t de modo que se ejecute "correctamente", no hay forma de elegir una longitud de tamaño_t de modo que todas las máquinas de Turing de detención funcionen correctamente)
Entonces: ¿está C99 Turing completo?
Respuestas:
No estoy seguro, pero creo que la respuesta es no, por razones bastante sutiles. Me pregunté en la informática teórica hace unos años y no conseguir una respuesta que va más allá de lo que voy a presentar aquí.
En la mayoría de los lenguajes de programación, puede simular una máquina de Turing de la siguiente manera:
Una implementación concreta que se ejecuta en una computadora se quedaría sin memoria si la cinta se alarga demasiado, pero una implementación ideal podría ejecutar el programa de la máquina Turing fielmente. Esto se puede hacer con lápiz y papel, o comprando una computadora con más memoria, y un compilador dirigido a una arquitectura con más bits por palabra y así sucesivamente si el programa alguna vez se queda sin memoria.
Esto no funciona en C porque es imposible tener una lista vinculada que pueda crecer para siempre: siempre hay un límite en la cantidad de nodos.
Para explicar por qué, primero necesito explicar qué es una implementación de C. C es en realidad una familia de lenguajes de programación. El estándar ISO C (más precisamente, una versión específica de este estándar) define (con el nivel de formalidad que permite el inglés) la sintaxis y la semántica de una familia de lenguajes de programación. C tiene muchos comportamientos indefinidos y comportamientos definidos por la implementación. Una "implementación" de C codifica todo el comportamiento definido por la implementación (la lista de cosas para codificar se encuentra en el apéndice J para C99). Cada implementación de C es un lenguaje de programación separado. Tenga en cuenta que el significado de la palabra "implementación" es un poco peculiar: lo que realmente significa es una variante de lenguaje, puede haber múltiples programas compiladores diferentes que implementan la misma variante de lenguaje.
En una implementación dada de C, un byte tiene valores posibles de CHAR_BIT . Todos los datos pueden representarse como una matriz de bytes: un tipo tiene como máximo 2 CHAR_BIT × sizeof (t) valores posibles. Este número varía en diferentes implementaciones de C, pero para una implementación dada de C, es una constante.2CHAR_BIT 2CHAR_BIT×sizeof(t)
t
En particular, los punteros solo pueden tomar como máximo . Esto significa que hay un número máximo finito de objetos direccionables.2CHAR_BIT×sizeof(void*)
Los valores de
CHAR_BIT
ysizeof(void*)
son observables, por lo que si se queda sin memoria, no puede simplemente continuar ejecutando su programa con valores más grandes para esos parámetros. Estaría ejecutando el programa bajo un lenguaje de programación diferente, una implementación de C diferente.Si los programas en un lenguaje solo pueden tener un número limitado de estados, entonces el lenguaje de programación no es más expresivo que los autómatas finitos. El fragmento de C que está restringido al almacenamiento direccionable solo permite como máximo estados del programa donde n es el tamaño del árbol de sintaxis abstracta del programa (que representa el estado del flujo de control), por lo tanto esto El programa puede ser simulado por un autómata finito con tantos estados. Si C es más expresivo, tiene que ser a través del uso de otras características.n×2CHAR_BIT×sizeof(void*) n
C no impone directamente una profundidad máxima de recursión. Se permite que una implementación tenga un máximo, pero también se permite que no tenga uno. Pero, ¿cómo nos comunicamos entre una llamada de función y su padre? Los argumentos no son buenos si son direccionables, porque eso limitaría indirectamente la profundidad de la recursividad: si tiene una función
int f(int x) { … f(…) …}
, todas las apariciones dex
los marcos activosf
tienen su propia dirección, por lo que el número de llamadas anidadas está limitado por el número de posibles direcciones parax
.El programa de CA puede usar almacenamiento no direccionable en forma de
register
variables. Las implementaciones "normales" solo pueden tener un número pequeño y finito de variables que no tienen una dirección, pero en teoría una implementación podría permitir una cantidad ilimitada deregister
almacenamiento. En dicha implementación, puede realizar una cantidad ilimitada de llamadas recursivas a una función, siempre que su argumento searegister
. Pero dado que los argumentos sonregister
, no puede hacer un puntero a ellos, por lo que debe copiar sus datos explícitamente: solo puede pasar una cantidad finita de datos, no una estructura de datos de tamaño arbitrario que esté hecha de punteros.Con una profundidad de recursión ilimitada y la restricción de que una función solo puede obtener datos de su llamador directo (
register
argumentos) y devolver datos a su llamador directo (el valor de retorno de la función), obtiene el poder de los autómatas deterministas .No puedo encontrar una manera de ir más allá.
(Por supuesto, puede hacer que el programa almacene el contenido de la cinta externamente, a través de las funciones de entrada / salida de archivos. Pero no se preguntará si C es Turing completo, sino si C más un sistema de almacenamiento infinito es Turing completo, para cuya respuesta es un aburrido "sí". También podría definir el almacenamiento como un oráculo de Turing: llamada
fopen("oracle", "r+")
,fwrite
el contenido inicial de la cinta yfread
el contenido final de la cinta).fuente
La adición de C99
va_copy
al argumento variable API puede darnos una puerta trasera a la integridad de Turing. Dado que es posible iterar a través de una lista de argumentos variables más de una vez en una función distinta de la que recibió originalmente los argumentos,va_args
se puede usar para implementar un puntero sin puntero.Por supuesto, una implementación real del argumento variable API probablemente tendrá un puntero en alguna parte, pero en nuestra máquina abstracta puede implementarse usando magia en su lugar.
Aquí hay una demostración que implementa un autómata pushdown de 2 pilas con reglas de transición arbitrarias:
Nota: Si
va_list
es un tipo de matriz, en realidad hay parámetros de puntero ocultos para las funciones. Por lo tanto, probablemente sería mejor cambiar los tipos de todos losva_list
argumentos awrapped_stack
.fuente
va_list
variables automáticasstack
. Estas variables deben tener una dirección&stack
, y solo podemos tener un número limitado de ellas. Este requisito podría eludirse declarando cada variable localregister
, ¿tal vez?register
.int
ser necesario que no tenga un límite a menos que alguien use el límite osizeof(int)
?int
tiene un valor entre algunos límites finitosINT_MIN
yINT_MAX
. Y si el valor de unint
desborda esos límites, se produce un comportamiento indefinido. Por otro lado, el estándar intencionalmente no requiere que todos los objetos estén físicamente presentes en la memoria en una dirección particular, ya que esto permite optimizaciones tales como almacenar el objeto en un registro, almacenar solo una parte del objeto y representarlo de manera diferente al estándar diseño u omitirlo por completo si no es necesario.Aritmética no estándar, tal vez?
Entonces, parece que el problema es el tamaño finito de
sizeof(t)
. Sin embargo, creo que sé una solución.Hasta donde yo sé, C no requiere una implementación para usar los enteros estándar para su tipo de entero. Por lo tanto, podríamos usar un modelo no estándar de aritmética . Luego, estableceríamos
sizeof(t)
un número no estándar, y ahora nunca lo alcanzaremos en un número finito de pasos. Por lo tanto, la longitud de la cinta de las máquinas de Turing siempre será menor que el "máximo", ya que el máximo es literalmente imposible de alcanzar.sizeof(t)
simplemente no es un número en el sentido regular de la palabra.Este es un tecnicismo, por supuesto: el teorema de Tennenbaum . Establece que el único modelo de aritmética de Peano es el estándar, que obviamente no funcionaría. Sin embargo, hasta donde yo sé, C no requiere implementaciones para usar tipos de datos que satisfagan los axiomas de Peano, ni requiere que la implementación sea computable, por lo que esto no debería ser un problema.
¿Qué debería suceder si intenta generar un entero no estándar? Bueno, puede representar cualquier número entero no estándar utilizando una cadena no estándar, por lo que solo debe transmitir los dígitos desde el frente de esa cadena.
fuente
sizeof(t)
es en sí mismo un valor de tiposize_t
, por lo que es un entero natural entre 0 ySIZE_MAX
.En mi opinión, una fuerte limitación es que el espacio direccionable (a través del tamaño del puntero) es finito, y esto es irrecuperable.
Se podría recomendar que la memoria se pueda "cambiar al disco", pero en algún momento la información de la dirección excederá el tamaño direccionable.
fuente
En la práctica, estas restricciones son irrelevantes para la integridad de Turing. El requisito real es permitir que la cinta sea arbitrariamente larga, no infinita. Eso crearía un problema de detención de otro tipo (¿cómo "calcula" el universo la cinta?)
Es tan falso como decir "Python no está completo porque no se puede hacer una lista infinitamente grande".
[Editar: gracias al Sr. Whitledge por aclarar cómo editar.]
fuente
size_t
es finito. El problema es que no puede establecer un límitesize_t
que sea válido durante todo el cálculo: para cualquier límite, un programa puede desbordarlo. Pero el lenguaje C indica que existe un límite parasize_t
: en una implementación dada, solo puede crecer hastasizeof(size_t)
bytes. Además, sé amable . Decir que las personas que te critican "no pueden pensar por sí mismas" es grosero.Los medios extraíbles nos permiten evitar el problema de memoria ilimitada. Quizás la gente piense que esto es un abuso, pero creo que está bien y, de todos modos, es inevitable.
Arregle cualquier implementación de una máquina universal de Turing. Para la cinta, utilizamos medios extraíbles. Cuando el cabezal se ejecuta al final o al principio del disco actual, la máquina solicita al usuario que inserte el siguiente o el anterior. Podemos usar un marcador especial para denotar el extremo izquierdo de la cinta simulada, o tener una cinta sin límites en ambas direcciones.
El punto clave aquí es que todo lo que el programa C debe hacer es finito. La computadora solo necesita suficiente memoria para simular el autómata, y
size_t
solo debe ser lo suficientemente grande como para permitir el direccionamiento de esa cantidad (en realidad bastante pequeña) de memoria y en los discos, que puede ser de cualquier tamaño finito fijo. Dado que solo se le solicita al usuario que inserte el disco siguiente o anterior, no necesitamos enteros ilimitadamente grandes para decir "Inserte el número de disco 123456 ..."Supongo que es probable que la principal objeción sea la participación del usuario, pero eso parece inevitable en cualquier implementación, porque parece que no hay otra forma de implementar memoria ilimitada.
fuente
Elige
size_t
ser infinitamente grandePodrías elegir
size_t
ser infinitamente grande. Naturalmente, es imposible realizar tal implementación. Pero eso no es sorprendente, dada la naturaleza finita del mundo en que vivimos.Implicaciones prácticas
Pero incluso si fuera posible realizar tal implementación, habría problemas prácticos. Considere la siguiente declaración C:
SIZE_MAX
SIZE_MAX
size_t
SIZE_MAX
printf
Afortunadamente, para nuestros propósitos teóricos, no pude encontrar ningún requisito en la especificación que garantice que las garantías
printf
terminen para todas las entradas. Entonces, hasta donde yo sé, no violamos la especificación C aquí.Sobre integridad computacional
Todavía queda por demostrar que nuestra implementación teórica es Turing Complete . Podemos mostrar esto implementando "cualquier máquina de Turing de una sola cinta".
La mayoría de nosotros probablemente hemos implementado una máquina de Turing como un proyecto escolar. No daré los detalles de una implementación específica, pero aquí hay una estrategia de uso común:
Ahora veamos qué se requiere para realizar tal implementación:
MAX_INT
ser infinitos. (Alternativamente, podríamos usar otros objetos para representar estados y símbolos).malloc
, pero hay un poco más que debemos considerar:malloc
fallar si, por ejemplo, la memoria disponible se ha agotado. Por lo tanto, nuestra implementación solo es verdaderamente universal simalloc
nunca falla.malloc
fallar. Sin violar el estándar C, nuestra implementación garantizará quemalloc
nunca falle.Entonces, la lista anterior es lo que es necesario para implementar una máquina de Turing en nuestra implementación hipotética de C. Estas características deben terminar. Sin embargo, se puede permitir que cualquier otra cosa no finalice (a menos que lo exija la norma). Esto incluye aritmética, IO, etc.
fuente
printf("%zu\n",SIZE_MAX);
imprimiría en tal implementación?sizeof(size_t)
(oCHAR_BITS
). No se puede reanudar desde el nuevo estado, hay que empezar de nuevo, pero la ejecución del programa puede ser diferente ahora que esas constantes son diferentesEl argumento principal aquí fue que el tamaño de size_t es finito, aunque puede ser infinitamente grande.
Hay una solución alternativa para ello, aunque no estoy seguro de si esto coincide con ISO C.
Suponga que tiene una máquina con memoria infinita. Por lo tanto, no está limitado por el tamaño del puntero. Aún tienes tu tipo size_t. Si me preguntas qué es sizeof (size_t), la respuesta será simplemente sizeof (size_t). Si pregunta si es mayor que 100, por ejemplo, la respuesta es sí. Si pregunta qué es sizeof (size_t) / 2, como podría adivinar, la respuesta sigue siendo sizeof (size_t). Si desea imprimirlo, podemos acordar algunos resultados. La diferencia de estos dos puede ser NaN y así sucesivamente.
El resumen es que relajar la condición para que size_t tenga un tamaño finito no interrumpirá ningún programa ya existente.
PS La asignación de memoria sizeof (size_t) todavía es posible, solo necesita un tamaño contable, así que supongamos que toma todos los pares (o un truco similar).
fuente
sizeof
tiene que devolver asize_t
. Entonces tienes que elegir algún valor particular.Sí lo es.
1. Respuesta citada
Como reacción a la gran cantidad de votos negativos en mis (y otras) respuestas correctas, en comparación con la alarmantemente alta aprobación de respuestas falsas, busqué una explicación alternativa menos teóricamente profunda. Encontré este . Espero que cubra algunas de las falacias comunes aquí, para que se muestre un poco más de información. Parte esencial del argumento:
En resumen, debido a que para cada función computable hay una solución en el lenguaje C (debido a los límites superiores ilimitados), cada problema computable tiene un programa C, por lo que C es Turing completo.
2. Mi respuesta original
Existen confusiones generalizadas entre los conceptos matemáticos en la informática teórica (como la integridad de Turing) y su aplicación en el mundo real, es decir, las técnicas en informática práctica. La integridad de Turing no es una propiedad de máquinas físicamente existentes ni de ningún modelo limitado en el espacio-tiempo. Es solo un objeto abstracto que describe las propiedades de las teorías matemáticas.
C99 es Turing completo independientemente de las restricciones basadas en la implementación, al igual que prácticamente cualquier otro lenguaje de programación común, ya que es capaz de expresar un conjunto funcionalmente completo de conectivos lógicos y, en principio, tiene acceso a una cantidad ilimitada de memoria. Las personas han señalado que C restringe explícitamente el acceso a la memoria aleatoria para que sea limitado, pero esto no es algo que uno no pueda eludir, ya que estas son restricciones adicionales establecidas en el estándar C, mientras que la integridad de Turing ya está implicada sin ellas :
Aquí hay una cosa muy básica sobre los sistemas lógicos que debería ser suficiente para una prueba no constructiva . Considere un cálculo con algunos esquemas y reglas de axioma, de modo que el conjunto de consecuencias lógicas sea X. Ahora, si agrega algunas reglas o axiomas, el conjunto de consecuencias lógicas aumenta, es decir, debe ser un superconjunto de X. Por eso, por ejemplo , la lógica modal S4 está contenida adecuadamente en S5. Del mismo modo, cuando tiene una subespecificación que es completa de Turing, pero agrega algunas restricciones en la parte superior, estas no evitan ninguna de las consecuencias en X, es decir, debe haber una forma de eludir todas las restricciones. Si desea un lenguaje que no sea completo de Turing, el cálculo debe reducirse, no ampliarse. Las extensiones que afirman que algo no sería posible, pero en realidad lo es, solo agregan inconsistencias. Sin embargo, estas inconsistencias en el estándar C pueden no tener consecuencias prácticas, al igual que la integridad de Turing no está relacionada con la aplicación práctica.
Simulando números arbitrarios basados en la profundidad de recursión (es decir, esto ; con la posibilidad de admitir múltiples números a través de la programación / pseudohilos; no hay límite teórico para la profundidad de recursión en C ), o el uso de almacenamiento de archivos para simular memoria de programa ilimitada ( idea ) probablemente solo dos de las infinitas posibilidades para demostrar constructivamente la integridad de Turing de C99. Uno debe recordar que para la computabilidad, la complejidad del tiempo y el espacio son irrelevantes. En particular, asumir un entorno limitado para falsificar la integridad de Turing es simplemente un razonamiento circular, ya que esa limitación excluye todos los problemas que exceden el límite de complejidad presupuestado.
( NOTA : solo escribí esta respuesta para evitar que las personas sean detenidas para ganar intuición matemática debido a algún tipo de pensamiento limitado orientado a la aplicación. Es una lástima que la mayoría de los estudiantes leerán la respuesta falsamente aceptada debido a que se votó en base a defectos fundamentales de razonamiento, para que más personas difundan esas falsas creencias. Si rechaza esta respuesta, usted es solo parte del problema).
fuente
CHAR_BITS
.