Turing machines and decidability

[-EquinoX-]

Okay, so if I have a turing machine so called M, is there a configuration alpha s beta which yields a configuration with state q? If it's decidable can someone explain the algorithm to proceed?

 

[CRGreathouse]

That seems to be clearly harder than the halting problem, which is undecidable.

 

[-EquinoX-]

can you provide me with more detailed explanation why this is undecideable? I mean more saying than it's harder than the halting problem, as I can see that as well

i've also scanned the question directly from the book in case it helps

 

[-EquinoX-]

and here's my answer so far:

Given the initial state s we can decide whether there exists a configuration αsβ and reading all the instructions of the k-cells of the TM machine that there is a path from that configuration to γqη where q is a given state of M and αβγη εΓ because there must exist a path according to the given instructions to reach from state s to q with the given configuration.

So I'd say it's decideable.. please correct me if I am wrong

 

[Coin]

So let's say you produce an algorithm that decides this problem.

I can then feed into your algorithm any turing machine M I like, and along with it feed in state q where I choose q to be the halting state for M. If your algorithm works, then your algorithm will tell me whether or not q is reached, and therefore it will have told me whether M halts. But that would mean you have solved the halting problem, therefore there does not exist any such algorithm.

This is what CRGreathouse means by your problem being "harder than the halting problem", it reduces to the halting problem. If you had an algorithm for deciding this problem then you could use the same algorithm to decide the halting problem. This (reducing the problem given to the halting problem) is generally the standard method for proving undecidability...

 

[-EquinoX-]

ok now it's clear! thanks guys