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.
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.