I need to show that $H_1(x)$ defined as follows is partially computable.

\begin{equation} H_1(x)= \begin{cases} 1 \;\;\;\;\;\text{ if } \Phi(x,x) \downarrow \\ \uparrow \;\;\;\;\; \text{ otherwise} \end{cases} \end{equation}

The thing is my textbook, that is "Computability, Complexity, and Languages" by Davis, Sigal and Weyuker, lacks of examples and walkthroughs so, personally, I find hard solving even the easiest exercises.

I think I can prove $H_1(x)$ partially computable, if I can find a program $\mathcal P$ that executes it.

First of all for the Universality Theorem:

$$\Phi(x,x) = \psi^{(1)}_{\mathcal P}(x) \text{ and } \# (\mathcal P)=x$$

so I can write a program that computes $\psi^{(1)}_{\mathcal P}(x)$:

\begin{array} \\ \;\;\;\;\;\;\;\;\;Y \gets 0 \\ \;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\ [E] \;\;\;\text{ GOTO } E \\ [A]\;\;\;\; Y \gets Y+1 \end{array}

I don't know if I am on the right track. I would greately appreciate every comment, suggestion, nudge in the right direction, because I really feel kind of lost.

Attempt #2: First of all I am so very sorry for not providing you enough details. Basically: $$\Phi^{(n)}(x_1, \ldots, x_n, x_{n+1}) = \psi^{(n+1)}_{\mathcal P}(x_1, \ldots, x_n, x_{n+1})$$

in plain English $\psi^{(n)}_{\mathcal P}(x_1, \ldots, x_n)$ is the value of the output at the terminal snapshot; $\Phi^{(n)}(x_1, \ldots, x_n, y)$, where $\#(\mathcal P) = y$ is the universal program $\mathcal U_n$, which works as an interpreter, it keeps track of the current snapshot by decoding the number of program being interpreted, decides what to do next and do it. So $f(x) = \Phi^{(1)}(x,y)=\psi^{(2)}_{\mathcal U_1}(x,y)$. So my answer would be:

\begin{array} \\ \;\;\;\;\;\;\;\;\;\text{IF } \Phi(x,x) \text{ GOTO } C \\ [A] \;\;\;\text{ GOTO } A \\ [C]\;\;\;\; Y \gets 1 \end{array}


\begin{array} \\ \;\;\;\;\;\;\;\;\;\text{IF STP}^{(2)}(x,x,y,k) \text{ GOTO } C \\ [A] \;\;\;\text{ GOTO } A \\ [C]\;\;\;\; Y \gets 1 \end{array}

where $STP^{(n)}(x_1, \ldots, x_n, y, t)$ is a primitive recursive predicate that happens to be true if the program with number $y$ on input $(x_1, \ldots, x_n)$ eventually stops after $t$ steps.

  • 1
    $\begingroup$ What is $\phi(x,x)$? Is it run machine number $x$ on input $x$ or something, i.e., $H_1$ is the halting problem? And what does partially computable mean, recursively enumerable? Do you know the standard enumeration of the rational numbers, $1/1, 1/2, 2/1, 3/1, 2/2, 1/3, \dots$? What if you enumerate them and for rational number $a/b$, run $\phi(a,a,b)$, where the $b$ refers to number of steps. If $\phi(a,a,b) \downarrow$ and accepts, say YES, o.w., move on to next number. Show $\phi(x,y,z)$ is computable (machine $x$, input $y$ for $z$ steps). $\endgroup$ – Pål GD Jan 20 '13 at 19:26
  • $\begingroup$ @PålGD By definition $\Phi^{(n)}(x_1,\ldots, x_n, y)=\psi^{(n)}_{\mathcal P}(x_1, \ldots, x_n)$ where $\#(\mathcal P) = y$ and partially computable function is a function that can be obtained from the initial functions by a finite number of applications of compositions, recursion and minimalizazion or if it is computed by some program. I really don't know if it involves the halting problem, the exercise doesn't specify it. Unfortunately I don't know what a recursively enumerable function is. $\endgroup$ – haunted85 Jan 20 '13 at 19:42
  • 2
    $\begingroup$ What is $\#(\cdot)$? Or specifically $\#(\mathcal{P})$? And what is $\psi$? You need to know that many books use different notations, so you need always to specify all the details of your questions. $\endgroup$ – Pål GD Jan 20 '13 at 19:55
  • 1
    $\begingroup$ Does the universality claim something about the computability of creating $\Phi(x,x)$, given $x$? You seem to be on the right track any way. Given an $x$, $H_1$ is supposed to run $\Phi(x,x)$, and if that halts (regardless of output), then $H_1$ returns 1, otherwise you just keep running $\Phi(x,x)$ (you have no choice, really). $\endgroup$ – Pål GD Jan 20 '13 at 22:22
  • 1
    $\begingroup$ You are not on the right track because your attempted solution never executes $\Phi(x,x)$. $\endgroup$ – Andrej Bauer Jan 21 '13 at 7:30

Many such exercises are best solved by writing down programs in your favorite programming language. However, a typical programming language cannot examine its own source code, or the source code of a subroutine, or of another program, whereas a Turing machine can. So we need to enrich the language with two special constructs:

  • eval(x,y) which runs source code x on input y and returns the result. This is more or less the universal Turing machine. (Yes, the Python toplevel interactive shell is the same thing as a universal Turing machine.)

  • uneval(f) which accepts a function f and returns its source code. This allows us to inspect source code, and to simulate it step-by-step (we can implement a "debugger" by hand once we get acces to source code).

Strictly speaking, eval is not needed because it can be implemented in a general-purpose programming language. It amounts to implementing an interpreter for the language inside the language itself, a favorite programming exercise of people who design programmng languages.

So, to so solve your exercise in Python:

def H1(x):
  "Simulate the machine x on input x. Return 1 if it halts, cycle otherwise."
  eval(x, x)
  return 1

That was easy, and to the point. Fiddling with Turing machines just obscures the fact that this is a very easy exercise (although at some point you do need to convince yourself that Turing machines can do all the things that a programming language can do, and vice versa).

By the way, when you pose questions here, you should not assume that everyone knows your textbook by heart. You should explain notation such as $\Phi(x,x)$. I had to guess what you meant.

  • $\begingroup$ I think part of the problem haunted85 has is dealing with notation. Can you explain how to translate your python program into his (or any) formal notation using enumerations? (Your last paragraph should be a comment on the quesiton, by the way.) $\endgroup$ – Raphael Jan 21 '13 at 11:13
  • 1
    $\begingroup$ No, I cannot explain that, or I should say I won't. That is like explaining what a compiler does, so it is best to just think about compilers. $\endgroup$ – Andrej Bauer Jan 21 '13 at 12:22

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.