Se seguirmos o livro (ou qualquer outra versão da especificação da linguagem, se você preferir), quanta energia computacional pode uma implementação C?
Observe que “implementação C” tem um significado técnico: é uma instanciação específica da especificação da linguagem de programação C em que o comportamento definido pela implementação é documentado. A implementação de CA não precisa ser executada em um computador real. Ele precisa implementar o idioma inteiro, incluindo todos os objetos com uma representação de cadeia de bits e tipos com um tamanho definido pela implementação.
Para os fins desta pergunta, não há armazenamento externo. A única entrada / saída que você pode executar é getchar
(ler a entrada do programa) e putchar
(gravar a saída do programa). Além disso, qualquer programa que invoque um comportamento indefinido é inválido: um programa válido deve ter seu comportamento definido pela especificação C mais a descrição da implementação dos comportamentos definidos pela implementação listados no apêndice J (para C99). Observe que chamar funções de biblioteca que não são mencionadas no padrão é um comportamento indefinido.
Minha reação inicial foi que uma implementação C não passa de um autômato finito, porque tem um limite na quantidade de memória endereçável (você não pode endereçar mais que sizeof(char*) * CHAR_BIT
bits de armazenamento, pois endereços de memória distintos devem ter padrões de bits distintos quando armazenados em um ponteiro de bytes).
No entanto, acho que uma implementação pode fazer mais do que isso. Tanto quanto posso dizer, o padrão não impõe limite à profundidade da recursão. Assim, você pode fazer quantas chamadas de função recursivas quiser, apenas todas, exceto um número finito de chamadas, devem usar register
argumentos não endereçáveis ( ). Assim, uma implementação C que permite recursão arbitrária e não tem limite no número de register
objetos pode codificar autômatos de empilhamento determinístico.
Isso está correto? Você consegue encontrar uma implementação C mais poderosa? Existe uma implementação C completa de Turing?
fonte
Respostas:
Conforme observado na pergunta, o padrão C requer que exista um valor UCHAR_MAX, de modo que cada variável do tipovocêCHA R _ MA Xs i ze o f( U n s i gn e d c h a r ∗ ) 101010
unsigned char
mantenha sempre um valor entre 0 e UCHAR_MAX, inclusive. Além disso, exige que todo objeto alocado dinamicamente seja representado por uma sequência de bytes que seja identificável via ponteiro do tipounsigned char*
, e que haja uma constantesizeof(unsigned char*)
tal que cada ponteiro desse tipo seja identificável por uma sequência desizeof(unsigned char *)
valores do tipounsigned char
. O número de objetos que podem ser alocados dinamicamente simultaneamente é, portanto, rigidamente limitado a . Nada impediria um compilador teórico de atribuir os valores dessas constantes para suportar mais de 10 10 10 objetos, mas, de uma perspectiva teórica, a existência de qualquer limite, por maior que seja, significa que algo não é infinito.Um programa pode armazenar uma quantidade ilimitada de informações na pilha se nada do que estiver alocado na pilha tiver seu endereço ; assim, poderia-se ter um programa em C capaz de fazer algumas coisas que não poderiam ser feitas por nenhum autômato finito de qualquer tamanho. Assim, mesmo que (ou talvez porque) o acesso a variáveis de pilha seja muito mais limitado do que o acesso a variáveis alocadas dinamicamente, ele faz com que C seja um autômato finito em um autômato push-down.
Há, no entanto, outro problema: é necessário que, se um programa examinar as seqüências de tamanho fixo subjacentes dos valores de caracteres associados a dois ponteiros para objetos diferentes, essas sequências sejam únicas. Uma vez que existem apenasvocêCHA R _ MA Xs i ze o f( U n s i gn e d c h a r ∗ ) Seqüências possíveis de valores de caracteres, qualquer programa que criou um número de ponteiros para objetos distintos além do que não poderia estar em conformidade com o padrão C se o código examinasse a sequência de caracteres associados a esses ponteiros . Em alguns casos, seria possível para um compilador determinar que nenhum código jamais examinaria a sequência de caracteres associados a um ponteiro. Se cada "caractere" fosse realmente capaz de conter qualquer número inteiro finito, e a memória da máquina fosse uma sequência contável e infinita de números inteiros [dada uma máquina de Turing com fita ilimitada, seria possível imitar essa máquina, embora fosse muito lenta], então seria realmente possível tornar C uma linguagem completa de Turing.
fonte
Com a biblioteca de encadeamento do C11 (opcional), é possível fazer uma implementação completa do Turing, com profundidade de recursão ilimitada.
Criar um novo encadeamento gera uma segunda pilha; duas pilhas são suficientes para a integridade de Turing. Uma pilha representa o que está à esquerda da cabeça, a outra pilha, o que está à direita.
fonte
Eu acho que é Turing completo : podemos escrever um programa que simula um UTM usando esse truque (eu rapidamente escrevi o código manualmente, então provavelmente existem alguns erros de sintaxe ... mas espero que não haja erros (principais) na lógica :-)
O
head
será um ponteiro para umacell_t
estruturastacker
função quando lê o último símbolo da fita de entrada (usando readchar)EDIT: depois de pensar um pouco sobre isso, há um problema com os ponteiros ...
se toda chamada da função recursiva
stacker
puder manter um ponteiro válido para uma variável definida localmente no chamador, tudo estará bem ; caso contrário, meu algoritmo não pode manter uma lista válida de vínculo duplo na recursão ilimitada (e, neste caso, não vemos uma maneira de usar a recursão para simular um armazenamento ilimitado de acesso aleatório).fonte
stacker
newcell
stacker
sizeof(cell_t)
Desde que você tenha um tamanho ilimitado de pilha de chamadas, você pode codificar sua fita na pilha de chamadas e acessá-la aleatoriamente rebobinando o ponteiro da pilha sem retornar das chamadas de função.Edição : Se você só pode usar o carneiro, que é finito, essa construção não funciona mais, então veja abaixo.
No entanto, é altamente questionável por que sua pilha pode ser infinita, mas a ram intrínseca não é.
Então, na verdade, eu diria que você nem consegue reconhecer todas as linguagens regulares, pois o número de estados é limitado (se você não contar o truque de rebobinar a pilha para explorar a pilha infinita).Eu até especularia que o número de idiomas que você pode reconhecer é finito (mesmo que os próprios idiomas possam ser infinitos, por exemploa*
, tudo bem, masb^k
só funciona para um número finito dek
s).EDIT : Isso não é verdade, pois você pode codificar o estado atual em funções extras, para que você possa realmente reconhecer TODOS os idiomas regulares.
Provavelmente, você pode obter todos os idiomas do Tipo 2 pelo mesmo motivo, mas não tenho certeza se você consegue colocar ambos, o estado e a constante da pilha na pilha de chamadas. Mas, de maneira geral, você pode efetivamente esquecer o carneiro, pois sempre pode dimensionar o tamanho do autômato para que seu alfabeto exceda a capacidade do carneiro. Então, se você pudesse simular uma TM com apenas uma pilha, o Tipo 2 seria igual ao Tipo 0, não seria?
fonte
Pensei nisso uma vez e decidi tentar implementar uma linguagem sem contexto, usando a semântica esperada; a parte principal da implementação é a seguinte função:
Pelo menos, acho que isso funciona. Pode ser que eu esteja cometendo algum erro fundamental, no entanto.
Uma versão fixa:
fonte
it = *it
deve ser substituído porit = * (void **) it
, caso contrário,*it
é do tipovoid
.Na linha da resposta do @ supercat:
As alegações de incompletude de C parecem estar centradas em torno de que objetos distintos devem ter endereços distintos, e o conjunto de endereços é considerado finito. Como @supercat escreve
unsigned char*
sizeof(unsigned char*)
sizeof(unsigned char*)
Nesse ponto, deve-se verificar se o padrão C realmente permitiria isso.
sizeof
fonte
uintptr_t p = (uintptr_t)sizeof(void*)
(colocar \ omega em algo que contém números inteiros não assinados). Eu não sei. Podemos definir o resultado como 0 (ou qualquer outro número).uintptr_t
teria que ser infinito também. Lembre-se, esse tipo é opcional - mas se você tiver um número infinito de valores de ponteiro distintos,sizeof(void*)
também deverá ser infinito, tambémsize_t
deve ser infinito. No entanto, minha objeção sobre o módulo de redução não é tão óbvia - ela só entra em jogo se houver um estouro, mas se você permitir tipos infinitos, eles nunca poderão estourar. Mas por outro lado, cada tipo tem valores mínimos e máximos, o que, pelo que sei, implica queUINT_MAX+1
deve transbordar.size_t
tipos de ponteiro e de to ∪ {ω}. Isso elimina o problema mínimo / máximo. O problema com a semântica de estouro ainda permanece. O que deveria ser a semântica deuint x = (uint)ω
não está claro para mim. Mais uma vez, podemos pegar 0 ao acaso, mas parece um pouco feio.