Um Turing tarpit é um tipo de linguagem de programação esotérica que se esforça para ser Turing-completa, usando apenas alguns elementos como possível. Brainfuck é talvez o mais conhecido tarpit, mas existem muitos.
-
Iota e Jot são linguagens funcionais com dois e três símbolos, respectivamente, com base no cálculo do combinador SK (I) .
-
OISC ( Um conjunto de instruções de computador ) indica um tipo de cálculo imperativo que requer apenas uma instrução de um ou mais argumentos, geralmente" subtrair e ramificar se menor ou igual a zero ", ou" inverter subtrair e pular se pedir emprestado " " O x86 MMU implementa a instrução anterior e é, portanto, Turing-completo.
Em geral, para que uma linguagem imperativa seja Turing-complete, ela precisa:
-
Uma forma de repetição condicional ou salto condicional (por exemplo,
while
,if
+goto
) -
Uma maneira de ler e escrever alguma forma de armazenamento (por exemplo, variáveis, fita)
Para uma linguagem funcional baseada em lambda-cálculo ser TC, é necessário:
-
A capacidade de abstrair funções sobre argumentos (por exemplo, abstração de lambda, cotação)
-
A capacidade de aplicar funções a argumentos (por exemplo, redução)
Existem, é claro, outras maneiras de olhar para a computação, mas esses são modelos comuns para os tarts de Turing. Observe que os computadores reais não são máquinas de Turing universais porque não têm armazenamento ilimitado. Estritamente falando, eles são “máquinas de armazenamento limitadas”. Se você continuasse adicionando memória a eles, eles assintoticamente aproximariam as máquinas de Turing do poder. No entanto, até máquinas de armazenamento limitadas e máquinas de estados finitas são úteis para computação; eles simplesmente não são universais .
Estritamente falando, E / S não é necessária para Turing-completude; TC apenas afirma que uma linguagem pode computar a função que você quer, não que ela possa mostrar o resultado. Na prática, toda linguagem útil tem uma maneira de interagir com o mundo de alguma forma.