Qualquer idioma que não esteja completo em Turing não pode escrever um intérprete para si próprio. Não tenho idéia de onde li isso, mas já o vi usado várias vezes. Parece que isso dá origem a uma espécie de linguagem completa "final" não-Turing; aquele (s) que só podemser interpretado por uma máquina de Turing. Essas linguagens não seriam necessariamente capazes de calcular todas as funções totais de naturais para naturais nem necessariamente seriam isomórficas (ou seja, talvez as línguas definitivas A e B existam de tal forma que exista uma função F que A possa computar, mas B não possa). A Agda pode interpretar o sistema T de Godel e a Agda é total, de modo que uma linguagem tão definitiva seja estritamente mais poderosa que o sistema T de Godel parece. Parece-me que esse idioma seria pelo menos tão poderoso quanto o agda (embora eu não tenha provas, apenas um palpite).
Alguma pesquisa foi feita nesse sentido? Quais resultados são conhecidos (ou seja, é conhecida uma linguagem "definitiva")?
Bônus: Estou preocupado que exista um caso patológico que não possa computar funções que o Sistema T de Godel ainda possa ser interpretado apenas por uma máquina de Turing porque permite que algumas funções realmente estranhas sejam computadas. É esse o caso ou podemos saber que essa linguagem seria capaz de calcular qualquer coisa que o Sistema T de Godel pudesse computar?
Respostas:
Esta é uma pergunta mal formulada, então vamos entender melhor. Eu vou fazer o estilo da teoria da computabilidade. Assim, usarei números em vez de cadeias: um código-fonte é um número, em vez de uma cadeia de símbolos. Realmente não importa, você pode substituir por s t r i n gN string abaixo.
Deixe ser uma função de emparelhamento⟨m,n⟩ .
Digamos que uma linguagem de programação seja fornecida pelos seguintes dados:L = ( P, E v )
O fato de ser decidível significa que existe um mapa computável total v a l i d : N → { 0 , 1 } tal que v a l i d ( n ) = 1P v a l i d: N → { 0 , 1 } . Informalmente, estamos dizendo que é possível dizer se uma determinada string é um pedaço de código válido. A função e v é essencialmente um intérprete para a nossa linguagem: e v ( m , n ) executa o código m na entrada nv a l i d(n)=1⟺n∈P ev ev(m,n) m n - o resultado pode ser indefinido.
Agora podemos introduzir alguma terminologia:
Outras definições de " interpreta L 2 " são possíveis, mas não permita que eu entre nisso agora.L1 L2
Dizemos que e L 2 são equivalentes se eles se interpretarem.L1 L2
Existe a "linguagem mais poderosa" das máquinas de Turing (que você chama de "máquina de Turing") na qual n ∈ N é uma codificação de uma máquina de Turing e φ ( n , m ) é a função computável parcial que "executa a máquina de Turing codificada por n na entrada m ". Esse idioma pode interceptar todos os outros idiomas, obviamente, uma vez que exigimos e vT=(N,φ) n∈N φ(n,m) n m ev ser computável.
Nossa definição de linguagens de programação é muito descontraída. Para o seguinte, vamos exigir mais três condições:
A classic result is this:
Theorem: If a language can interpret itself then it is not total.
Proof. Supposeu is the universal program for a total langauge L implemented in L , i.e., for all m∈P and n∈N ,
Observe that we could replace the successor map with any other fixpoint-free map.
Here is a little theorem which I think will clean up a misunderstanding.
Theorem: Every total language can be interpreted by another total language.
Proof. LetL be a total language. We get a total L′ which interprets L by adjoining to L its evaluator ev . More precisely, let P′={⟨0,n⟩∣n∈P}∪{⟨1,0⟩} and define ev′ as
Exercise: [added 2014-06-27] The languageL′ constructed above is not closed under composition. Fix the proof of the theorem so that L′ satisfies the extra requirements if L does.
In other words, you never need the full power of Turing machines to interpret a total languageL – a slightly more powerful total language L′ suffices. The language L′ is strictly more powerful than L because it interprets L , but L does not interpret itself.
fonte
is_total
, which is otherwise non-cmputable, but couldn't implement evaluation (because you'd have to also compute the bit of the resulting function). In general I would say it's not a programming language if you can't even implement a parser for it.This statement is incorrect. Consider the programming language in which the semantics of every string is "Ignore your input and halt immediately". This programming language is not Turing complete but every program is an interpreter for the language.
fonte