Submitted by BernardJOrtcutt t3_zvnq0i in philosophy
Merciful_tofu t1_j1ynjw7 wrote
About the Halting Problem and Determinism
Disclaimer: For people that never heard of a deterministic Turing machine (DTM)[https://en.m.wikipedia.org/wiki/Turing_machine] or the Halting Problem (https://en.m.wikipedia.org/wiki/Halting_problem) the following might not make much sense.
-
DTMs are a theoretical mathematical formalism that describe a system that is intrinsically deterministic. I say this because at any given point of the calculation, considering the configuration, tape content and DTM state we can exactly say what the next configuration/ tape and state will look like.
-
The Halting Problem is an example how some Problems that can be defined for this deterministic theoretical formalism are undecidable.
-
The very nature of the Halting Problem being undecidable implies that something in the formalism is indeterministic. (?) My thought is that if the formalism was completely deterministic, we would be able to decide the Halting Problem for all possible problem instances.
Dear big brains of Reddit: What do you all think about this? Is this an example of how a deterministic system can be indeterministic, or does undecidability imply something different? I am looking forward to your thoughts!
Viewing a single comment thread. View all comments