Human brains are finite state machines. A Turing machine has unlimited memory and time.
Oops! You’re right, and It’s something that I used to know. So IIRC as long your tape (and your time) is not infinite you still have a finite state machine, so Turing machines are kind of finite state machines taken to the limit for (n→∞) is that right?
Turing machines are a finite state machine that have access to a memory tape. This was intended to be sort of analogous to humans being able to take notes on unbounded amounts of paper when thinking.
Turing machines are kind of the limit of finite state machines. There are particular Turing machines that can simulate all possible finite state machines. In general, an arbitrary sequence of finite state machines can be uncomputable. But there are particular primitive recursive functions that simulate arbitrary finite state machines, (given the value as an input. ) You don’t need the full strength of turing completeness to do that. So I would say, kind of no. There are systems strictly stronger than all finite automaton, yet not Turing complete.
Really, the notion of a limit isn’t rigorously defined here, so its hard to say.
I fleshed out what I meant a bit more what I was imagining:
I have a particular Turing machine (for example one that recognizes the language L:={anbn|n∈N} ) as long as you then limit the amount of transitions/time and the length of the string, then you could construct a finite state machine that reconizes the same language (for example L:={anbn|0≤n≤k∧k,n∈N} ).
Naively, I’d imagine it to be possible for any particular Turing machine to construct an inductive rule how to construct the n+1-transition-finite state machine and the k+1-memory state machine from the n-time and k-memory state machine? Because in that case I’d imagine specifying a kind of “infinite state machine” by some (1-memory,1-time)-state machine and two induction rules how to extend the state machine as long as no termination state is reached.
The language above can be recognized by a pushdown automaton or generated by a corresponding context-free grammar. I think past me had already heard about this idea, forgot about it and then was trying really hard to rederive something similar to it.
Thanks for the answer!
Oops! You’re right, and It’s something that I used to know. So IIRC as long your tape (and your time) is not infinite you still have a finite state machine, so Turing machines are kind of finite state machines taken to the limit for (n→∞) is that right?
Turing machines are a finite state machine that have access to a memory tape. This was intended to be sort of analogous to humans being able to take notes on unbounded amounts of paper when thinking.
Turing machines are kind of the limit of finite state machines. There are particular Turing machines that can simulate all possible finite state machines. In general, an arbitrary sequence of finite state machines can be uncomputable. But there are particular primitive recursive functions that simulate arbitrary finite state machines, (given the value as an input. ) You don’t need the full strength of turing completeness to do that. So I would say, kind of no. There are systems strictly stronger than all finite automaton, yet not Turing complete.
Really, the notion of a limit isn’t rigorously defined here, so its hard to say.
I fleshed out what I meant a bit more what I was imagining:
I have a particular Turing machine (for example one that recognizes the language L:={anbn|n∈N} ) as long as you then limit the amount of transitions/time and the length of the string, then you could construct a finite state machine that reconizes the same language (for example L:={anbn|0≤n≤k∧k,n∈N} ).
Naively, I’d imagine it to be possible for any particular Turing machine to construct an inductive rule how to construct the n+1-transition-finite state machine and the k+1-memory state machine from the n-time and k-memory state machine? Because in that case I’d imagine specifying a kind of “infinite state machine” by some (1-memory,1-time)-state machine and two induction rules how to extend the state machine as long as no termination state is reached.
The language above can be recognized by a pushdown automaton or generated by a corresponding context-free grammar. I think past me had already heard about this idea, forgot about it and then was trying really hard to rederive something similar to it.