O que são orientações práticas para a avaliação de uma linguagem "de Turing Perfeição"?

https://stackoverflow.com/questions/449014

19-08-2019
|

Pergunta

Eu li "o-que-é-turing-completo" e a página da wikipédia, mas estou menos interessado em uma prova formal de que, na prática, implicações de ser Turing Completa.

O que eu estou realmente tentando decidir é se o brinquedo língua que eu acabei desenvolvida poderia ser usado como um uso geral da linguagem.Eu sei que posso provar é se eu posso escrever uma máquina de Turing com ele.Mas eu não quero passar por esse exercício até que eu estou bastante certo de sucesso.

Existe um conjunto mínimo de recursos, sem que Turing Integralidade é impossível?Existe um conjunto de características que praticamente garante a integralidade?

(Meu palpite é que a ramificação condicional e lida/escrita de memória, vai ficar-me quase lá)

EDITAR:

Eu acho que eu tenho ido em uma tangente, dizendo: "Turing Completa".Eu estou tentando adivinhar com razoável confiança de que um recém-inventado a linguagem com um determinado conjunto de recurso (ou, em alternativa, uma VM com um determinado conjunto de instruções) seria capaz de calcular qualquer coisa vale a pena computação.Eu sei que provar que você pode construir uma máquina de Turing com ele é de um jeito, mas não a única.

O que eu estava esperando era um conjunto de diretrizes como:"se ele pode fazer X,Y e Z, pode provavelmente fazer qualquer coisa".

Solução

Você precisa de algum tipo de construção de alocação dinâmica (malloc ounew ou cons fará) e funções recursivas ou alguma outra maneira de escrever um loop infinito. Se você tem isso e pode fazer qualquer coisa interessante, você quase certamente está preenchido.

O cálculo Lambda é equivalente a poder a uma máquina de Turing e, se você implementar o Lambda Cálculus, é realmente muito divertido escrever programas Lambda Cálculo. Caminho Mais divertido do que escrever um programa de escrita para uma máquina de Turing!

A única implicação prática da completude de Turing que estou ciente é que você pode escrever programas que não terminam. Eu usei algumas línguas de fins especiais que garantem a rescisão e, portanto, são não Turing-complete. Às vezes, é útil desistir do poder expressivo extra em troca de terminação garantida.

Outras dicas

'Turing Completity' descreve a propriedade de poder expressar qualquer arbitrário computação algorítmica, qual era o ponto de Máquina de Turing em primeiro lugar. Um idioma ou sistema lógico pode ser descrito como 'Turing completo' se tiver essa propriedade. De uma perspectiva prática, todas as linguagens de programação de uso geral - e um número surpreendentemente grande de fins especiais - podem fazer isso para uma definição adequadamente frouxa (veja abaixo).

No entanto, uma definição estrita de integridade de Turing implica capacidade de armazenamento infinito, o que, obviamente, não é fisicamente possível. Diante disso, nenhuma máquina física pode estar completa, mas essa restrição geralmente é relaxada (pelo menos informalmente) ao atribuir a integridade de Turing a uma linguagem de programação. Um teste trivial de integridade de Turing para um idioma é se o idioma pode ser usado para implementar um simulador de máquina Turing.

Um exemplo de um sistema generalizado que não está completo é a álgebra relacional, a base teórica por trás do SQL, conforme descrito no artigo de Codd Um modelo relacional para grandes bancos de dados compartilhados. Álgebra relacional tem a propriedade de Godel completude, o que significa que ele pode expressar qualquer cálculo que possa ser definido em termos de Cálculo de predicado de primeira ordem (ou seja, expressões lógicas ordinárias). No entanto, não é preenchido, pois não pode expressar uma computação algorítmica arbitrária.

Observe que a maioria, se não todos os dialetos SQL práticos, estende o modelo relacional puro com construções processuais na medida em que estão atingindo a definição, conforme normalmente aplicado às linguagens de programação. No entanto, uma consulta SQL individual em geral não é.

Alguns exemplos mais flagrantes de idiomas completos específicos de domínio são Tex e sendmail.cf,. Neste último caso, há realmente um exemplo famoso de alguém usando sendmail.cf para Implementar um simulador universal de máquina de Turing.

Se você pode escrever um Brainf $ &# Intérprete em seu idioma, é turing-complete. LOLCODE Foi provado que o Turing está preenchido exatamente dessa maneira.

Exemplos de idiomas que não são completos com frequência loops limitados, Curti:

for i=1 to N {...}

mas falta ilimitado Loops que verificam uma condição mais geral, como:

while bool_expr {...}

Se todas as construções possíveis de loops forem delimitadas, seu programa é garantido para terminar. E, embora uma garantia de rescisão incondicional seja potencialmente útil, também é uma indicação de que o idioma não está completo.

Observe também que pregar tudo possível Construções de loop podem ser difíceis; Por exemplo, tenho certeza de que os modelos C ++ não pretendiam ser completos ...

Não tenho certeza se existe um "conjunto mínimo de recursos", mas para provar que um idioma está completo, você só precisa provar que ele pode imitar outro sistema completo de Turing (não necessariamente uma máquina de Turing), desde que o Sabe -se que outro sistema está completo. http://en.wikipedia.org/wiki/Turing_Complete#examples tem uma lista inteira de sistemas completos de Turing. Alguns deles são mais simples que as máquinas Turing.

Gostaria de adicionar uma ressalva ao que Norman Ramsey disse: uma máquina de Turing tem memória infinita e, portanto, linguagens de programação que são consideradas completas estão apenas sob a suposição de que a memória também é infinita.

O Brainfuck está completo e possui apenas estruturas de loop e incrementação/decrementação da memória, então isso é suficiente.

Por outro lado, não há como modificar qualquer valor no cálculo lambda, mas está completo, por isso é claramente possível fazê -lo sem memória mutável.

Provavelmente seu programa não tem nada a ver com o cálculo lambda, por isso, por uma resposta prática, o mínimo deve ser

Uma maneira de escrever para uma variável
Uma maneira de ler para uma variável
Uma forma de goto condicional (se declaração, enquanto loop, etc)

Não me lembro de ver nada como Recursos mínimos para a integridade de Turing. No entanto, se o seu idioma suporta loops e ramificações condicionais, as chances de estarem completas são boas. No entanto, a única maneira de provar que ainda é similar uma máquina de Turing ou outra linguagem completa de Turing.

Se você pode implementar uma máquina de Turing (na medida em que elas podem ser implementadas, pois elas são construções matemáticas com memória ilimitada [o tamanho da fita é Infinte]), você pode ter certeza de que está completo.

Algumas indicações:

Você pode verificar a memória e manipulá -la com base no valor atual, além de usá -lo para controlar o fluxo do programa.
Essa memória pode ser alocada na memória, strings que você pode anexar, uma pilha na qual você pode alocar memória por meio de recursão etc.
O fluxo do programa pode ser através da iteração ou por meio de recursão baseada em seleção.

Qualquer idioma capaz de não terminação é praticamente completo. Você pode tornar um idioma que não termina a terminação, fornecendo estruturas de loops ilimitadas (como enquanto os loops ou um goto que pode alcançar a si mesmo novamente) ou, dando-lhe recursão geral (deixando uma função se chamar sem restrição.)

Uma vez que você são Turing completo, você pode fazer coisas como interpretar outros idiomas completos, incluindo os seus.

A verdadeira questão é "De que é o bem?" Se o seu idioma for usado em um domínio específico para resolver problemas específicos, pode ser melhor encontrar uma maneira de expressar as soluções em um idioma que não está completo e, portanto, garantido para dar uma resposta.

Você sempre pode adicionar a completude, escrevendo "faça isso, isso ou qualquer outra coisa; mas faça-o com o resultado fornecido por x" em qualquer outro idioma completo, onde X é fornecido por um idioma completo que não toca.

Claro, se você deseja usar apenas um idioma, provavelmente era melhor ser completo ...

Você pode tentar imitar um Oisc (Computador de um conjunto de instruções). Se você puder imitar uma das instruções lá, como essas instruções únicas podem ser usadas para compor uma máquina completa de Turing, você provou que seu idioma também deve estar completo.

Existe um conjunto mínimo de recursos, sem que Turing Integralidade é impossível?Existe um conjunto de características que praticamente garante a integralidade?

Sim, você precisa ter o controle de fluxo condicional nos dados:o que é muitas vezes expresso como if.Por exemplo, um +-*/ calculadora de bolso não é Turing-completa, já que não há nenhuma maneira de expressar condicionais.

Você também precisa ser capaz de expressar um salto para um ponto anterior no programa, em cima do que você poderia implementar um loop.Por exemplo BPF, que proíbe saltos para trás para garantir que o programa irá terminar, também não Turing completa.

Você precisa de algum de armazenamento que é legível e gravável e arbitrariamente grande.Por exemplo, uma língua que tem apenas dois de 32 bits variáveis é limitado no que pode calcular.Você tem muitas opções para como o armazenamento é estruturado:memória endereçada por ponteiros, arrays, pilhas, contras as células, pura estruturas de dados, etc.

Em cima desses você pode construir cada linguagem de programação:pode não ser fácil ou rápido, mas é o suficiente.

... do que nas implicações práticas de ser completo completo.

Duvido que haja implicações práticas de estar completo.

Se você olhar para alguns dos exemplos de máquinas completas de Turing, por exemplo, o original Máquina de Turing, você verá que estão tão longe de serem úteis para cálculos reais que o conceito deve ser apenas de interesse teórico.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow