# Sequence of total languages whose limit is turing complete

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?

• Please make your question self-contained, and include definitions of the concepts you're using. – Yuval Filmus Sep 15 '15 at 17:32
• 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. – Jake Sep 15 '15 at 17:35
• 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})$. – Gilles 'SO- stop being evil' Sep 15 '15 at 18:53
• 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? – Jake Sep 15 '15 at 19:29

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.