News for hackers. Stuff that matters.
Re:‘It Can’t Be True’ – Inside the Semiconductor Industry’s ... by pdkl95 on Tuesday January 09, 2018 @09:27AM (#16106347)
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

[3] "math" := ZF set theory

[4] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...

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.