Existem critérios mínimos para uma linguagem de programação ser Turing completa?

Existe um conjunto de construções de linguagem de programação em uma linguagem de programação para que seja considerada Turing Complete?

Pelo que sei da wikipedia , o idioma precisa suportar a recursão ou, aparentemente, deve ser capaz de executar sem parar. Isso é tudo o que existe?

Sempre achei que funções -recursive acertou em cheio. Aqui está o que define todo o conjunto de funções computáveis; é o menor conjunto de funções que contém resp. fechado contra:$\mu$

1. A função constante$0$
2. A função sucessora
3. Selecionando Parâmetros
4. Composição da função
5. Recursão Primitiva
6. O operador (procure o menor tal que ...)$\mu$$x$

Verifique o link acima para obter detalhes; você vê que isso cria uma linguagem de programação muito compacta. Também é horrível programar - sem almoço grátis. Se você deixar cair qualquer um deles, perderá a potência total, portanto, é um conjunto mínimo de axiomas.

Você pode traduzi-los literalmente em elementos sintáticos básicos para programas WHILE , a saber

1. A constante 0
2. Incrementação _ + 1
3. Acesso variável x
4. Concatenação de programa / instrução _; _
5. Loops de contagem regressiva for ( x to 0 ) do _ end
6. Enquanto loops while ( x != 0 ) do _ end

Existe um conjunto de cálculos que precisam ser executáveis ​​em uma linguagem de programação para que seja considerado Turing Complete?

Sim, para ser considerado Turing completo, uma linguagem de programação precisa ser capaz de executar qualquer cálculo que possa ser executado por uma máquina de Turing. Portanto, como requisito mínimo, pode-se implementar uma máquina universal de Turing - ou um intérprete para qualquer outra linguagem completa de Turing - nela.

Pelo que sei da wikipedia, o idioma precisa suportar a recursão ou, aparentemente, deve ser capaz de executar sem parar. Isso é tudo o que existe?

Não. Por exemplo, um idioma em que a única operação permitida é a recursão (ou seja, a única função possível que você pode escrever é f(x) = f(x), não é o Turing completo porque tudo o que você pode escrever nele são programas que nunca terminam. Como eu disse anteriormente, um idioma completo do Turing precisa ser capaz de implementar qualquer computação que possa ser executada por uma máquina de Turing, o que claramente não é suficiente.

Além disso, um idioma não precisa suportar a recursão da maneira que você pensa. Apenas uma maneira irrestrita de expressar loops. Isso pode ser recursão, mas também pode ser um loop while ou goto. Uma linguagem que não possui funções ainda pode estar completa em Turing. E novamente loops ou funções recursivas não são uma condição suficiente. Você ainda precisa executar um código diferente, dependendo de uma condição e calcular novos valores a partir dos antigos (caso contrário, todos os loops / recursões seriam infinitos ou não serão executados).

Quanto à existência de um conjunto mínimo de operações necessárias e suficientes, de modo que qualquer idioma que suporte essas operações seja Turing completo e qualquer idioma que não seja: não, não existe (a menos que você defina "operação" tão vagamente , que se torna sem sentido):

Por exemplo, como eu já disse, existem linguagens completas de Turing que não suportam funções recursivas (ou nenhuma função). Eles ainda podem ser concluídos por Turing se tiverem uma gotodeclaração ou whileloop (e uma maneira de armazenar quantidades arbitrárias de dados). No entanto, uma linguagem com funções recursivas não precisa whilenem gotoser Turing completa. Portanto goto, não estaria no conjunto de operações suficientes necessárias, mas há idiomas que o Turing não está mais completo se você remover goto. Portanto, não existe tal conjunto.

Existem várias instruções únicas que levam a idiomas completos de Turing. O exemplo típico é "subtrair e ramificar se zero". Estes são bem conhecidos no contexto da programação em linguagem assembly. Veja o artigo da Wikipedia para detalhes.

Isso leva a uma caracterização: um idioma é Turing completo se, e somente se, é capaz de simular as operações de busca e armazenamento de números inteiros na memória e de executar a operação "subtrair e ramificar se zero" neles.

Essa não é uma resposta geral para sua pergunta, mas pelo teorema da programação estruturada , tudo o que é necessário é a capacidade de fazer seleção (por exemplo, ifem C / C ++) e repetição (por exemplo, whileem C / C ++). Edit: como apontado por Dave Clarke nos comentários, o teorema da programação estruturada também requer sequência. Inicialmente, não listei isso, pois considerava que o leitor entenderia que também são necessários blocos básicos de outras instruções, como as mencionadas posteriormente para leitura e gravação no armazenamento de memória etc.). É claro que é melhor ser explícito; você precisa ser capaz de fazer essas coisas também.

Como ambos podem ser implementados usando uma instrução de salto condicional (por exemplo, JNZem x86), isso também é suficiente para a equivalência de Turing.

Observe que outras coisas são necessárias, ou seja, a capacidade de escrever um número ilimitado de símbolos (por exemplo, bits ... 0 ou 1) em algum tipo de armazenamento de memória externa. Nesse sentido, computadores reais não são equivalentes a Turing, pois nenhum deles possui uma quantidade infinita de armazenamento. O modelo de Turing ainda é útil, já que a quantidade de memória é geralmente enorme e, mesmo que qualquer problema que um computador real possa resolver possa ser resolvido por um autômato finito determinístico, o uso desse modelo de computação não é particularmente útil (uma vez que o número de estados seria absurdamente enorme).

Observe que isso não está necessariamente em desacordo com a resposta de sepp2k; essa é apenas uma maneira diferente de pensar sobre a mesma pergunta.

EDITAR:

Observe também que você realmente não precisa de ambos ife whileem C / C ++. Você pode simular ifusando whileo seguinte:

bool C;
// some code that sets C
if(C) { /* some other code /* }
// rest of the program

O código a seguir é sempre equivalente:

bool C;
// some code that sets C
bool C2 = C;
while(C2) { /* some other code /* C2 = false; }
// rest of the program

Bem ... a construção deve funcionar e ser possível se você for cuidadoso. Observe também que, se você tiver funções recursivas, também precisará de seleção; como as funções recursivas sem seleção não podem realmente implementar casos base, então qualquer função recursiva resultaria em recursão infinita.

EDITAR:

Além disso, com relação à sua pergunta sobre se a capacidade de escrever um programa que não interrompe é suficiente para a equivalência de Turing, a resposta é não; é necessário, mas não suficiente. Podemos resolver o problema da parada de programas escritos em um idioma que não pode expressar programas que não são interrompidos; a resposta é "o programa pára" para todas as instâncias. No entanto, podemos definir um idioma em que a única instrução faz com que a máquina entre em um loop infinito ... esse idioma não é equivalente a Turing.

$\mathbf{S}$$\mathbf{K}$$(\mathbf{S}\ x\ y\ z) = (x\ z\ (y\ z))$$(\mathbf{K}\ x\ y) = x$

$\mathbf{X}=\lambda x.((x\ \mathbf{S})\ \mathbf{K})$

As construções de linguagem são intercambiáveis

Não há critérios mínimos definidos sobre quais construções devem ser fornecidas nativamente por uma linguagem de programação. Se ele fornece algumas construções estranhas que de alguma forma podem ser complicadas para expressar um sistema completo de Turing, aparentemente essas construções são "tão adequadas" quanto quaisquer outras.

Para provar isso - uma linguagem que fornece apenas uma operação "subtrair e ramificar se zero" é Turing concluída; existem linguagens completas de Turing que não fornecem uma construção "substrato e ramificação se zero" separada; portanto, não há construção ou conjunto de construções que seja obrigatório.

Os efeitos de qualquer construção de linguagem completa do TP podem ser emulados pelas construções de qualquer outra linguagem completa do TP.