Re:‘It Can’t Be True’ – Inside the Semiconductor Industry’s ...
by msmith10101 on Tuesday January 09, 2018 @11:06AM
(#16107118)
Not 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.
Re:‘It Can’t Be True’ – Inside the Semiconductor Industry’s ...
by mannykannot on Tuesday January 09, 2018 @12:07PM
(#16107661)
There 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.
Re:‘It Can’t Be True’ – Inside the Semiconductor Industry’s ...
by pdkl95 on Tuesday January 09, 2018 @06:20PM
(#16111109)
Are 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?
Re:‘It Can’t Be True’ – Inside the Semiconductor Industry’s ...
by mannykannot on Tuesday January 09, 2018 @10:44PM
(#16112402)
One never actually runs a Turing machine, they exist only for the purpose of argument.
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
[3] "math" := ZF set theory
[4] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...