What is the relationship between two definitions of Turing-computability of a partial function?

Question

When one wants to know that whether a partial function $f \colon \Sigma^{*} \supsetneq \mathrm{dom}(f) \rightarrow \Sigma^{*}$ is Turing-computable, there are two methods that I think they are both useful.

1. We can define a total function $\bar{f}$ such that $$ \bar{f}(x) = \left\{ \begin{aligned} &f(x),&x \in \mathrm{dom}(f) \\ &\bot,&x \not\in \mathrm{dom}(f) \\ \end{aligned} \right.$$ Thus, $f$ is Turing-computable if $\bar{f}$ is Turing-computable by a TM using $\bar{\Sigma} = \Sigma \cup \{ \bot \}$. (Some answers use this definition. see [1] and [2])

2. Let $M$ be a TM, and We say $f$ is Turing-computable by $M$ if $$M(x) = \left\{ \begin{aligned} &f(x),&& x \in \mathrm{dom}(f) \\ &\bot,&&x \not\in \mathrm{dom}(f) \\ \end{aligned} \right.$$ where $M(x) = \bot$ means that $M$ never halts on $x$. (This definition is introduced in my books.)

These two definitions are not equivalent, since $M$ can computes some functions whose domain is Turing-recognizable instead of Turing-decidable in sense of definition 2.

I want know that is the definition 2 more powerful? In another word, if $f$ is Turing-computable in sense of definition 1, can we prove that it is also Turing-computable in sense of definition 2?

Answer 1

Definition 1 is incorrect. It does not define the notion of partial computable function correctly. Definition 2 is correct.

Proposition: A partial function $f$ is computable according to your definition 1 if, and only if, it is a partial computable function whose domain $\mathrm{dom}(f)$ is a computably decidable set.

Proof. Suppose $f$ is computable according to definition 1. Then for every $n \in \mathbb{N}$, we have $n \in \mathrm{dom}(f)$ if, and only if, $\bar{f}(n) \neq \bot$. So we can decide whether $n \in \mathrm{dom}(f)$.

Conversely, suppose $f$ is a partial computable function whose domain $\mathrm{dom}(f)$ is decidable. Then $\bar{f}$ is computable because we can compute it like this: given input $n$, if $n \in \mathrm{dom}(f)$ then output $\bot$, otherwise output $f(n)$. $\Box$

Answer 2

I am not sure why you think that Definition 2 could be more powerful. If one of the two is more powerful, then it's Definition 1 and in this case, I actually think that Definition 1 is more powerful.

If you have a Turing Machine M which computes a total function, it also means that M halts on all inputs. In your Definition 1, M would then never use the bottom symbol (sorry, I can't figure out how to type it!) except when processing one of the undefined inputs. Then you could simply modify such a Turing Machine to always check before terminating whether the output would be the bottom symbol or not, and in the latter case, to just run forever. Then the new Turing Machine would be exactly as needed in Definition 2.

The other direction on the other hand, is impossible. Just take any semi-decidable problem which is not decidable, for example the epsilon halting problem (the problem to decide whether a given Turing Machine holds on the empty word). There you have a Turing Machine which exactly computes the partial function which maps each halting Turing Machine to 1 and any other Turing Machine to that bottom symbol. But there is no total computable function which maps each halting Turing Machine to 1 and any other to the bottom symbol or any other symbol distinct from 1.