3 ms·
I'm pretty sure any physically realizable computer is a Finite State Machine (FSM). The Turing Machine assumptions of infinite memory and unbounded time lead t
by trashtester 3y ago
I'm pretty sure any physically realizable computer is a Finite State Machine (FSM).
The Turing Machine assumptions of infinite memory and unbounded time lead to a lot of poor intuitions about them, in my experience.
That bad intuitions would also apply to FSM's, though. Or to the human brain for that matter.
For instance, a well trained human brain may be Turing Complete, if they can access some external storage (like pen&paper). This leads to confused concepts such as the Chinese Room argument.
Even though a human brain can contain a Turing Machine, it doesn't mean that understanding a Turing Machine gives much relevant understanding of how the Brain normally operates. The native compute model of the brain is completely different.
- nyrikki 3y agoLLMs are pessimisticly constrained to being equivalent to TC0 or more specifically are uniform consent depth threshold circuits. Circuits and TMs are very different, but while LLMs can use threshold circuits, they do not have access to finite size input parity circuits, nor can they do operations like xor in a single layer. It is the cost of high parallelism. For those who are trying to figure out real world applications, it is worth the effort to learn circuit complexity, as it will be far more realistic than TM. https://complexityzoo.net/Complexity_Zoo:T#tc0 https://complexityzoo.net/Complexity_Zoo:T#tc0