### Rice's Theorem comprehension check

Posted:

**Fri May 12, 2017 6:54 pm UTC**Refreshing my memory of the halting problem for the thread in the math forum led me to pages about Rice's Theorem, and it took me a while to wrap my head around that proof so I want to check here if I basically understand what's going on.

First of all, we know from the halting problem proof that there can be no program H(n) which always determines whether program N halts with input n. (I'm going to use capital letters for programs and lower case letters for the strings representing those programs. Also all programs take one input, which I don't always specify.)

So then suppose we have a program P(n) which determines whether (the partial function computed by) program N has some non-trivial property (i.e. a property that at least one program has and at least one program doesn't have). P outputs 1 for inputs with the property and 0 for inputs without the property.

We can assume wlog that P(n)=0 when N doesn't halt on any input. We can make this assumption because P(n) is equivalent to Q(n)=1-P(n) in the sense that they partition the set of programs into the same two subsets, so we can use whichever one outputs 0 for never-halting programs.

Because the property determined by P is non-trivial, let a be a string such that P(a)=1.

For any n, we can construct a program TN(m) which

1) Runs N(n)

2) Computes A(m)

(TN is a different program for each n, which takes m as its only input.)

But then if we define H(n) so it

1) Constructs tn as (the string corresponding to the program) described above

2) Outputs P(tn)

then H(n) is a halting oracle.

---

Is that basically correct?

I was getting confused by the first step of H, I think because I was picturing a Turing machine rather than a program written in a more human readable language. I think I get it now that I imagine H just concatenating the relevant strings of programming language.

First of all, we know from the halting problem proof that there can be no program H(n) which always determines whether program N halts with input n. (I'm going to use capital letters for programs and lower case letters for the strings representing those programs. Also all programs take one input, which I don't always specify.)

So then suppose we have a program P(n) which determines whether (the partial function computed by) program N has some non-trivial property (i.e. a property that at least one program has and at least one program doesn't have). P outputs 1 for inputs with the property and 0 for inputs without the property.

We can assume wlog that P(n)=0 when N doesn't halt on any input. We can make this assumption because P(n) is equivalent to Q(n)=1-P(n) in the sense that they partition the set of programs into the same two subsets, so we can use whichever one outputs 0 for never-halting programs.

Because the property determined by P is non-trivial, let a be a string such that P(a)=1.

For any n, we can construct a program TN(m) which

1) Runs N(n)

2) Computes A(m)

(TN is a different program for each n, which takes m as its only input.)

But then if we define H(n) so it

1) Constructs tn as (the string corresponding to the program) described above

2) Outputs P(tn)

then H(n) is a halting oracle.

---

Is that basically correct?

I was getting confused by the first step of H, I think because I was picturing a Turing machine rather than a program written in a more human readable language. I think I get it now that I imagine H just concatenating the relevant strings of programming language.