Si seguimos el libro (o cualquier otra versión de la especificación del lenguaje si lo prefiere), ¿cuánta potencia computacional puede tener una implementación de C?
Tenga en cuenta que "implementación C" tiene un significado técnico: es una instanciación particular de la especificación del lenguaje de programación C donde se documenta el comportamiento definido por la implementación. La implementación de CA no tiene que poder ejecutarse en una computadora real. Tiene que implementar todo el lenguaje, incluidos todos los objetos que tienen una representación de cadena de bits y los tipos que tienen un tamaño definido por la implementación.
A los efectos de esta pregunta, no hay almacenamiento externo. La única entrada / salida que puede realizar es getchar
(para leer la entrada del programa) y putchar
(para escribir la salida del programa). Además, cualquier programa que invoque un comportamiento indefinido no es válido: un programa válido debe tener su comportamiento definido por la especificación C más la descripción de la implementación de los comportamientos definidos por la implementación enumerados en el apéndice J (para C99). Tenga en cuenta que llamar a funciones de biblioteca que no se mencionan en el estándar es un comportamiento indefinido.
Mi reacción inicial fue que una implementación en C no es más que un autómata finito, ya que tiene un límite en la cantidad de memoria direccionable (no se puede direccionar más que sizeof(char*) * CHAR_BIT
bits de almacenamiento, ya que distintas direcciones de memoria deben tener patrones de bits distintos cuando se almacenan en un puntero de byte).
Sin embargo, creo que una implementación puede hacer más que esto. Por lo que puedo decir, el estándar no impone ningún límite en la profundidad de la recursión. Por lo tanto, puede realizar tantas llamadas a funciones recursivas como desee, solo todas menos un número finito de llamadas deben usar register
argumentos no direccionables ( ). Por lo tanto, una implementación en C que permite la recursión arbitraria y no tiene límite en el número de register
objetos puede codificar autómatas de pushdown determinista.
¿Es esto correcto? ¿Puedes encontrar una implementación de C más potente? ¿Existe una implementación de Turing-complete C?
fuente
Respuestas:
Como se señaló en la pregunta, el estándar C requiere que exista un valor UCHAR_MAX de modo que cada variable de tipoUdoHA R _ MA Xs i ze o f( u n s i gn e d c h a r ∗ ) 101010
unsigned char
siempre tenga un valor entre 0 y UCHAR_MAX, inclusive. Además, requiere que cada objeto asignado dinámicamente esté representado por una secuencia de bytes que sea identificable mediante un puntero de tipounsigned char*
, y que exista una constantesizeof(unsigned char*)
tal que cada puntero de ese tipo sea identificable por una secuencia desizeof(unsigned char *)
valores de tipounsigned char
. El número de objetos que pueden asignarse dinámicamente simultáneamente está, por lo tanto, rígidamente limitado a . Nada impediría que un compilador teórico asigne los valores de esas constantes para soportar más de 10 10 10 objetos, pero desde una perspectiva teórica la existencia de cualquier límite, no importa cuán grande sea, significa que algo no es infinito.Un programa podría almacenar una cantidad ilimitada de información en la pila si nada de lo que se asigna en la pila tiene su dirección tomada ; por lo tanto, se podría tener un programa en C que fuera capaz de hacer algunas cosas que ningún autómata finito de ningún tamaño podría hacer. Por lo tanto, aunque (o tal vez porque) el acceso a las variables de la pila es mucho más limitado que el acceso a las variables asignadas dinámicamente, convierte a C de ser un autómata finito en un autómata pushdown.
Sin embargo, existe otra posible arruga: se requiere que si un programa examina las secuencias subyacentes de longitud fija de valores de caracteres asociados con dos punteros a diferentes objetos, esas secuencias deben ser únicas. Porque solo hayUdoHA R _ MA Xs i ze o f( u n s i gn e d c h a r ∗ ) posibles secuencias de valores de caracteres, cualquier programa que creara una cantidad de punteros a objetos distintos que no pudieran cumplir con el estándar C si el código alguna vez examinara la secuencia de caracteres asociados con esos punteros . Sin embargo, en algunos casos sería posible que un compilador determinara que ningún código examinaría la secuencia de caracteres asociada a un puntero. Si cada "char" era realmente capaz de contener cualquier número entero finito, y la memoria de la máquina era una secuencia infinita de números enteros [dada una máquina Turing de cinta ilimitada, uno podría emular una máquina de este tipo aunque sería realmente lenta], entonces de hecho, sería posible hacer de C un lenguaje completo de Turing.
fuente
Con la biblioteca de subprocesos de C11 (opcional), es posible realizar una implementación completa de Turing con una profundidad de recursión ilimitada.
Crear un nuevo hilo produce una segunda pila; dos pilas son suficientes para completar Turing. Una pila representa lo que está a la izquierda de la cabeza, la otra pila lo que está a la derecha.
fuente
Creo que está completando Turing : podemos escribir un programa que simule un UTM usando este truco (escribí rápidamente el código a mano, por lo que probablemente haya algunos errores de sintaxis ... pero espero que no haya errores (mayores) en la lógica :-)
El
head
será un puntero a unacell_t
estructurastacker
función cuando lee el último símbolo de la cinta de entrada (usando readchar)EDITAR: después de pensar un poco al respecto, hay un problema con los punteros ...
si cada llamada de la función recursiva
stacker
puede mantener un puntero válido a una variable definida localmente en la persona que llama, entonces todo está bien ; de lo contrario, mi algoritmo no puede mantener una lista válida de doble enlace en la recursión ilimitada (y en este caso no veo una manera de usar la recursión para simular un almacenamiento ilimitado de acceso aleatorio).fuente
stacker
newcell
stacker
sizeof(cell_t)
Siempre que tenga un tamaño ilimitado de la pila de llamadas, puede codificar su cinta en la pila de llamadas y acceder aleatoriamente rebobinando el puntero de la pila sin regresar de las llamadas a funciones.Edición : si solo puede usar el carnero, que es finito, esta construcción ya no funciona, así que vea a continuación.
Sin embargo, es muy cuestionable por qué su pila puede ser infinita pero el ariete intrínseco no.
Entonces, en realidad, diría que ni siquiera puede reconocer todos los idiomas regulares, ya que el número de estados está limitado (si no cuenta el truco de pila-rebobinado para explotar la pila infinita).Incluso podría especular que el número de idiomas que puede reconocer es finito (incluso si los idiomas mismos pueden ser infinitos, por ejemplo,a*
está bien, perob^k
solo funciona para un número finito dek
s).EDITAR : Esto no es cierto, ya que puede codificar el estado actual en funciones adicionales, por lo que realmente puede reconocer TODOS los idiomas regulares.
Lo más probable es que pueda obtener todos los idiomas de Tipo 2 por la misma razón, pero no estoy seguro de si puede colocar ambos, el estado y el contenido de la pila en la pila de llamadas. Pero en términos generales, puede olvidarse efectivamente del carnero, ya que siempre puede escalar el tamaño del autómata para que su alfabeto exceda la capacidad del carnero. Entonces, si pudieras simular una TM con solo una pila, Tipo-2 sería igual a Tipo-0, ¿no?
fuente
Pensé en esto una vez y decidí intentar implementar un lenguaje sin contexto utilizando la semántica esperada; La parte clave de la implementación es la siguiente función:
Al menos, creo que esto funciona. Sin embargo, puede ser que esté cometiendo un error fundamental.
Una versión fija:
fuente
it = *it
debe ser reemplazado porit = * (void **) it
, ya que de lo contrario*it
es de tipovoid
.En la línea de la respuesta de @ supercat:
Las afirmaciones de incompletitud de C parecen centrarse en que los objetos distintos deben tener direcciones distintas, y se supone que el conjunto de direcciones es finito. Como escribe @supercat
unsigned char*
sizeof(unsigned char*)
sizeof(unsigned char*)
En este punto, uno debería verificar que el estándar C lo permitiría.
sizeof
fuente
uintptr_t p = (uintptr_t)sizeof(void*)
(poner \ omega en algo que contiene enteros sin signo). Yo no sé. Podemos evitar definir el resultado como 0 (o cualquier otro número).uintptr_t
Tendría que ser infinito también. Eso sí, este tipo es opcional, pero si tiene un número infinito de valores de puntero distintos,sizeof(void*)
también debe ser infinito, por lo quesize_t
debe ser infinito. Sin embargo, mi objeción sobre el módulo de reducción no es tan obvia: solo entra en juego si hay un desbordamiento, pero si permite tipos infinitos, es posible que nunca se desborden. Pero, por otro lado, cada tipo tiene valores mínimos y máximos, que por lo que puedo decir implica queUINT_MAX+1
debe desbordarse.size_t
tipos de puntero para que sean ℕ ∪ {ω}. Esto elimina el problema min / max. El problema con la semántica de desbordamiento aún persiste. Lo que debería ser la semánticauint x = (uint)ω
no me resulta claro. De nuevo, podríamos tomar 0 al azar, pero se ve un poco feo.