Um idioma total que apenas um idioma completo de Turing pode interpretar

16

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 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?

Jake
fonte
2
Suas declarações são confusas devido ao modo como você usa a terminologia. Em vez de confiar na terminologia, tente expor sua pergunta de maneira matematicamente rigorosa e clara, para que possamos entendê-la. O que você quer dizer com linguagem de programação no contexto da teoria da computabilidade? Você quer dizer uma enumeração de funções computáveis?
precisa
1
Meu palpite sobre o que você lê: se uma linguagem é suficientemente forte e contém a função universal de outra classe de funções, ela pode definir a função diagonal para essa classe. Se for uma classe de funções totais, a função diagonal não poderá estar na classe.
precisa
Foi declarado informalmente onde eu o encontrei. Algo literalmente ao longo do que eu dei aqui. Também não sei como declarar isso de maneira matemática. Após algumas leituras, não tenho certeza de qual é a "função diagonal de uma classe de funções". Penso nos seus termos o que quero dizer é que "uma classe de funções totais não pode conter sua própria função universal" e, portanto, acho que estou perguntando "que classe de funções totais C é o caso de nenhuma classe de funções totais conter o função universal para C ". Se eu entendo o que é uma "função universal", acho que está correto.
Jake
1
A rigor, essa não é uma questão de nível de pesquisa. Além disso, por que esse é um wiki da comunidade? Ou é?
Andrej Bauer
"Parece que isso dá origem a um tipo de linguagem completa" definitiva "e não-true; aquela que só pode ser interpretada por uma máquina de Turing." não siga essa afirmação parece não sequitur, o que você quer dizer com isso, por que parece?
vzn 27/06

Respostas:

42

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 gNstring abaixo.

Deixe ser uma função de emparelhamentom,n .

Digamos que uma linguagem de programação seja fornecida pelos seguintes dados:L=(P,ev)

  1. um conjunto decidível PN de "programas válidos" e
  2. um calculável e parcial função .ev:P×NN

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 ) = 1Pvalid: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 nvalid(n)=1nPevev(m,n)mn - o resultado pode ser indefinido.

Agora podemos introduzir alguma terminologia:

  1. Um idioma é total se for uma função total para todos os m Pnev(m,n)mP .
  2. Uma linguagem de interpreta língua L 2 = ( P 2 , e v 2 ) se existe u P 1 de tal modo que e v 1 ( u , n , m ) e v 2 ( n , m ) para todos os n PL1=(P1,ev1) L2=(P2,ev2)uP1ev1(u,n,m)ev2(n,m)nPe . Aqui u é o simulador para L 2 implementado em L 1 . Também é conhecido como programa universal para L 2 .mNuL2L1L2

Outras definições de " interpreta L 2 " são possíveis, mas não permita que eu entre nisso agora.L1L2

Dizemos que e L 2 são equivalentes se eles se interpretarem.L1L2

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,φ)nNφ(n,m)nmev ser computável.

Nossa definição de linguagens de programação é muito descontraída. Para o seguinte, vamos exigir mais três condições:

  • L implements the successor function: there is succP such that ev(succ,m)=m+1 for all mN,
  • L implements the diagonal function: there is diagP such that ev(diag,m)=m,m for all mN,
  • L is closed under composition of functions: if L implements f and g then it also implements fg,

A classic result is this:

Theorem: If a language can interpret itself then it is not total.

Proof. Suppose u is the universal program for a total langauge L implemented in L, i.e., for all mP and nN,

ev(u,m,n)ev(m,n).
As successor, diagonal, and ev(u,) are implemented in L, so is their composition kev(u,k,k)+1. There exists n0P such that ev(n0,k)ev(u,k,k)+1, but then
ev(u,n0,n0)ev(n0,n0)ev(u,n0,n0)+1
As there is no number equal its own successor, it follows that L is not total or that L does not interpret itself. QED.

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. Let L be a total language. We get a total L which interprets L by adjoining to L its evaluator ev. More precisely, let P={0,nnP}{1,0} and define ev as

ev(b,n,m)={ev(n,m)if b=0,ev(m0,m1)if b=1 and m=m0,m1
Obviously, L is total because L is total. To see that L can simulate L just take u=1,0, since then ev(u,m,n)ev(m,n), as required. QED.

Exercise: [added 2014-06-27] The language L 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 language L – 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.

Andrej Bauer
fonte
If I checked the wiki checkbox it was unintentional.
Andrej Bauer
2
Is there any extra power in languages where you can't tell whether or not a given program is valid?
Phylliida
3
@DaniPhye: If the language syntax is not semidecidable then you can "hide" computational power in the syntax. For instance, the language rules could require that each function be equipped with a bit which tells whether the function is total. We could then implement 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.
Andrej Bauer
3
How does "If a language can interpret itself then it is not total" gel with this result: A Self-Interpreter for F-omega?
Cactus
18

Any language which is not Turing complete can not write an interpreter for it self.

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.

David Richerby
fonte
Ah! That is a good point. So there has to be certain requirements on what the language computes. It seems that some minimum requirement must be made on the power of the language to make that statement true. It seems like if we demand it be able to solve basic arithmetic problems then it might hold.
Jake
@Jake You might actually be able to get away with something incredibly weak like "the language defines at least one non-constant function" or "the language defines more than one function". My counterexample is clearly trivial for any reasonable definition of "trivial".
David Richerby
Sounds like an interesting problem for me to think about. If I find anything I'll reply back.
Jake