Is there a total language that can express any halting algorithm, or a proof that such a language cannot exist?

Question

Conjecture: there is a language L with the following properties:

1. There is a halting algorithm that checks whether program P is in L.
2. There is a halting evaluation algorithm E(P, I) that runs any pair of program P in L and input I.
3. For any halting algorithm P' (represented as a state and an instruction table for a Turing machine) there is a program P in L such that for any input I, E(P, I) = P'(I). That is, there is a program that always produces the same output.

There is no need for a halting algorithm that would check whether algorithm P' has an equivalent program P in L. That would be undecidable.

Question: is there an example of L? Is there a formal proof that L is impossible? Is there a formal proof that this question is also undecidable?

Answer 1

Below I'll conflate algorithms, Turing machines, and indices for such.

The answer is no since we can diagonalize. By $(1)$ we can enumerate the elements of $L$ as $e_0,e_1,e_2,...$, but then we can diagonalize: let $M$ be the machine which, on input $i$, runs machine $e_i$ on input $i$ and outputs $1$ + the result.

(Note that dropping the requirement that $L$ consist only of halting algorithms - which is equivalent, given $(1)$, to your $(2)$ - makes the answer trivially yes since we can then take $L$ to be the set of all programs.)

---

Incidentally, although it's totally unrelated I can't help mentioning a deeply surprising positive result: there is a computable set of Turing machine such that every Turing machine appears up to equivalence exactly once on the list! Such sets are called Friedberg numberings; see here for a quick proof of their existence by Kummer, substantially simplifying the original proof by Friedberg. This is almost impossible; the saving grace is that we don't require (and indeed, can't have) a computable way to tell where a given Turing machine appears up to equivalence in the set.

In terms of programming languages, this means that we can whip up a language MWAHAHAH with the following seemingly-contradictory properties:

• Every algorithm is indeed implementable in MWAHAHAH.

• Programming as we understand it is impossible, since there is no general procedure for telling what program in MWAHAHAH performs a given algorithm.

As far as I know, nobody's actually produced such a language, but since the existence proof is totally explicit it would be a fun exercise for somebody who really loves terrible things.