Halting problem some properties

91 Views Asked by At

I am referring a little bit to my previous question on https://math.stackexchange.com/questions/392843/existence-universal-goto-programm-turing-machine#=

Let $f(n)$ be the output of the universal program $U$ on input $(n,n)$. It is easy to see that $h(n)=f(n)+1$ if $f(n)$ is defined or $h(n)=17$ otherwise is not recursiv.

First question: How can be followed that the set $H:=\{n: U(n,n) halts \}$ is not recursiv, where $U(n,n)$ is the program where the input of the program is the program itself.

Second question: Now let $H':=\{n: U(n,0) halts\}$, i.e the set of source codes $n$ which halts for input $0$. This set is also not recursiv.

My atempt (I hope I unterstood it correctly): If $H'$ is recursiv then we can decide $H'$. Now I fix $n$ and I want to see if $n\in H$, this means that the source-code $n$ will be transorme into a new source code $g(n)$, this program overwirtes the input-variable with $n$ and afterwards the old program $n$ will be executed. How can it be followed now (using Church-Turing, not formally) that $g$ is total and recursiv?

Third question: We say that $A$ is many one reducible to $B$ is $A\le_m B$ if there is a total recursiv function $g$, such that $A=g^{-1}(B)$. Now I consider $H^*:=\{(n,m): U(n,m) halts\}$ then it can be followed $H=_mH'=_mH^*$, but how?