= 27d567bc2d48d9f40e9ccc20ea370b15)
dfranke comments on We are not living in a simulation - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (211)
Brains, like PCs, aren't actually Turing-equivalent: they only have finite storage. To actually be equivalent to a Turing machine, they'd need something equivalent to a Turing machine's infinite tape. There's nothing analogous to Rice's theorem or the halting theorem which holds for finite state machines. All those problems are decidable. Of course, decidable doesn't mean tractable.
It is true that you can run finite state machines until they either terminate or start looping or run past the Busy Beaver for that length of tape; but while you may avoid Rice's theorem by pointing out that 'actually brains are just FSMs', you replace it with another question, 'are they FSMs decidable within the length of tape available to us?'
Given how fast the Busy Beaver grows, the answer is almost surely no - there is no runnable algorithm. Leading to the dilemma that either there are insufficient resources (per above), or it's impossible in principle (if there are unbounded resources there likely are unbounded brains and Rice's theorem applies again).
(I know you understand this because you pointed out 'Of course, decidable doesn't mean tractable.' but it's not obvious to a lot of people and is worth noting.)
This is just a pedantic technical correction since we agree on all the practical implications, but nothing involving FSMs grows nearly as fast as Busy Beaver. The relevant complexity class for the hardest problems concerning FSMs, such as determining whether two regular expressions represent the same language, is the class of EXPSPACE-complete problems. This is as opposed to R for decidable problems, and RE and co-RE for semidecidable problems like the halting problem. Those classes are way, WAY bigger than EXPSPACE.