Podemos representar todos os programas de computador como gráficos?

7

Eu estava pensando outro dia, e me ocorreu que todos os programas de computador parecem representáveis ​​como um gráfico (uma árvore de sintaxe abstrata, por exemplo) ou, uma vez que expressões comuns são combinadas, um gráfico de sintaxe abstrata.

Ocorreu-me que talvez qualquer programa de computador possa ser representado como um desses gráficos + semântica de avaliação anexada a ele. Estou curioso para saber se isso é universalmente verdadeiro para uma máquina de turing (suponho que você possa obter um gráfico potencialmente infinito, mas isso é matemática, então tudo bem). Eu tenho pensado nisso e em muitas coisas, como sistemas de tipos fortes e que se encaixam bem nessa abstração (eles impõem restrições estruturais no gráfico). Você pode até considerar o sistema de tipos como seu próprio programa e representá- lo como um gráfico diferente + semântica de avaliação operando no gráfico do programa ...

Apenas curioso se essa é uma equivalência conhecida ou não.

graphs turing-machines machine-models gct
fonte
É um conceito bastante básico para otimizar o design do compilador.
Khslam
11
Eu posso representar qualquer equação matemática por gráfico. Qual é o ponto?
Val
uma resposta bastante bizarra: sabe-se que as caminhadas aleatórias quânticas em tempo contínuo são capazes de computação universal - na verdade, o mesmo acontece com os computadores quânticos adiabáticos. até diagramas de circuito são graficamente tecnicamente com vértices agindo como funções, e esses também são capazes de computação universal. não é bem o que você estava pensando, parecia :) #
292/14

Respostas:

10

Não sei se é uma equivalência particularmente conhecida, mas é bastante simples quando você pensa sobre isso.

Sabe-se que as máquinas de Turing são equivalentes ao cálculo Lambda (sem tipagem). A tese de Church-Turing propõe que essa é a forma mais poderosa de computação.

O Cálculo Lambda é um sistema de reescrita de termos definido sintaticamente. Essencialmente, é uma linguagem de programação muito simples. Portanto, ele pode ser analisado em uma árvore de sintaxe abstrata (gráfico).

Então nós temos:

  1. Todo programa de computador é representável no cálculo lambda sem tipo.
  2. Todo programa de cálculo lambda pode ser analisado em uma árvore de sintaxe abstrata

Isso significa que todo programa de computador pode ser representado como uma árvore de sintaxe abstrata do Lambda Calculus.

Essas árvores podem não ter muito em termos de propriedades interessantes. Por exemplo, eles definitivamente não são únicos, ou seja, duas árvores diferentes podem executar cálculos idênticos.

jmite
fonte
11
Você também pode usar uma linguagem de programação de uso geral completa (preferencialmente estruturada) de Turing. Além disso, em programas de análise estática, são representados como gráficos com ciclos.
Bellpeace 14/05