Relationship between function decidability and set decidability

46 Views Asked by At

Let $\Sigma$ denote an arbitrary language. If $\omega = \mathbb{N} + \{ 0\}$, a $\Sigma$-mixed function is a function s.t. $\mathcal{D}_f \subseteq \omega^n \times \Sigma^{*m}$, with $n, m, \geq 0$, and $Im_f = \omega \lor Im_f = \Sigma$ holds. We say a $\Sigma$-mixed function is $\Sigma$-effectively computable if there is some algorithmic procedure (AP) $\mathbb{P}$ s.t.

  • Given an input in $\omega^n \times \Sigma^{*m} \in \mathcal{D}_f$, $\mathbb{P}$ outputs the value of $f(\overrightarrow{x}, \overrightarrow{\alpha})$.

  • Given an input in $\omega^n \times \Sigma^{*m} \not\in \mathcal{D}_f$, $\mathbb{P}$ does not halt.

The notion of AP here given is non-rigorous but can be accepted for our purposes.

We say a set $S \subseteq \omega^n \times \Sigma^{*m}$ is effectively computable (or decidable) if its characteristic function is effectively computable.

From the definitions above, it should follow that if $f$ is $\Sigma$-effectively computable, then $\mathcal{D}_f$ is $\Sigma$-computable. Otherwise, the distinction between the two points in the definition of a $\Sigma$-effectively computable function would make no sense. In other words, it seems to be a theorem that

The domain of any $\Sigma$-effectively computable function is a decidable set.

This property is not stated in any section of my textbook. It seems, although perhaps rather simple, to be important. I wonder if there's some defect in my logic, since I would not expect my textbook to omit such a property.

1

There are 1 best solutions below

1
On BEST ANSWER

From the comments, it seems that you thought the AP would need to decide in advance whether its input was in the domain of $f$. That isn't the intention: the AP just follows its instructions on any given input. E.g., the input could be a representation of a Turing machine and the AP could simulate execution of the Turing machine starting with a blank tape. The AP doesn't need to know in advance whether it's going to terminate on any given argument.