Todos os idiomas completos são intercambiáveis

26

Note que, embora eu saiba programar, sou bastante iniciante na teoria do CS.

De acordo com esta resposta

Turing completude é um conceito abstrato de computabilidade. Se um idioma é Turing completo, ele é capaz de fazer qualquer cálculo que qualquer outro idioma completo de Turing possa fazer.

E qualquer programa escrito em qualquer idioma completo de Turing pode ser reescrito em outro .

Está bem. Isso faz sentido. Posso traduzir (compilar) C em Assembly (e faço isso todos os dias!) E traduzir o Assembly em C (você pode escrever uma máquina virtual em C). E o mesmo se aplica a qualquer outro idioma - você pode compilar qualquer idioma no Assembly e executá-lo em uma VM escrita em outro outro idioma.

Mas qualquer programa escrito em um idioma completo de Turing pode ser reescrito em outro?

E se minha montagem tiver um código de operação LIGHTBUTTON? Fisicamente, não posso emular esse idioma em um sistema (idioma) sem uma lâmpada.

Está bem. Então você dirá que, como estamos lidando com a teoria dos computadores , não estamos discutindo limitações de dispositivos físicos.

Mas e um dispositivo que não tem multiplicação? divisão? Que eu saiba (embora isso seja mais uma pergunta para math.SE), não se pode emular multiplicação (e definitivamente não divisão) com adição e subtração [1].

Então, como um "idioma completo completo" (que pode adicionar, subtrair e pular) emularia outro idioma que pode adicionar, subtrair, multiplicar e pular?

EDITAR

[1] Em números reais arbitrários.

excursão
fonte
33
Os números reais pertencem ao domínio da Hyper-Turing-Computation. Uma máquina de Turing não pode lidar com números reais; portanto, eles são irrelevantes para a integridade de Turing.
Jörg W Mittag 01/01
3
Relacionado: um conjunto de instruções em linguagem assembly com apenas uma instrução ainda é poderoso o suficiente para construir um computador universal: en.wikipedia.org/wiki/One_instruction_set_computer . Por exemplo, "Subtraia e ramifique se for menor ou igual a zero" com operandos de memória. Será lento comparado a um x86 moderno, mas a taxa de desempenho é finita para qualquer programa.
Peter Cordes
11
Nenhuma máquina física (realmente existente) é ou pode ser completa em Turing, porque a perfeição em Turing exige armazenamento infinito e o universo não é infinito. Daqui resulta que a resposta afirmativa para se duas máquinas abstratas são equivalentes não ajuda a responder à pergunta se duas aproximações físicas dessas máquinas são equivalentes.
Ben
2
@ PeterCordes: Eu suponho que quando você diz que a proporção é finita, você simplesmente quer dizer que qualquer tarefa que seja concluída em tempo finito em um deles o fará em tempo finito em ambos - não que para qualquer máquina em particular (não incluindo a entrada) haja qualquer limite finito para o quão alto a taxa pode chegar para algumas entradas. Penso que se poderia construir máquinas completas de Turing para as quais se poderia selecionar entradas que tornariam a relação arbitrariamente alta - possivelmente nem mesmo uma função computável do tamanho da entrada.
Supercat
6
Não sei de onde você tira a idéia de que "não se pode emular multiplicação (e definitivamente não divisão) com adição e subtração". Foi ensinado desde o ensino fundamental quando aprender a multiplicar
phuclv

Respostas:

55

A perfeição de Turing diz uma coisa e apenas uma coisa: um modelo de computação é Turing-complete, se qualquer computação que pode ser modelada por uma Máquina de Turing também pode ser modelada por esse modelo.

Então, quais são os cálculos que uma máquina de Turing pode modelar? Bem, acima de tudo, Alan Turing e todos os seus colegas estavam sempre interessados ​​em funções em números naturais. Portanto, a Máquina de Turing (e o cálculo λ, o cálculo combinador SK, funções urs-recursivas, ...) falam apenas sobre a computabilidade das funções em números naturais. Se você não está falando sobre uma função em números naturais, o conceito de completeza de Turing nem faz sentido, simplesmente não é aplicável.

Observe, no entanto, que podemos codificar muitas coisas interessantes como números naturais. Podemos codificar strings como números naturais, podemos codificar gráficos como números naturais, podemos codificar booleanos como números naturais. Podemos codificar as Máquinas de Turing como números naturais, o que nos permite criar Máquinas de Turing que falam sobre Máquinas de Turing!

E, é claro, nem todas as funções em números naturais são computáveis. Uma máquina de Turing pode computar apenas algumas funções em números naturais, o cálculo λ pode calcular apenas algumas funções em números naturais, o cálculo combinador SK pode calcular apenas algumas funções em números naturais,…. Surpreendentemente (ou não), verifica-se que todo modelo de computação (que é realmente realizável em nosso universo físico) pode computar as mesmas funções em números naturais (pelo menos para todos os modelos que encontramos até agora). [Nota: obviamente, existem modelos mais fracos de computação, mas ainda não encontramos um que seja mais forte, exceto alguns que são obviamente incompatíveis com o nosso universo físico, como modelos usando números reais ou viagens no tempo.]

Esse fato, que depois de muito tempo pesquisando muitos modelos diferentes, descobrimos, todas as vezes, que eles podem calcular exatamente as mesmas funções, é a base da Tese da Igreja-Turing, que diz (grosso modo) que todos modelos de computação são igualmente poderosos, e todos eles capturam a noção "ideal" do que significa ser "computável". (Há também um segundo aspecto mais filosófico dos CTT, a saber, que um ser humano seguindo um algoritmo também pode calcular exatamente as mesmas funções que uma MT pode calcular e não mais.)

No entanto , nada disso diz algo sobre

  • quão eficientes são os vários modelos
  • quão conveniente eles são usar
  • o que mais eles podem fazer além de funções de computação nos números naturais

E que é precisamente onde as diferenças entre diferentes modelos de computação (e linguagens de programação) entram em jogo.

Como exemplo de desempenho diferente, uma máquina de acesso aleatório e uma máquina de Turing podem copiar uma matriz. Porém, uma RAM precisa de operações para fazer isso, enquanto uma TM precisa de operações , pois precisa pular os elementos da matriz para copiar cada elemento e existem elementos para copiar.O ( s i z e 2 a r r a y ) s i z e a r r a y s i z e a r r a yO(sEuzeumarrumay)O(sEuzeumarrumay2)sEuzeumarrumaysEuzeumarrumay

Como exemplo de conveniência diferente, você pode comparar o código escrito em uma linguagem de alto nível, o código escrito em assembly e a descrição de uma TM para resolver o mesmo problema.

E seu interruptor de luz é um exemplo do terceiro tipo de diferença, coisas que alguns modelos podem fazer que não funcionam em números naturais e, portanto, não têm nada a ver com a perfeição de Turing.

Para responder suas perguntas específicas:

Mas qualquer programa escrito em um idioma completo de Turing pode ser reescrito em outro?

Não. Somente se o programa computar uma função computável de Turing em números naturais. E mesmo assim, pode precisar de uma codificação complexa. Por exemplo, o cálculo λ nem sequer possui números naturais, eles precisam ser codificados usando funções (porque funções é a única coisa que o cálculo λ possui).

Essa codificação da entrada e da saída pode ser muito complexa, assim como a expressão do algoritmo. Portanto, embora seja verdade que qualquer programa pode ser reescrito, o programa reescrito pode ser muito mais complexo, muito maior, usar muito mais memória e muito mais lento.

E se minha montagem tiver um código de operação LIGHTBUTTON? Fisicamente, não posso emular esse idioma em um sistema (idioma) sem uma lâmpada.

Uma lâmpada não é uma função computável de Turing em números naturais. Realmente, uma lâmpada não é uma função nem uma computação. Ligar e desligar uma lâmpada é um efeito colateral de E / S. As máquinas de Turing não modelam efeitos colaterais de E / S e a conclusão de Turing não é relevante para eles.

Em números reais arbitrários.

A perfeição de Turing lida apenas com funções computáveis ​​em números naturais, não se preocupa com números reais.

A perfeição de Turing simplesmente não é muito interessante quando se trata de perguntas como a sua por dois motivos:

  1. Não é um obstáculo muito alto. Tudo que você precisa é IF, GOTO, WHILE, e uma variável único inteiro (assumindo que a variável pode conter arbitrariamente grandes números inteiros). Ou recursão. Muitas e muitas coisas estão completas em Turing. O jogo de cartas Magic: The Gathering está completo em Turing. CSS3 é Turing-completo. O sendmailarquivo de configuração é Turing-complete. O Intel x86 MMU é Turing-complete. A MOVinstrução Intel x86 é Turing-complete. As animações do PowerPoint são completas de Turing. O Excel (sem scripts, usando apenas fórmulas) é Turing-complete. O protocolo de roteamento BGP é Turing-complete. sedé Turing completo. As mod_rewriteregras do Apache são completas de Turing. Google for " (acidentalmente ou surpreendentemente) completo"para encontrar outros exemplos interessantes. Se quase tudo estiver completo em Turing, ser completo em Turing deixa de ser uma propriedade interessante.
  2. Na verdade, não é necessário ser útil. Muitas coisas úteis não são completas para Turing. CSS antes da versão 3 não é Turing-completo (eo fato de que CSS3 é não é realmente usado por qualquer pessoa). O SQL antes de 1999 não era completo para Turing, mas ainda era tremendamente útil. A linguagem de programação C sem bibliotecas adicionais não parece estar completa com Turing . As linguagens de tipo dependente são, mais ou menos por definição, não completas para Turing; no entanto, você pode escrever sistemas operacionais, servidores da Web e jogos neles.

Edwin Brady, autor de Idris, usa o termo "Tetris-complete" para falar sobre alguns desses aspectos. Ser completo com Tetris não é definido rigorosamente (exceto o óbvio "pode ​​ser usado para implementar o Tetris"), mas abrange coisas como ser de alto nível e expressivo o suficiente para que você possa escrever um jogo sem enlouquecer, ser capaz de interagir com o mundo externo (entrada e saída), ser capaz de expressar efeitos colaterais, ser capaz de escrever um loop de eventos, ser capaz de expressar programação reativa, assíncrona e simultânea, ser capaz de interagir com o sistema operacional, ser capaz interagir com bibliotecas estrangeiras (em outras palavras: poder chamar e ser chamado pelo código C) e assim por diante. Essas são características muito mais interessantes de uma linguagem de programação de propósito geral do que a integridade de Turing.


Você pode achar interessante a minha resposta à pergunta que você vinculou , que aborda alguns dos mesmos pontos, embora ela responda a uma pergunta diferente.

Jörg W Mittag
fonte
7
Eu realmente gosto dessa resposta, mas acho que vale a pena notar que podemos representar todo tipo de coisas interessantes por números naturais. Por exemplo, podemos representar seqüências de caracteres por números naturais, podemos representar gráficos por números naturais, podemos representar todo o estado da memória de um computador por um número natural. Números reais podem ser codificados como funções em números naturais e (muitas) funções em números naturais podem ser codificados por números naturais. Portanto, limitar as funções de números naturais para números naturais não é uma grande limitação - a menos que esteja escuro e você queira que o computador acenda a luz.
Theodore Norvell
3
Boa resposta, mas esta: "ser completo em Turing deixa de ser uma propriedade interessante" é simplesmente errado. Se algo está completo em Turing, seu problema de parada é Turing-completo por redução computável ao problema de parada para máquinas de Turing. Por exemplo, o jogo de cartas Magic: The Gathering está completo em Turing. Isso significa que suas regras são indecidíveis , ou seja, no caso geral, é impossível deduzir computavelmente qual será o seguinte estado do jogo, que é uma propriedade muito interessante. Mais seriamente, usamos a redundância e reduções de Turing para provar problemas indecidíveis.
quicksort
Turing e seus colegas estavam interessados ​​em funções em números naturais, mas as máquinas de Turing realmente não lidam com números, elas lidam com cadeias de símbolos. Obviamente, você pode interpretar trivialmente linhas finas de símbolos em um alfabeto finito conhecido como números naturais, mas as TMs não fazem diretamente "numerosas" coisas com suas entradas, elas apenas manipulam os "dígitos". Na verdade, ele precisa de um pouco de lógica para passar das descrições padrão das TMs para "funções em números naturais"; ao trabalhar com TMs, você codifica números naturais como cadeias, não cadeias como números.
Ben
Essa é obviamente uma ótima resposta, mas temo que vá além do entendimento do OP. O OP já está confuso sobre a implementação da multiplicação em (subconjuntos finitos de) números reais. Diante disso, sua resposta parece implicar que as linguagens de programação completas de Turing não são, de fato, permutáveis ​​para fins de computação pura, quando na realidade são (porque tudo que as CPUs modernas fazem - e não apenas algumas coisas - pode ser codificado como natural). números).
quer tocar hoje
9
@TheodoreNorvell Sobre o assunto de codificar números reais com números naturais. De fato, quase todos os números reais não podem ser codificados por números naturais. O conjunto de números reais que podem ser codificados por números naturais, em virtude de serem codificados por números naturais, é no máximo contável. E como é infinitamente contável, o conjunto mede zero. É um pouco falso dizer que podemos representar números reais em geral com números naturais, pois só podemos representar uma fração infinitesimal deles, ou para ser mais preciso: 0%.
Shufflepants
9

Claro que você pode implementar a multiplicação com adição e subtração:

/* Assume b is positive for simplicity */
int multiply(int a, int b) {
  int res = 0;
  while (b > 0) { res += a; b -= 1; }
  return res;
}

O fato de você provavelmente não fazer isso não torna menos possível.

Divisão é dificilmente mais difícil:

/* Assume a and b are positive for simplicity */
int divide(int a, int b) {
  int res = 0;
  while (a >= b) { res += 1; a -= b; }
  return res;
}

E como você acha que a multiplicação e a divisão são realmente realizadas pelos circuitos da CPU? Dica: não é uma tabela de pesquisa enorme. É mais eficiente do que o anterior, pois a troca de bits também é usada, mas é fundamentalmente implementada em termos de adição e subtração.

rici
fonte
4
2precEusEuon
7
@ouring: Você sabe, a aritmética de ponto flutuante estava disponível antes dos coprocessadores de ponto flutuante.
rici 01/01
6

Nenhuma máquina física (realmente existente) é ou pode ser completa em Turing, porque a perfeição em Turing exige armazenamento infinito e o universo não é infinito.

Daqui resulta que a resposta afirmativa para se duas máquinas abstratas são equivalentes não ajuda a responder à pergunta se duas aproximações físicas dessas máquinas são equivalentes.

Portanto, a equivalência de Turing dos modelos abstratos de (por exemplo) duas linguagens não significa que cada uma pode calcular tudo o que a outra pode computar na prática. Um pode enfrentar limitações físicas antes do outro.

Ben
fonte
Mas a pergunta feita sobre idiomas. Menciona máquinas específicas, mas apenas porque ele não percebe que praticamente nenhuma máquina real opera com números reais.
Shufflepants
3

nm=n+n(m-1 1)m/n=1 1+(m-n)/n

De fato, as operações "adicionar 1", "subtrair 1" e "salto condicional se um registro especificado for zero" são suficientes para tornar um modelo computacional completo de Turing (consulte a máquina de 2 contadores como referência para um modelo computacional muito mínimo de Turing).

22n=n+n2m×2n=2m×nm×(2n+1 1)=m+2m×n

ordenação rápida
fonte
3

tl; dr - Máquinas de Turing são apenas uma descrição lógica básica para a operação de um sistema lógico geral. Eles podem fazer a maioria das coisas que podemos descrever, incluindo chamar opcodes especializados e operações matemáticas construídas.


E se minha montagem tiver um código de operação LIGHTBUTTON? Fisicamente, não posso emular esse idioma em um sistema (idioma) sem uma lâmpada.

Em um modelo de Turing, símbolos como um LIGHTBUTTONcódigo de operação são apenas cadeias de caracteres em qualquer alfabeto que o computador de Turing use.

Portanto, a máquina de Turing seria responsável por produzir a string "LIGHTBUTTON"ou algum valor inteiro que corresponda ao código de operação; se uma entidade externa age ou não sobre ela, não é da conta do computador de Turing.

Programas C têm a mesma limitação. LIGHTBUTTONOu seja, um programa C só pode chamar o código de operação , no entanto, se a CPU efetua ou não uma operação associada a esse código de operação depende da CPU.


Mas e um dispositivo que não tem multiplicação? divisão? Que eu saiba (embora isso seja mais uma pergunta para math.SE), não se pode emular multiplicação (e definitivamente não divisão) com adição e subtração [em números reais arbitrários].

Sim, uma máquina de Turing poderia fazer essas coisas, mesmo em números reais, na medida em que qualquer lógica descritiva por humanos pudesse. A máquina de Turing pode ser tão simples quanto a automação celular da Regra 110 .

O truque é construir um sistema lógico a partir de qualquer física que a máquina tenha naturalmente. Por exemplo, as CPUs principais podem fazer multiplicação e divisão porque possuem unidades lógicas aritméticas (ALU) . Mas as ULAs não são mágicas; eles são apenas portas lógicas simples . E esses portões lógicos são feitos de transistores . E esses transistores são feitos de areia dopada .

Portanto, para obter um dispositivo completo de Turing para fazer contas, basta programar dessa maneira.

π-π=0 0ππππ=0 0

Nat
fonte
3

Mas qualquer programa escrito em um idioma completo de Turing pode ser reescrito em outro?

Se a entrada para o programa for uma sequência de bits arbitrariamente longa e a saída também for uma sequência de bits arbitrariamente longa, então YES. Supondo que você tenha tempo e energia para reescrevê-lo e que não se importe com o desempenho e que tenha memória física suficiente para ambas as implementações.

As considerações práticas que significam duas linguagens completas de Turing não são intercambiáveis ​​incluem:

  • eles suportam diferentes tipos de entrada e saída (por exemplo, acesso ao banco de dados SQL)

  • eles têm diferentes bibliotecas de tipos de dados (por exemplo, suporte para strings Unicode)

  • eles fornecem diferentes paradigmas de programação otimizados para diferentes tarefas (por exemplo, objetos, threads, corotinas, funções de primeira classe)

  • eles fornecem bibliotecas de funções diferentes (por exemplo, análise e serialização de XML)

Michael Kay
fonte
1

Não. Turing-completeness não tem nada a ver com programas , trata-se de funções matemáticas (ou algoritmos ). Qualquer algoritmo - qualquer cálculo - você pode fazer em C, em qualquer outra linguagem completa de Turing (isso deve ser óbvio). Mas a integridade de Turing na verdade não diz que você pode executar E / S - de maneira alguma. Ele não fala sobre o hardware. Apenas os cálculos.

Você pode estender uma linguagem Turing-completo com qualquer operação de hardware que você quer (tecnicamente, é assim fputce fgetctrabalho em C). Se você pegar duas linguagens completas de Turing e as estender com operações específicas de hardware idênticas , elas permanecerão intercambiáveis. Portanto, sua linguagem assembly com LIGHTBULBoperação é mais poderosa que a completa Turing; você poderia dizer que é Turing completoLIGHTBULB . Para tornar qualquer outro idioma idêntico a ele, ele também precisa estar completo em Turing LIGHTBULB; a maneira mais fácil de fazer isso é adicionar uma LIGHTBULBprimitiva / instrução / função / etc. a ela.

É por isso que as implementações C geralmente oferecem suporte ao assembler embutido ou documentam uma maneira de chamar funções escritas no assembler, e porque implementações de outras linguagens geralmente fornecem uma maneira de chamar funções escritas em C.

Jonathan Cast
fonte