3
$\begingroup$

It is well known that the set of all functions computable by a TC system is exactly the same as the set of functions computable by any other TC system, given suitable translation. I'm wondering whether the same is true for the complement of those, the set of all non-computable functions (i.e. non-halting algorithms); are those necessarily the same for any TC system as well?

I realize this is potentially ill-posed, since I'm essentially asking about equivalence of functions which are outside of the domain of the system and thus yield no proper values. Intuitively, though, it seems like it may be possible to compare them anyway, or at least the vast majority of them.

For example, if I have a Turing machine that writes 1s to the tape forever, that seems arguably isomorphic to the implementation of a looping successor function or counter in any other given language. With proper translation algorithms, one could imagine being able to formally equate the behavior of such algorithms within two different systems. That said, I would also not be shocked if it turns out it is provably impossible to make any such equivalence between two systems in general.

If I had to guess, it seems to me that any non-halting behavior that can be progressively evaluated in one system should also be expressible in any other. If anyone knows whether or not this is true, or can explain why this question is unresolvable in some way, I'll consider my question answered.

$\endgroup$
3
  • 1
    $\begingroup$ If $A = B$, then $A^\mathsf{c} = B^\mathsf{c}$. So if two systems agree on what's computable, then they must agree on what isn't computable. $\endgroup$
    – Hayden
    Commented May 31, 2022 at 6:04
  • $\begingroup$ Also, your use of "computable" and "noncomputable" doesn't seem standard to me. A function which doesn't halt on any input is still computable, it just isn't total computable. The set of noncomputable (partial/total) functions is the set of all (partial/total) functions which don't have some algorithmic description. E.g., the halting problem (with respect to some fixed model of computation) is noncomputable in the latter sense. $\endgroup$
    – Hayden
    Commented May 31, 2022 at 6:15
  • $\begingroup$ I apologize for my terminology, I figured it'd be off in some way. Hopefully it was clear I effectively meant halting and non-halting algorithms. Also, if your answer above is The Answer (it certainly sounds right), please go ahead and post it as an answer. $\endgroup$
    – Trevor
    Commented May 31, 2022 at 6:17

1 Answer 1

2
$\begingroup$

Given some model of computation $T$ let $\operatorname{Rec}(T)$ denote the set $$\operatorname{Rec}(T) = \{f \colon {\subseteq} \mathbb{N} \to \mathbb{N} \mid \text{$f$ computable wrt $T$} \}.$$ Breaking this down a little more, $f$ is computable with respect to some model of computation $T$ if there is some algorithm (in the sense of $T$) such that for each $n \in \mathbb{N}$ the algorithm converges on input $n$ if and only if $f(n)$ is defined, in which case their respective outputs agree.

If $T_1$ and $T_2$ are Turing complete systems, then by definition we have $\operatorname{Rec}(T_1) = \operatorname{Rec}(T_2)$, i.e., $T_1$ and $T_2$ agree on what it means for a partial function $f \colon {\subseteq} \mathbb{N} \to \mathbb{N}$ to be partial computable. If $A_1$ and $A_2$ denote algorithms in the senses of $T_1$ and $T_2$, respectively, which represent $f$, then by definition $$\text{$A_1$ converges on input $n$} \iff \text{$f(n)$ is defined} \iff \text{$A_2$ converges on input $n$}.$$ As such, if $f$ is total (i.e., $f(n)$ is defined for every $n \in \mathbb{N}$) then every algorithm $T_1$ represents $f$ by and every algorithm $T_2$ represents $f$ by will both necessarily halt on every input.


Things are more complicated if you phrase things in terms of the algorithms themselves instead of in terms of the partial computable functions that those algorithms represent. For precision, let's say that a Turing complete system is a partial computable function $\Phi \colon {\subseteq} \mathbb{N}^2 \to \mathbb{N}$ such that:

  • For every partial computable function $f \colon {\subseteq} \mathbb{N} \to \mathbb{N}$ there exists some $e \in \mathbb{N}$ for which $\Phi(e, -) = f$ (in which case $e$ is often called an index or Gödel number for $f$).
  • For every partial computable function $\theta \colon {\subseteq} \mathbb{N}^2 \to \mathbb{N}$ there exists a total computable function $g \colon \mathbb{N} \to \mathbb{N}$ such that $\Phi(g(e), -) = \theta(e, -)$ for every $e \in \mathbb{N}$.

These conditions are related to a general theory of effective enumerations of the partial computable functions (see Gödel Numberings of Partial Recursive Functions, Rogers 1958). Let $\Phi_1$ and $\Phi_2$ be the partial computable functions corresponding to $T_1$ and $T_2$ in this manner. Then your question can be phrased in the following way:

How do the sets $\{e \in \mathbb{N} \mid \text{$\Phi_1(e, -)$ total}\}$ and $\{e \in \mathbb{N} \mid \text{$\Phi_2(e, -)$ total}\}$ relate to one-another?

The sets $\mathrm{Tot}_k = \{e \in \mathbb{N} \mid \text{$\Phi_k(e, -)$ total}\}$ ($k = 1, 2$) are complicated in certain technical senses -- they are $\Pi^0_2$ subsets of $\mathbb{N}$ since $$e \in \mathrm{Tot}_k \iff \forall n \exists s (\text{$\Phi_k(e, n)$ converges/halts in $\leq s$ steps}).$$ More than just that, they are many-one-complete among all the $\Pi^0_2$ subsets of $\mathbb{N}$, meaning that for any other $\Pi^0_2$ subset $S \subseteq \mathbb{N}$, there exists a total computable function $F \colon \mathbb{N} \to \mathbb{N}$ such that $S = F^{-1}[\mathrm{Tot}_k]$. To put that into more perspective, an implication of this is that $\mathrm{Tot}_k$ are each Turing equivalent to $0''$, the Halting problem relative to the Halting problem.

Despite being pretty darn unsolvable (though still pretty low in the degrees of unsolvability in comparison to other unsolvable problems), that they are both many-one-complete among the $\Pi^0_2$ subsets of $\mathbb{N}$ means they are many-one-equivalent to each other, meaning there are total computable functions $F, G \colon \mathbb{N} \to \mathbb{N}$ such that $\mathrm{Tot}_2 = F^{-1}[\mathrm{Tot}_1]$ and $\mathrm{Tot}_1 = G^{-1}[\mathrm{Tot}_2]$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .