3

I am looking for an alternative yet rigorous proof to a theorem about recursively enumerable sets.

Let $A \subseteq \mathbb{N}_0$ for the purposes of this question. Here is the version of recursive enumerability I am using:

Definition. A set $A$ is recursively enumerable if either $A = \varnothing$ or there exists a total $\mu$-recursive function $\varphi$ such that $\operatorname{Im}(\varphi) = A$.

A theorem posits the equivalence of the above definition with another criterion.

Theorem. $A$ is recursively enumerable $\Longleftrightarrow$ $A$ is the domain of a $\mu$-recursive function $\Omega$.

Assume henceforth that $A \neq \varnothing$.

The $\Longrightarrow$-direction is quite clear and easy to prove formally: taking $\Omega (x) \equiv \mu z[\varphi(z) - x = 0]$ suffices. The converse $\Longleftarrow$-direction is more difficult for me. I have seen two types of arguments so far.

  • One of them relies heavily on Church's thesis. This is not rigorous, so is undesirable.
  • Both of them make heavy direct or indirect use of the equivalence of the sets of $\mu$-recursive and Turing computable functions. This is not covered in the course I'm taking.

I have thought about putting in the work to rigorously prove the equivalence of these two formulations but it is probably pages of relatively tedious work. Therefore, I thought it would be a good idea to ask before going down that road:

Q: Is there and do you know of a rigorous proof without Turing machines of the statement

$$\text{$A$ is the domain of a $\mu$-recursive function $\Omega \Longrightarrow A$ is recursively enumerable}$$

by, e.g., a direct construction of a total $\mu$-recusive $\varphi$ such that $\operatorname{Im}(\varphi) = A$?

Linear Christmas
  • 1,285
  • I would do something like $\varphi(x):=\Omega(x)\cdot 0+x$. – Berci Jan 08 '21 at 18:15
  • @Berci Such a $\varphi$ might not be total as $\Omega$ might be partial. Or am I missing something? – Linear Christmas Jan 08 '21 at 19:14
  • Ah yes, indeed, you need total function. – Berci Jan 08 '21 at 19:32
  • Assume $A$ is infinite (otherwise $A$ is recursive, and hence r.e.). Intuitively, you want to define $\varphi$ as follows: $\varphi$ simulates $\Omega$ in parallel on $0,1,2,\dots$ . Eventually some of these computations will converge (this happens exactly when you run $\Omega$ with some $i\in A$). You then define $\varphi(n)$ as the input of the $n$-th convergent run. All of this can be formalized without TMs by means of the UTM-theorem, but it's hard to provide a formal answer without knowing what you covered in the course and what you would consider sufficiently formal. – Manlio Jan 09 '21 at 09:40
  • @Manlio Yes, I have seen that proof construction. However, as it contains the concept of "converges on $n$th step", it already seems to apply a Turing machine to calculate the $\varphi$ values, does it not? (Or even increasingly many Turing machines as I assume one parallel computation is added each step). You mentioned the formalisation of this with the UTM theorem, but as that proves the existance of a "universal Turing machine", it will have to use Turing machines. (1/2) – Linear Christmas Jan 09 '21 at 10:54
  • @Manlio By "rigorous" I mean using classical mathematical tools to prove the existance of $\varphi$ with the requires properties. So direct constructions of $\phi$ will work, proof by contradiction is an option, and so on. (The same standards as a rigorous course on standard analysis, for instance). This does exclude appeals to intuition alone, and the CT thesis. In the OP, I try to ask for a rigorous proof without the use of Turing machines. An analogy from analysis would be "Is there a clever/slick/alternative/shoeter way of proving xyz?", I suppose. Hopefully this clarifies things. (2/2) – Linear Christmas Jan 09 '21 at 11:03
  • Despite its name, the UTM-theorem states the existence of a universal partial recursive function (with some specific properties). Besides, if you want to develop the theory without using TMs, you may want to check e.g. https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf. In particular, take a look at the definition of Kleene's T predicate, ($T_n$ in the paper), which (intuitively) describes the computation of a partial recursive function. You can use it to define a notion of "halts in $s$ steps" without referring to TMs. – Manlio Jan 09 '21 at 12:04
  • That being said, let me add that TMs are not outside of math. They are perfectly valid formal objects and can be used within proofs without making them flawed (and therefore a statement like "the $e$-th Turing machine halts in $s$ steps" can be made precise and used). It is perfectly reasonable to ask for a proof that doesn't rely on TMs, but it is rather weird that TMs are not covered in your computability course, especially given that they are ubiquitous in the literature, and that their intuitive meaning is so strong that using TMs can really improve the readability of a proof. – Manlio Jan 09 '21 at 12:07
  • @Manlio I'll have a look at the link, thanks for the comments! To clarify, of course Turing machines can be used in rigorous proofs and are a part of maths. Turing machines are also covered in the course. But if a proof in the recursion formulation relies on Turing machines, then one usually needs information on the equivalence of the two formulations. The proof of this equivalence is what is not covered in the course. So I am essentially looking for a proof of the theorem in OP that takes less effort then proving the equivalence beforehand. – Linear Christmas Jan 09 '21 at 12:54

0 Answers0