Potência computacional máxima de uma implementação C

28

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_BITbits 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 registerargumentos não endereçáveis ​​( ). Assim, uma implementação C que permite recursão arbitrária e não tem limite no número de registerobjetos 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?

Gilles 'SO- parar de ser mau'
fonte
4
@ Dave: Como Gilles explicou, parece que você pode ter memória ilimitada, mas não há como abordá-la diretamente.
Jukka Suomela
2
De sua explicação parece que qualquer implementação C só pode ser programado para aceitar línguas aceites por determinista autômatos pushdown, que são mais fracos do que línguas mesmo livres de contexto. Esta observação, no entanto, é de pouco interesse na minha opinião, pois a pergunta é uma aplicação incorreta de assintóticos.
21910 Warren Schudy
3
Um ponto a ser lembrado é que existem muitas maneiras de acionar o "comportamento definido pela implementação" (ou "comportamento indefinido"). E, em geral, uma implementação pode fornecer, por exemplo, funções de biblioteca que fornecem funcionalidade que não está definida no padrão C. Tudo isso fornece "brechas" através das quais você pode acessar, digamos, uma máquina completa de Turing. Ou até algo muito mais forte, como um oráculo que resolve o problema da parada. Um exemplo estúpido: o comportamento definido pela implementação de estouros de número inteiro assinados ou conversões de ponteiro de número inteiro pode permitir que você acesse esse oráculo.
Jukka Suomela
7
A propósito, pode ser uma boa ideia adicionar a tag "recreacional" (ou o que estiver usando para quebra-cabeças engraçados) para que as pessoas não levem isso muito a sério. Obviamente, é a "pergunta errada" a ser feita, mas mesmo assim achei divertido e intrigante. :)
Jukka Suomela
2
@Jukka: Boa ideia. Por exemplo, estouro de X = escreva X / 3 na fita e mova na direção X% 3, estouro = dispara o sinal correspondente ao símbolo na fita. Parece um abuso, mas definitivamente está no espírito da minha pergunta. Você poderia escrever como resposta? (@others: Não que eu queira desencorajar outras sugestões tão inteligentes!)
Gilles 'SO- stop be evil'

Respostas:

8

Conforme observado na pergunta, o padrão C requer que exista um valor UCHAR_MAX, de modo que cada variável do tipo unsigned charmantenha 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 tipo unsigned char*, e que haja uma constante sizeof(unsigned char*)tal que cada ponteiro desse tipo seja identificável por uma sequência de sizeof(unsigned char *)valores do tipo unsigned 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.UCHAR_MAXsizeof(unsigned char)101010

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 apenas UCHAR_MAXsizeof(unsigned char)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.

supercat
fonte
Com essa máquina, o que sizeof (char) retornaria?
TLW 26/07
1
@TLW: O mesmo que qualquer outra máquina: 1. As macros CHAR_BITS e CHAR_MAX seriam um pouco mais problemáticas; o padrão não permitiria o conceito de tipos que não têm limites.
Supercat
Opa, eu quis dizer CHAR_BITS, como você disse, desculpe.
TLW 26/07
7

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.

Jared
fonte
Mas as máquinas de Turing com uma fita progredindo infinitamente em apenas uma direção são tão poderosas quanto as máquinas de Turing com uma fita progredindo infinitamente em duas direções. Além disso, vários threads podem ser simulados por um agendador. De qualquer forma, nem precisamos de uma biblioteca de threads.
xamid 7/03
3

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

  • definir uma estrutura que possa ser usada como uma lista vinculada dupla para representação em fita
    typdef struct {
      cell_t * pred; // célula à esquerda
      cell_t * succ; // célula à direita
      int val; // valor da célula
    } cell_t 

O headserá um ponteiro para uma cell_testrutura

  • definir uma estrutura que possa ser usada para armazenar o estado atual e um sinalizador
    typedef struct {
      estado int;
      sinalizador int;
    } info_t 
  • em seguida, defina uma função de loop único que simule um Universal TM quando a cabeça estiver entre os limites da lista de links duplos; quando a cabeça atingir um limite, defina o sinalizador da estrutura info_t (HIT_LEFT, HIT_RIGHT) e retorne:
void simulate_UTM (célula_t * cabeça, info_t * informação) {
  while (true) {
    head-> val = UTM_nextsymbol [info-> estado, head-> val]; // escreve símbolo
    info-> state = UTM_nextstate [info-> state, head-> val]; // próximo estado
    if (info-> state == HALT_STATE) {// imprime se aceita e sai do programa
       putchar ((info-> estado == ACCEPT_STATE)? '1': '0');
       saída (0);
    }
    int move = UTM_nextmove [info-> estado, cabeça-> val];
    if (move == MOVE_LEFT) {
      cabeça = cabeça-> pred; // vire à esquerda
      if (head == NULL) {info-> flag = HIT_LEFT; Retorna; }
    } outro {
      cabeça = cabeça-> succ; // move para a direita
      if (head == NULL) {info-> flag = HIT_RIGHT; Retorna; }
    }
  } // ainda no limite ... continue
}
  • em seguida, defina uma função recursiva que primeiro chame a rotina UTM de simulação e depois se chame recursivamente quando a fita precisar ser expandida; quando a fita precisa ser expandida na parte superior (HIT_RIGHT), não há problemas; quando ela precisa ser deslocada na parte inferior (HIT_LEFT), basta mudar os valores das células usando a lista vinculada dupla:
empilhador nulo (cell_t * top, cell_t * bottom, cell_t * head, info_t * info) {
  simulate_UTM (cabeça, informações);
  cell_t newcell; // a nova célula
  newcell.pred = top; // atualiza a lista vinculada dupla com a nova célula
  newcell.succ = NULL;
  top-> succ = & newcell;
  newcell.val = EMPTY_SYMBOL;

  switch (info-> clique) {
    caso HIT_RIGHT:
      empilhador (& newcell, bottom, newcell, info);
      quebrar;
    caso HIT_BOTTOM:
      cell_t * tmp = nova célula;
      while (tmp-> pred! = NULL) {// aumenta valores
        tmp-> val = tmp-> pred-> val;
        tmp = tmp-> pred;
      }
      tmp-> val = EMPTY_SYMBOL;
      empilhador (& newcell, bottom, bottom, info);
      quebrar;
  }
}
  • a fita inicial pode ser preenchida com uma função recursiva simples que cria a lista vinculada dupla e, em seguida, chama a stackerfunção quando lê o último símbolo da fita de entrada (usando readchar)
void init_tape (célula_t * parte superior, célula_t * parte inferior, info_t * informação) {
  cell_t newcell;
  int c = readchar ();
  if (c == END_OF_INPUT) empilhador (& superior, inferior, inferior, informações); // não há mais símbolos, comece
  newcell.pred = top;
  if (top! = NULL) top.succ = & newcell; else bottom = & newcell;
  init_tape (& newcell, bottom, info);
}

EDIT: depois de pensar um pouco sobre isso, há um problema com os ponteiros ...

se toda chamada da função recursiva stackerpuder 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).

Marzio De Biasi
fonte
3
stackernewcellstacker2n/sns=sizeof(cell_t)
@ Gilles: você está certo (veja minha edição); se você limitar a profundidade de recursão você começa um autômato finito
Marzio De Biasi
@MarzioDeBiasi Não, ele está errado, pois se refere a uma implementação concreta que o padrão não pressupõe. Na verdade, não há limite teórico para a profundidade de recursão em C . A escolha de usar uma implementação baseada em pilha limitada não diz nada sobre os limites teóricos da linguagem. Mas a totalidade de Turing é um limite teórico.
xamid 7/03
0

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 exemplo a*, tudo bem, mas b^ksó funciona para um número finito de ks).

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?

bitmask
fonte
5
O que é um "ponteiro de pilha"? (Observe que a palavra “pilha” não aparece no padrão C.) Minha pergunta é sobre C como uma classe de linguagens formais, não sobre implementações de C em um computador (que são obviamente máquinas de estados finitos). Se você deseja acessar a pilha de chamadas, deve fazê-lo da maneira fornecida pelo idioma. Por exemplo, usando o endereço dos argumentos da função - mas qualquer implementação fornecida possui apenas um número finito de endereços, o que limita a profundidade da recursão.
Gilles 'SO- stop be evil'
Modifiquei minha resposta para excluir o uso de um ponteiro de pilha.
bitmask
1
Não entendo para onde você está indo com sua resposta revisada (além de alterar a formulação de funções computáveis ​​para linguagens reconhecidas). Como as funções também têm um endereço, você precisa de uma implementação grande o suficiente para implementar qualquer máquina de estados finitos. A questão é se e como uma implementação C poderia fazer mais (por exemplo, implementar uma máquina de Turing universal) sem depender de um comportamento não definido.
Gilles 'SO- stop be evil'
0

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:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else reject();
  for(it = back; it != NULL; it = *it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

{anbncn}

Pelo menos, acho que isso funciona. Pode ser que eu esteja cometendo algum erro fundamental, no entanto.

Uma versão fixa:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else for(it = back; it != NULL; it = * (void **) it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}
Ben Standeven
fonte
Bem, não é um erro fundamental, mas it = *itdeve ser substituído por it = * (void **) it, caso contrário, *ité do tipo void.
Ben Standeven
Eu ficaria muito surpreso se viajar a pilha de chamadas assim seria definido o comportamento em C.
Radu Grigore
Ah, isso não vai funcionar, porque o primeiro 'b' faz com que read_a () falhe e, portanto, desencadeia uma rejeição.
Ben Standeven
Mas é legítimo percorrer a pilha de chamadas dessa maneira, uma vez que o padrão C diz: "Para um objeto desse tipo [isto é, com armazenamento automático] que não possui um tipo de matriz de comprimento variável, sua vida útil se estende da entrada no bloco com que está associado até a execução desse bloco terminar de qualquer maneira (inserir um bloco fechado ou chamar uma função suspende, mas não termina, a execução do bloco atual.) Se o bloco for inserido recursivamente, uma nova instância do objeto é criado sempre. " Portanto, cada chamada de read_triple criaria um novo ponteiro que pode ser usado na recursão.
Ben Standeven
2
2CHAR_BITsizeof(char*)
0

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

Conforme observado na pergunta, o padrão C requer que exista um valor UCHAR_MAXtal que toda variável do tipo char não assinado sempre mantenha um valor entre 0 e UCHAR_MAXinclusive. Além disso, exige que todo objeto alocado dinamicamente seja representado por uma sequência de bytes que seja identificável por meio de ponteiro do tipo char não assinado *, e que haja uma constante sizeof(unsigned char*)tal que todo ponteiro desse tipo seja identificável por uma sequência de sizeof(unsigned char *)valores do tipo não assinado Caracteres.

unsigned char*N{0,1}sizeof(unsigned char*){0,1}sizeof(unsigned char)Nsizeof(unsigned char*)Nω

Nesse ponto, deve-se verificar se o padrão C realmente permitiria isso.

sizeofZ

Alexey B.
fonte
1
Muitas operações em tipos integrais são definidas para ter um resultado que é “módulo reduzido um a mais que o valor máximo representável no tipo de resultado”. Como isso funcionaria se esse máximo fosse um ordinal não finito?
Gilles 'SO- stop be evil'
@ Gilles Este é um ponto interessante. De fato, não está claro qual seria a semântica 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).
Alexey B.
1
uintptr_tteria 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ém size_tdeve 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 que UINT_MAX+1deve transbordar.
Gilles 'SO- stop be evil'
Também é um bom argumento. De fato, temos vários tipos (ponteiros e size_t) que devem ser ℕ, ℤ ou alguma construção baseada neles (para size_t se for algo como ℕ ∪ {ω}). Agora, se para alguns desses tipos, o padrão exigir uma macro que defina o valor máximo (PTR_MAX ou algo parecido), as coisas ficarão complicadas. Mas até agora eu era capaz de financiar apenas os requisitos de macros MIN / MAX para tipos não-ponteiros.
Alexey B.
Outra possibilidade a ser investigada é definir os size_ttipos 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 de uint x = (uint)ωnão está claro para mim. Mais uma vez, podemos pegar 0 ao acaso, mas parece um pouco feio.
Alexey B.