I am reading Kleene's "Mathematical Logic" $2002$ pp 242-246.

Let $T(i,a,x)$ stand for: $i$ is the index of a Turing machine (under particular enumeration) which when applied to $a$ as an argument will at moment $x$ (but not earlier) have completed the computation of a value (call that value $\phi_i(a)$).

Then Kleene tells the theorem: (A) The predicate $T(i, a,x)$ is decidable. (B) $\phi_i(a)$ as a partial function of $i$ and $a$ is computable.

I am not sure I understand the definition of a partial function. In the book, Kleene says that "As a function of $i$ and $a$ both, $\phi_i (a)$ as we remarked is defined exactly when there exists $x$ such that $T(i,a,x)$ is true. So it is a partially defined number-theoretic function of two variables $i$ and $a$, or briefly a partial function."

My problem with this definition is that how do we know that there exists $x$ such that $T(i,a,x)$ is true? Intuitively, I feel that this condition is not decidable, i.e. there does not exist an algorithm to check this. Because if it is false then I would check each $x$ but never reach the end. Why do we allow this kind of undecidable property to be in our definition? I feel concerned about this because Turing machines are used in metamathematics, i.e. our reasoning about formal systems, and we want this reasoning to be finitary (whatever that means).

Long story short - if there is a partial function defined by undecidable property, how do I know whether for each specific value as an argument the function is defined or not. And can this create any problems?

  • $\begingroup$ Yes, $\exists x T(i,a,x)$ is undecidable. This is the halting problem. If all partial recursive functions had decidable domains, then there would hardly need to be a concept of a partial recursive function at all: you could just extend it with a default value to make it a total recursive function. $\endgroup$ – spaceisdarkgreen Jan 8 at 5:56
  • $\begingroup$ @spaceisdarkgreen thanks for comment, how does one make sense about part B of the theorem then? For example, what are the outputs for Turing machine of part B? I am not sure how it detects that function is not defined and what it outputs then. $\endgroup$ – Daniels Krimans Jan 8 at 6:00
  • $\begingroup$ It is a partial recursive function. The very idea of "partial" in partial recursive function is that on some inputs the algorithm does not terminate. $\endgroup$ – spaceisdarkgreen Jan 8 at 6:12
  • 2
    $\begingroup$ The key point in the definition of computable functions is the use of the $\mu$-operator or unbounded search operator. The "unbounded" feaure is exactly what introduces the partial definiteness aspect. $\endgroup$ – Mauro ALLEGRANZA Jan 8 at 12:18
  • 2
    $\begingroup$ Close. The part about the Turing machine 'not knowing' is superfluous: it is not a thing that knows things, it is a thing that performs computations on inputs. You also need a provision that the machine does not halt when the function is undefined. Maybe it will be helpful to start with the Turing machine. Each Turing machine $T$ defines a partial function $f$ as follows: (1) If $T$ halts with value $v$ on input $x,$ then $f(x)=v.$ (2) If $T$ does not halt on input $x$ then $f(x)$ is undefined. A partial function is computable iff there is a Turing machine that defines it in this manner. $\endgroup$ – spaceisdarkgreen Jan 9 at 1:06

Your Answer

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

Browse other questions tagged or ask your own question.