2 ms·
> Note that a finite state machine is actually the most powerful known physically realizable form of computation. Your laptop is actually a FSM I’m under the i
by User23 5y ago
> Note that a finite state machine is actually the most powerful known physically realizable form of computation. Your laptop is actually a FSM
I’m under the impression that our computing machines are LBAs, not FSMs. Linear bounded automata are practically as powerful as Turing machines. Sipser gives a nice introductory treatment of the subject.
> It only becomes important if something in the universe actually computes one of those functions that cannot be computed by TMs
Or the universe isn’t a computer and doesn’t compute anything. In that case computation is just a human concept that reduces to moving pebbles (calculi) between various jars.
- mcguire 5y agoNote: not a computational theory guy. I'm a little uncomfortable with LBAs there because, while there is a limit to the storage based on the input size, there is no limit on the input size. It's a fine distinction, but that's the fun of theory.
- Stupulous 5y agoI assume you know more about this than me, so can you help me understand this or direct me somewhere? The universe is constantly taking its current state (or infinity of relativistic frames and/or multiverses) and outputting its next state/states. Is that not definitionally a specialized computer? Are my assumptions wrong?