1
$\begingroup$

This is Universality theorem In the Computability, Complexity and Languages book written by Davis in page 70:

If $\phi^{(n)}(x_1,...,x_n,y) = \psi_P(x_1,...,x_n)$        $where$  #$(P) = y$

Theorem 3.1 (Universality Theorem): for each $n>0$ the function $\phi^{(n)}(x_1,...,x_n,y)$ is partially computable.

From what I understand of this theorem, the universal program is more like an interpreter it takes $x_1,...,x_n$ as input and $y$ as a program number and simulates what program with number $y$ does on the $x_i$s.

Since there is no program for halting problem so there is no $y$ for it to be passed to $\phi^{(n)}(x_1,...,x_n,y)$ so I think this theorem is not applicable to halting problem.Is it right?

$\endgroup$

closed as unclear what you're asking by Ran G., David Richerby, Luke Mathieson, Nicholas Mancuso, Raphael Feb 4 '15 at 12:02

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ please try to explain what you are trying to ask. Specifically, what do you mean by saying "this theorem is not applicable to halting problem"? $\endgroup$ – Ran G. Jan 29 '15 at 22:33
  • $\begingroup$ @RanG. I mean can we use Universality Theorem for Halting problem ? $\endgroup$ – M a m a D Jan 31 '15 at 4:15
  • 1
    $\begingroup$ but how? can you specify $\phi$, $\psi$ etc, in the way you wish to "use it for halting problem"? $\endgroup$ – Ran G. Jan 31 '15 at 10:37
1
$\begingroup$

By this book notation we have

$Halt(x,y)$ $\iff$ Program number $y$ eventually halts on input $x$.

Since there $Halt(x,y)$ is not computable predicate (theorem 2.1 page 68) there is no program that check if program number $y$ halts in input $x$ (for every $y$ and $x$), but this not mean that there is no program that run program number $y$ on input $x$!

By using universal program $\phi(x,y)$ we can run program number $y$ on input $x$. This means that $Halt(x,y)$ is r.e.

+if you think a bit more you can observe that program number y can get stuck in loop on input x, and that's why $Halt(x,y)$ is not computable.

$\endgroup$

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