4
$\begingroup$

First let me clarify what I mean by a number of things. A language is a decidable set of natural numbers which encode functions from natural numbers to natural numbers $ \mathbb{N} \to \mathbb{N}$. A language is said to be total if it only encodes total functions from naturals to naturals. A language is turing complete if it can encode all functions from natural numbers to natural numbers that a universal turing machine can. Because I can make a turing machine than infinitely loops on some inputs I can encode a non-total function with a turing machine. So being turing complete implies being non-total.

An interpreter of a language $L$ is a function $I_L : \mathbb{N} \to \mathbb{N}$ such that $n \in \mathbb{N} \mapsto I_L(pair(p, n))$ is the same function that $p$ encodes forall $p \in L$. A nice theorem says that if a language is total, it cannot encode such a function.

A while back I was wondering "is there a language that could only be interpreted by a turing complete language". Now the answer seems obvious to me (thanks to some help from stack exchange); no, no such things exists. You can always just add an interpreter for the language to get a total language that can't be interpreted by the previous one.

Clearly this gives raise to a sequence of total languages. Namely the first language you pick, then that language plus its interpreter, then that language plus its interpreter, etc...

But I have no reason to believe that this sequence is even particularly useful. I have some vague intuitive sense of a the limit of this sequence but I can't seem to pin down what a limit of a sequence of languages is. I do not think the limit of this sequence is turing complete. I do think the limit of this sequence is a partial language however. Namely, it seems the limit language should be able to interpret itself (perhaps this is not a good intuition?).

Does such a notion of a limit exist? If it does is there a sequence of total languages whose limit is turing complete? If such a limit exists is it computable? If it is computable, why does no one use such a language?

Bonus: Since we are talking limits anyhow. Is there a topology of languages to be considered here?

Improve this question
$\endgroup$
4
  • $\begingroup$ Please make your question self-contained, and include definitions of the concepts you're using. $\endgroup$
    – Yuval Filmus
    Sep 15, 2015 at 17:32
  • $\begingroup$ What do you mean by self contained? I'll add definitions in the mean time. edit: ah, do you mean just not referencing the other thread? I'll remove that whole section in such a case. $\endgroup$
    – Jake
    Sep 15, 2015 at 17:35
  • $\begingroup$ There's no universal encoding of functions $\mathbb{N} \to \mathbb{N}$ into integers, so you should make the encoding explicit — what you call “language” isn't a set, it's a specific encoding $\mathbb{N} \to \mathbb{N} \to \mathbb{N}$ where you happen to be interested in the image set $\phi(\mathbb{N})$. $\endgroup$
    – Gilles 'SO- stop being evil'
    Sep 15, 2015 at 18:53
  • $\begingroup$ Does it mater what encoding is used? I suppose a better phrasing would be "a language $L$ is a decidable set equipped with an encoding function $L \to (\mathbb{N} \to \mathbb{N})$ Does that seem more clear? $\endgroup$
    – Jake
    Sep 15, 2015 at 19:29

1 Answer 1

Reset to default
3
$\begingroup$

I'm not sure I full get your encoding and based on the comments there seem to be some problems with it, but I'll nevertheless provide my answer (or "answer", if you prefer).

A sequence of languages (your terminology) that satisfies your constraints is a sequence where the $i$th element in the sequence runs the Universal Turing machine for $i$ steps or until the machine halts, whichever comes first.

Clearly, each element in this sequence is total, but the limit is a Universal Turing Machine.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Super disappointing. But yea that makes sense. Thanks! $\endgroup$
    – Jake
    Sep 16, 2015 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.