Talk:Proof of impossibility

From Wikipedia, the free encyclopedia

"Here's another clue that points to impossibility: we can describe a "machine" to do the computation as a "state machine". When the end-number is "1" then the machine halts (this is easy to construct). But can we build another machine to determine if our state machine always halts (at 1) for any arbitrary number we stick into it? No, by Turing's thesis."

I don't think this is quite right - if the Collatz conjecture has a solution, then a Turing machine CAN be built to predict the behavior of a state machine, just by using the proof of the conjecture.

The same argument can be incorrectly used to show that solvable problems are unsolvable: Consider a modified version of the Collatz conjecture, where the iterative formula is just n -> (n-1) if n > 0, and 0 -> 0. This is iterative formula is trivially proven to halt for all n>0.

To show the flaw in the argument above, we could build a state machine that halts when the number is zero, AND we could build a turing machine that trivially predicts the behavior of the state machine (using the simple fact that we know it halts if n>0).