Thanks for showing this with a whiteboard and diagrams. My professor did nothing but scribble a few sentences on the board and talk for an hour. You're a prime example of youtube being a better source for education than my actual university.
You dont really write w on the tape. Using C, you construct the Mw so it would write the w on its own tape at the beginning of its execution (it has w "hard-coded" in itself). Then you could feed it to B and get a solution for (M,w).
I believe your construction is probably good supporting material for why the undecidable/looping bit appears for the constructed machine, but your argument for that isn't clear to me. You also haven't clearly described why the constructed machine and the blank tape machine have output/decidability equivalence.
Reductions are a bit tricky. The whole concept is using problems that have already been proven to be undecidable, NP complete, P, etc, and reducing them to other problems to see if they are also undecidable, NP complete, P, etc. The "constructed machine" is not a new machine, per say. It is a machine that takes TM A's inputs, and "decides" A using a "decider", a procedure that runs TM B to solve TM A's original problem. So the final output will always be TM B's output. In this case, the original problem A is: Does M Halt? The decider converts, or "reduces", A to B, and we know that A is undecidable because that has previously been proven (see: the halting problem). If B always accepted or rejected and could not loop forever, we could solve A using B using the decider he constructed. This has been proven to be impossible, so B must be able to loop forever as well. Further: 1) If A reduces to B and B is decidable, then A is decidable. This is because, since B is decidable, we can decide A by reducing it to B. 2) If A reduces to B and A is undecidable, then B is undecidable. This is because if B were decidable, A could be decided using B (1), so by contradiction, B must be undecidable. However: 1) If A reduces to B and B is undecidable, we do NOT know whether or not A is decidable. Decidable and undecidable problems can both be reduced to an undecidable problem. 2) If A reduces to B and A is decidable, we do NOT know whether or not B is decidable. Same reason as #1 Note that these same concepts work for NP completeness.
I guess the prof made a mistake. He said "reducing the blank tape problem to the halting problem". In fact, reducing A to B means that A is solvable once B is solvable, i.e. A is less difficult than B. On the other way around, once you get an algorithm for B, you can transform that algorithm-B into algorithm-A to solve problem A. In this sense, we should reduce halting problem into blank tape problem. Then by assuming an algorithm solving the black tape problem, we shall construct another algorithm to solve halting problem, which contradicts the fact that halting problem is unsolvable.
Thanks for showing this with a whiteboard and diagrams. My professor did nothing but scribble a few sentences on the board and talk for an hour. You're a prime example of youtube being a better source for education than my actual university.
Wonderfully put, kind stranger. Thank you for speaking on behalf of us.
I have been struggling with this halting problem, and now it makes sense a bit. Thanks
♫ 'Cause I've got a blank tape baby....and I'll write your word ♫
Great explanation, great Professor.
Thank you very much. Very clear explanation.
This helped me! Thanks.
Thank you!
8 years later .....this helped me Soo much
CZcams Professors >>> GOAT!
This is very well done, thank you
Thankyou sir
i have never seen described with picture...surely helps a lot, thank you
謝謝!很清楚
Can someone please explain to me why it's necessary to write a w on the tape?
You dont really write w on the tape. Using C, you construct the Mw so it would write the w on its own tape at the beginning of its execution (it has w "hard-coded" in itself). Then you could feed it to B and get a solution for (M,w).
Because when you write w on the tape to create Mw, when you feed it to B, the input is exactly the same as in the halting problem.
@@scutze Ah ok. That makes a lot more sense now.
As a visual person, this is the greatest thing ever
I believe your construction is probably good supporting material for why the undecidable/looping bit appears for the constructed machine, but your argument for that isn't clear to me. You also haven't clearly described why the constructed machine and the blank tape machine have output/decidability equivalence.
Reductions are a bit tricky. The whole concept is using problems that have already been proven to be undecidable, NP complete, P, etc, and reducing them to other problems to see if they are also undecidable, NP complete, P, etc.
The "constructed machine" is not a new machine, per say. It is a machine that takes TM A's inputs, and "decides" A using a "decider", a procedure that runs TM B to solve TM A's original problem. So the final output will always be TM B's output.
In this case, the original problem A is: Does M Halt? The decider converts, or "reduces", A to B, and we know that A is undecidable because that has previously been proven (see: the halting problem). If B always accepted or rejected and could not loop forever, we could solve A using B using the decider he constructed. This has been proven to be impossible, so B must be able to loop forever as well.
Further:
1) If A reduces to B and B is decidable, then A is decidable. This is because, since B is decidable, we can decide A by reducing it to B.
2) If A reduces to B and A is undecidable, then B is undecidable. This is because if B were decidable, A could be decided using B (1), so by contradiction, B must be undecidable.
However:
1) If A reduces to B and B is undecidable, we do NOT know whether or not A is decidable. Decidable and undecidable problems can both be reduced to an undecidable problem.
2) If A reduces to B and A is decidable, we do NOT know whether or not B is decidable. Same reason as #1
Note that these same concepts work for NP completeness.
It is clear ....
3:30, no it is not impossible. Imagine a machine that takes M and W as input, then outputs randomly Yes or No. Same inputs, same outputs.
chat, is this real?
Are these two statements same: 1) Reducing the blank tape problem to halting problem 2) Reducing the halting problem to blank tape problem?
nope
I guess the prof made a mistake. He said "reducing the blank tape problem to the halting problem". In fact, reducing A to B means that A is solvable once B is solvable, i.e. A is less difficult than B. On the other way around, once you get an algorithm for B, you can transform that algorithm-B into algorithm-A to solve problem A. In this sense, we should reduce halting problem into blank tape problem. Then by assuming an algorithm solving the black tape problem, we shall construct another algorithm to solve halting problem, which contradicts the fact that halting problem is unsolvable.