Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
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). – Pål GD Jan 20 at 19:26
@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. – haunted85 Jan 20 at 19:42
1  
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. – Pål GD Jan 20 at 19:55
@PålGD absolutely, thank you for your remark. So $\#(\mathcal P)$ is the number of the program $\mathcal P$, $\psi^{(n)}_{\mathcal P}(x_1, \ldots, x_n)$ is the value of the output variable $Y$ at the final snapshot of the program $\mathcal P$. – haunted85 Jan 20 at 20:13
1  
You are not on the right track because your attempted solution never executes $\Phi(x,x)$. – Andrej Bauer Jan 21 at 7:30
show 2 more comments

1 Answer

up vote 2 down vote

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.

share|improve this answer
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.) – Raphael♦ Jan 21 at 11:13
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. – Andrej Bauer Jan 21 at 12:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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