4 ms·
The problem, I believe, is that most people (even many in CS/CE/EE) don't fully understand the complexity of Turing machines running programs in recursively enu
by pdkl95 9y ago
The problem, I believe, is that most people (even many in CS/CE/EE) don't fully understand the complexity of Turing machines running programs in recursively enumerable languages. Moving a problem into software doesn't merely add complexity; it moves the problem into another class of complexity where behavior cannot be understood without running the program[1]. The behavior of sufficiently large programs (>8k states[2]) is so complex it cannot be described by math[3].
Anybody claiming to understand the consequences of adding any new feature to a processor (or software) is implicitly claiming they have solved the equivalent to halting problem. The only solution is to move as many problem as possible back to a simpler domain that is actually decidable[4].
[1] halting problem, Gödel’s Incompleteness Theorem
[2] https://www.scottaaronson.com/blog/?p=2725 https://www.scottaaronson.com/blog/?p=2725
[3] "math" := ZF set theory
[4] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...
- msmith10101 9y agoNot really. That's the 'only solution' if use limit yourself to the straight jacket of existing CS theoretical methods. Given how irrelevant it has been to industry up to this point (unable to even prove something as simple to state as whether P = NP), that seems pointless.
- mannykannot 9y agoThere are many specific Turing machines for which the behavior can be understood without running the program, such as the one that starts by unconditionally halting.
- pdkl95 9y agoAre you careful to only run e.g only run javascript it's one of those special cases? How often do you use the one-state program that unconditionally halts?
- mannykannot 9y agoOne never actually runs a Turing machine, they exist only for the purpose of argument.