Can every problem in Theory of Computation be stated as undecidable, by writing a reduction from Halting Problem?

Question

Let us consider the problem that Whether a given Turing Machine M, has at least 481 states.

Since the number of states of M can be read off from the encoding of M. We can build a Turing machine that, given the encoding of M written on its input tape, counts the number of states of M and accepts or rejects depending on whether the number is at least 481.

(Source : Discussion in Automata and Computability by Dexter Kozen)

But, let us forget this for some time, and try to write reduction from a Halting problem.

HP # x -> Halting problem instance

We are constructing a machine 'R'

Input to R: A machine description M

What 'R' does:: First runs HP on x, if halts, then check whether M has 481 states, if yes accept, else reject.

L(R) = {
                 Set of all descriptions M, which has at least 481 states  ::::  If HP halts on x
                 Phi  ::: If HP doesn't halt on x
       }

Doesn't this hold as a reduction from Halting Problem to the problem mentioned above?

Or I am doing some wrong in the process of the reduction?

Thanks in advance!!

Answer 1

Just because a problem can be reduced from the halting problem does not make the original problem undecideable. A problem is decideable if there exists an algorithm that solves the problem. That means that a problem is undecideable if there does not exist any algorithm that solves it. In other words, a problem is undecideable if, for every algorithm, it is true that the algorithm does not solve the problem.

The existence of some algorithm that does not solve the problem in no way shows that the problem is undecideable.

Answer 2

Your reduction goes in the wrong way. You should reduce to the halting problem and not from. So, the correct reduction would be something like this:

1. I want to solve MY PROBLEM.
2. I think I cannot do it, so I will prove the following: If I can solve MY PROBLEM, I can solve HP.
3. I assume I can create a Turing machine for MY PROBLEM.
4. I somehow modify an arbitrary input to HP, so that it can be input to Turing machine for MY PROBLEM.
5. I get an answer from the Turing machine and decode it back, so that I have an answer for the original input to HP.
6. The answer should not exist, thus, my assumption 3 is wrong.

Answer 3

The problem is that I understood the definition of reduction in the wrong way.

The reduction is to be made from a language (set) or essentially a problem of that. (A set can be represented as a problem that, given an entity, whether that entity belongs to that set or not) to another language.

So first of all, writing the language that we need.

L481 = { M | M has at least 481 states }

Corresponding problem::

Given a Turing machine M, whether M has at least 481 states i.e. whether M belongs to L481 or not.

So in this case I need to do

Halting Problem <=m L481

So we need to map between the instances of first language to second language, in such a way that if the mapped instance is decidable to be a member of L481 or not, we can decide whether the instance of Halting problem say M#x, M halts on x or not.

So,

M#x |-> N

The reduction algorithm that we need to pose:

if M halts on x <=> N has at least 481 states
if M doesn't halt on x <=> N doesn't have at least 481 states

This absolutely can not be true, as a machine N has fixed number of states in its finite control, irrespective of any other things, other than the description of that.

So, this reduction is false.

What I have done, earlier in my question, was I have written reduction in the wrong way, that I have to write a machine, that takes some instances and decide on them whether that belongs to the L481 or not. (essentially I was trying to write a decider, for a problem which is undecidable).