0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I understand the proposition and that is why I think that these definitions are not equivalent. But I am not sure how do you judge which one is correct by this proposition. Of course, definition 2 is the "formal one". But I find that there are some answers using the definition 1 (maybe I misunderstand the answers). Ignoring which one is the formal definition, let's just define two sets of partial functions, I want know which one is bigger, and if the latter is bigger, that the definition 2 is the correct one makes sense. $\endgroup$ – TeamBright Oct 25 '17 at 5:59
  • $\begingroup$ You misunderstand, or the textbooks you are reading are not written well (or both!) I proved that the second one is bigger, isn't this clear? The second one is "all partial computable maps" and the first one is "all partial computable maps with decidable domain" $\endgroup$ – Andrej Bauer Oct 25 '17 at 13:08
  • $\begingroup$ The reason that the second definition is the correct one has nothing to do with what you wrote so far. The fact that that is the correct definition was established in 1930's by some smart people who gave good reasons for the definition. $\endgroup$ – Andrej Bauer Oct 25 '17 at 13:10
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I mean a definition "more powerful" means that this definition makes more partial functions be computable by a TM. It seems that your view is the same as mine. By the way, you can click the "edit" of my question to find and check how to type some symbols. $\endgroup$ – TeamBright Oct 25 '17 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.