¿C es realmente Turing completo?

40

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?

TLW
fuente
3
¿Cuáles son las "semánticas abstractas" de C? ¿Están definidos en alguna parte?
Yuval Filmus
44
@YuvalFilmus: consulte, por ejemplo , aquí , es decir, C como se define en el estándar en lugar de, por ejemplo, "así es como lo hace gcc".
TLW
1
existe el "tecnicismo" de que las computadoras modernas no tienen memoria infinita como la TM pero aún se consideran "computadoras universales". y tenga en cuenta que los lenguajes de programación en su "semántica" realmente no asumen una memoria finita, excepto que todas sus implementaciones , por supuesto, están limitadas en la memoria. ver, por ejemplo, ¿ funciona nuestra PC como una máquina de Turing ? de todos modos, esencialmente todos los lenguajes de programación "convencionales" están completos.
vzn
2
C (como máquinas de Turing) no se limita a la utilización de la memoria del ordenador interno para sus cálculos, por lo que esto no es un argumento válido en contra de la Turing completo de C.
reinierpost
@reinierpost: es como decir que un teletipo es inteligente. Eso significa que "C + un equivalente externo de TM" es completo de Turing, no que C es completo de Turing.
TLW

Respuestas:

34

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:

  • simulando el autómata finito con un programa que usa una cantidad finita de memoria;
  • simulando la cinta con un par de listas enlazadas de enteros, que representan el contenido de la cinta antes y después de la posición actual. Mover el puntero significa transferir el encabezado de una de las listas a la otra lista.

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_BITt2CHAR_BIT×sizeof(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_BITy sizeof(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 de xlos marcos activos ftienen su propia dirección, por lo que el número de llamadas anidadas está limitado por el número de posibles direcciones para x.

El programa de CA puede usar almacenamiento no direccionable en forma de registervariables. 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 de registeralmacenamiento. En dicha implementación, puede realizar una cantidad ilimitada de llamadas recursivas a una función, siempre que su argumento sea register. Pero dado que los argumentos son register, 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 ( registerargumentos) 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+"), fwriteel contenido inicial de la cinta y freadel contenido final de la cinta).

Gilles 'SO- deja de ser malvado'
fuente
No está claro de inmediato por qué el conjunto de direcciones debe ser finito. Escribí algunos pensamientos en una respuesta a la pregunta que usted vincula: cstheory.stackexchange.com/a/37036/43393
Alexey B.
44
Lo sentimos, pero por la misma lógica, no hay ningún lenguaje de programación completo de Turing. Cada idioma tiene una limitación explícita o implícita en el espacio de direcciones. Si crea una máquina con memoria infinita, entonces los punteros de acceso aleatorio obviamente también serán de longitud infinita. Por lo tanto, si aparece dicha máquina, tendrá que ofrecer un conjunto de instrucciones para el acceso secuencial a la memoria, junto con una API para lenguajes de alto nivel.
IMil
14
@IMil Esto no es cierto. Algunos lenguajes de programación no tienen limitación en el espacio de direcciones, ni siquiera implícitamente. Para tomar un ejemplo obvio, una máquina universal de Turing donde el estado inicial de la cinta forma el programa es un lenguaje de programación completo de Turing. Muchos lenguajes de programación que realmente se usan en la práctica tienen la misma propiedad, por ejemplo, Lisp y SML. Un lenguaje no tiene que tener un concepto de "puntero de acceso aleatorio". (cont.)
Gilles 'SO- deja de ser malvado'
11
@IMil (cont.) Las implementaciones generalmente funcionan para el rendimiento, pero sabemos que una implementación que se ejecuta en una computadora en particular no es completa en Turing ya que está limitada por el tamaño de la memoria de la computadora. Pero eso significa que la implementación no implementa todo el lenguaje, solo un subconjunto (de programas que se ejecutan en N bytes de memoria). Puede ejecutar el programa en una computadora, y si se queda sin memoria, muévalo a una computadora más grande, y así sucesivamente para siempre o hasta que se detenga. Esa sería una forma válida de implementar todo el lenguaje.
Gilles 'SO- deja de ser malvado'
6

La adición de C99 va_copyal 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_argsse 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:

#include <stdarg.h>
typedef struct { va_list va; } wrapped_stack; // Struct wrapper needed if va_list is an array type.
#define NUM_SYMBOLS /* ... */
#define NUM_STATES /* ... */
typedef enum { NOP, POP1, POP2, PUSH1, PUSH2 } operation_type;
typedef struct { int next_state; operation_type optype; int opsymbol; } transition;
transition transition_table[NUM_STATES][NUM_SYMBOLS][NUM_SYMBOLS] = { /* ... */ };

void step(int state, va_list stack1, va_list stack2);
void push1(va_list stack2, int next_state, ...) {
    va_list stack1;
    va_start(stack1, next_state);
    step(next_state, stack1, stack2);
}
void push2(va_list stack1, int next_state, ...) {
    va_list stack2;
    va_start(stack2, next_state);
    step(next_state, stack1, stack2);
}
void step(int state, va_list stack1, va_list stack2) {
    va_list stack1_copy, stack2_copy;
    va_copy(stack1_copy, stack1); va_copy(stack2_copy, stack2);
    int symbol1 = va_arg(stack1_copy, int), symbol2 = va_arg(stack2_copy, int);
    transition tr = transition_table[state][symbol1][symbol2];
    wrapped_stack ws;
    switch(tr.optype) {
        case NOP: step(tr.next_state, stack1, stack2);
        // Note: attempting to pop the stack's bottom value results in undefined behavior.
        case POP1: ws = va_arg(stack1_copy, wrapped_stack); step(tr.next_state, ws.va, stack2);
        case POP2: ws = va_arg(stack2_copy, wrapped_stack); step(tr.next_state, stack1, ws.va);
        case PUSH1: va_copy(ws.va, stack1); push1(stack2, tr.next_state, tr.opsymbol, ws);
        case PUSH2: va_copy(ws.va, stack2); push2(stack1, tr.next_state, tr.opsymbol, ws);
    }
}
void start_helper1(va_list stack1, int dummy, ...) {
    va_list stack2;
    va_start(stack2, dummy);
    step(0, stack1, stack2);
}
void start_helper0(int dummy, ...) {
    va_list stack1;
    va_start(stack1, dummy);
    start_helper1(stack1, 0, 0);
}
// Begin execution in state 0 with each stack initialized to {0}
void start() {
    start_helper0(0, 0);
}

Nota: Si va_listes 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 los va_listargumentos a wrapped_stack.

Feersum
fuente
Esto podría funcionar. Una posible preocupación es que se basa en la asignación de un número ilimitado de va_listvariables automáticas stack. 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 local register, ¿tal vez?
chi
@chi AIUI no se requiere que una variable tenga una dirección a menos que alguien intente tomar la dirección. Además, es ilegal declarar el argumento inmediatamente anterior a los puntos suspensivos register.
Feersum
Por la misma lógica, ¿no debería intser necesario que no tenga un límite a menos que alguien use el límite o sizeof(int)?
chi
@chi Para nada. El estándar define como parte de la semántica abstracta que inttiene un valor entre algunos límites finitos INT_MINy INT_MAX. Y si el valor de un intdesborda 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.
feersum
4

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.

PyRulez
fuente
¿Cómo sería una implementación?
reinierpost
@reinierpost Supongo que representaría datos usando algún modelo contable no estándar de PA. Calcularía operaciones aritméticas utilizando un grado PA . Creo que cualquier modelo de este tipo debería proporcionar una implementación válida de C.
PyRulez
Lo siento, esto no funciona. sizeof(t)es en sí mismo un valor de tipo size_t, por lo que es un entero natural entre 0 y SIZE_MAX.
Gilles 'SO- deja de ser malvado'
@Gilles SIZE_MAX también sería un natural no estándar.
PyRulez
Este es un enfoque interesante. Tenga en cuenta que también necesitaría, por ejemplo, intptr_t / uintptr_t / ptrdiff_t / intmax_t / uintmax_t para que no sea estándar. En C ++ esto entraría en conflicto con las garantías de avance ... no estoy seguro acerca de C.
TLW
0

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.

Yves Daoust
fuente
¿No es este el punto principal de la respuesta aceptada? No creo que agregue nada nuevo a las respuestas de esta pregunta de 2016.
chi
@chi: no, la respuesta aceptada no menciona el intercambio a memoria externa, lo que podría considerarse una solución alternativa.
Yves Daoust
-1

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.]

theDoctor
fuente
77
No creo que esto responda la pregunta. La pregunta ya anticipaba esta respuesta, y explicaba por qué no es válida: "aunque el estándar C permite que size_t sea arbitrariamente grande, debe fijarse en cierta longitud, y no importa en qué longitud se fije, todavía es finito ". ¿Tienes alguna respuesta a ese argumento? No creo que podamos contar la pregunta como respondida a menos que la respuesta explique por qué ese argumento es incorrecto (o correcto).
DW
55
En cualquier momento, un valor de tipo size_tes finito. El problema es que no puede establecer un límite size_tque 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 para size_t: en una implementación dada, solo puede crecer hasta sizeof(size_t)bytes. Además, sé amable . Decir que las personas que te critican "no pueden pensar por sí mismas" es grosero.
Gilles 'SO- deja de ser malvado'
1
Esta es la respuesta correcta. Una máquina de torneado no requiere una cinta infinita, requiere una cinta "arbitrariamente larga". Es decir, puede suponer que la cinta es tan larga como debe ser para completar el cálculo. También puede suponer que su computadora tiene tanta memoria como necesita. No se requiere absolutamente una cinta infinita, porque cualquier cálculo que se detenga en un tiempo finito no puede utilizar una cantidad infinita de cinta.
Jeffrey L Whitledge
Lo que muestra esta respuesta es que para cada TM puede escribir una implementación en C con una longitud de puntero suficiente para simularla. Sin embargo, no es posible escribir una implementación de C que pueda simular cualquier TM. Por lo tanto, la especificación prohíbe que cualquier implementación particular sea T-complete. Tampoco es T-complete, porque la longitud del puntero es fija.
1
Esta es otra respuesta correcta que apenas es visible debido a la incapacidad de la mayoría de las personas en esta comunidad. Mientras tanto, la respuesta aceptada es falsa y su sección de comentarios está protegida por moderadores que eliminan comentarios críticos. Adiós, cs.stackexchange.
xamid
-1

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_tsolo 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.

David Richerby
fuente
3
Yo diría que, a menos que la definición de C requiera un almacenamiento externo ilimitado, esto no puede aceptarse como prueba de la integridad de Turing. (ISO 9899 no requiere que, por supuesto, esté escrito para la ingeniería del mundo real). Lo que me preocupa es que, si aceptamos esto, por un razonamiento similar podríamos afirmar que los DFA están completos, ya que podrían usarse conducir una cabeza sobre una cinta (el almacenamiento externo).
chi
@chi No veo cómo sigue el argumento de DFA. El objetivo de un DFA es que solo tiene acceso de lectura al almacenamiento. Si le permite "pasar una cabeza por una cinta", ¿no es eso exactamente una máquina de Turing?
David Richerby
2
De hecho, estoy jugando un poco aquí. El punto es: ¿por qué está bien agregar una "cinta" a C, dejar que C simule un DFA y usar este hecho para afirmar que C está Turing completo, cuando no podemos hacer lo mismo con los DFA? Si C no tiene forma de implementar memoria ilimitada por sí solo, entonces no debe considerarse que Turing está completo. (Todavía lo llamaría "moralmente" Turing completo, al menos, ya que los límites son tan grandes que en la práctica no importan en la mayoría de los casos) Creo que para resolver definitivamente el asunto, uno necesitaría una especificación formal rigurosa de C (el estándar ISO no es suficiente)
chi
1
@chi Está bien porque C incluye rutinas de E / S de archivo. Los DFA no lo hacen.
David Richerby
1
C no especifica completamente lo que hacen estas rutinas: la mayor parte de su semántica está definida por la implementación. La implementación de CA no es necesaria para almacenar el contenido del archivo, por ejemplo, creo que puede comportarse como si cada archivo fuera "/ dev / null", por así decirlo. Tampoco es necesario almacenar una cantidad ilimitada de datos. Diría que su argumento es correcto, al considerar lo que hace la gran mayoría de las implementaciones de C y generalizar ese comportamiento a una máquina ideal. Si confiamos estrictamente en la definición de C, solo, olvidando la práctica, no creo que sea válida.
chi
-2

Elige size_tser infinitamente grande

Podrías elegir size_tser 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:

printf("%zu\n",SIZE_MAX);

SIZE_MAXSIZE_MAXO(2size_t)size_tSIZE_MAXprintf

Afortunadamente, para nuestros propósitos teóricos, no pude encontrar ningún requisito en la especificación que garantice que las garantías printfterminen 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:

  • El número de estados, el número de símbolos y la tabla de transición de estado son fijos para cualquier máquina dada. Entonces podemos representar estados y símbolos como números, y la tabla de transición de estado como una matriz bidimensional.
  • La cinta se puede representar como una lista vinculada. Podemos usar una sola lista de doble enlace o dos listas de un solo enlace (una para cada dirección desde la posición actual).

Ahora veamos qué se requiere para realizar tal implementación:

  • La capacidad de representar un conjunto de números fijo, pero arbitrariamente grande. Para representar cualquier número arbitrario, también elegimos MAX_INTser infinitos. (Alternativamente, podríamos usar otros objetos para representar estados y símbolos).
  • La capacidad de construir una lista enlazada arbitrariamente grande para nuestra cinta. Una vez más, no hay límite finito en el tamaño. Esto significa que no podemos construir esta lista por adelantado, ya que gastaríamos una eternidad para construir nuestra cinta. Pero, podemos construir esta lista de forma incremental si utilizamos la asignación dinámica de memoria. Podemos usar malloc, pero hay un poco más que debemos considerar:
    • La especificación C permite mallocfallar si, por ejemplo, la memoria disponible se ha agotado. Por lo tanto, nuestra implementación solo es verdaderamente universal si mallocnunca falla.
    • Sin embargo, si nuestra implementación se ejecuta en una máquina con memoria infinita, entonces no hay necesidad de mallocfallar. Sin violar el estándar C, nuestra implementación garantizará que mallocnunca falle.
  • La capacidad de desreferenciar punteros, buscar elementos de matriz y acceder a los miembros de un nodo de lista vinculada

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.

Nathan Davis
fuente
66
¿Qué se printf("%zu\n",SIZE_MAX);imprimiría en tal implementación?
Ruslan
1
@Ruslan, tal implementación es imposible, al igual que es imposible implementar una máquina Turing. Pero si tal implementación fuera posible, imagino que imprimiría alguna representación decimal de un número infinitamente grande, presumiblemente, una corriente infinita de dígitos decimales.
Nathan Davis el
2
@NathanDavis Es posible implementar una máquina Turing. El truco es que no necesita construir una cinta infinita, solo construye la parte usada de la cinta de forma incremental según sea necesario.
Gilles 'SO- deja de ser malvado'
2
@Gilles: en este universo finito en el que vivimos, es imposible implementar una máquina de Turing.
gnasher729
1
@NathanDavis Pero si haces eso, entonces has cambiado sizeof(size_t)(o CHAR_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 diferentes
Gilles 'SO- estar parada mal'
-2

El 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).

Eugene
fuente
1
"La diferencia de estos dos puede ser NaN". No, no puede ser. No existe un NaN de tipo entero en C.
TLW
Según la norma, sizeoftiene que devolver a size_t. Entonces tienes que elegir algún valor particular.
Draconis
-4

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:

[...] Su argumento es el siguiente: supongamos que uno ha escrito un programa de terminación dado que puede requerir, durante su ejecución, hasta una cantidad arbitraria de almacenamiento. Sin cambiar ese programa, es posible a posteriori implementar una pieza de hardware de computadora y su compilador de C que brinde suficiente almacenamiento para acomodar este cálculo. Esto puede requerir ampliar los anchos de char (a través de CHAR_BITS) y / o punteros (a través de size_t), pero el programa no necesitaría ser modificado. Como esto es posible, C es de hecho Turing-Complete para terminar programas.

La parte difícil de este argumento es que solo funciona cuando se considera terminar programas. Los programas de terminación tienen esta buena propiedad de que tienen un límite superior estático para sus requisitos de almacenamiento, que uno puede determinar experimentalmente ejecutando el programa sobre la entrada deseada con tamaños de almacenamiento crecientes, hasta que "encaje".

La razón por la que me confundí en mi tren de pensamientos es que estaba considerando la clase más amplia de programas "útiles" sin fin [...]

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).

xamid
fuente
44
No sigo tu último párrafo. Afirmas que agregar restricciones aumenta el poder expresivo, pero eso claramente no es cierto. Las restricciones solo pueden disminuir el poder expresivo. Por ejemplo, si toma C y agrega la restricción de que ningún programa puede acceder a más de 640 kb de almacenamiento (de cualquier tipo), entonces lo ha convertido en un elegante autómata finito que claramente no está completo de Turing.
David Richerby
3
Si tiene una cantidad fija de almacenamiento, no puede simular nada que requiera más recursos de los que tiene. Solo hay muchas configuraciones en las que puede estar su memoria, lo que significa que solo hay muchas cosas que puede hacer.
David Richerby
2
No entiendo por qué te refieres a "máquinas físicamente existentes". Tenga en cuenta que la integridad de Turing es una propiedad de un modelo computacional matemático, no de sistemas físicos. Estoy de acuerdo en que ningún sistema físico, al ser un objeto finito, puede acercarse al poder de las máquinas de Turing, pero eso es irrelevante. Todavía podemos tomar cualquier lenguaje de programación, considerar la definición matemática de su semántica y verificar si ese objeto matemático está completo. El juego de la vida de Conway es poderoso, incluso si no hay una implementación física posible.
chi
2
@xamid Si tiene dudas con respecto a las políticas de moderación de este sitio, llévelo a Computer Science Meta . Hasta entonces, por favor se amable . El abuso verbal de otros no será tolerado. (He eliminado todos los comentarios que no pertenecen al tema en cuestión.)
Raphael
2
Usted dice que modificar el ancho de un puntero no cambiaría el programa, pero los programas pueden leer el ancho de un puntero y hacer lo que quieran con ese valor. Lo mismo para CHAR_BITS.
Draconis