Sometimes in mathematics, you can right 20 slightly different definitions and find you have defined 20 slightly different things. Other times you can write many different formalizations and find they are all equivalent. Turing completeness is the latter. It turns up in Turing machines, register machines, tiling the plane, Conways game of life and many other places. There are weaker and stronger possibilities, like finite state machines, stack machines and oracle machines. (Ie a Turing machine with a magic black box that solves the halting problem is stronger than a normal Turing machine)
Human brains are finite state machines. A Turing machine has unlimited memory and time.
Physical laws are generally continuous, but there exists a Turing machine that takes in a number N and computes the laws to accuracy 1/N. This isn’t philosophically forced, but it seems to be the way things are. All serious theories are computable.
We could conceivably be in a universe that wasn’t simulateable by a Turing machine. Assuming our brains are simulatable, we could never know this absolutely, as simulators with a huge but finite amount of compute trying to trick us could never be ruled out. 0 and 1 aren’t probabilities and you are never certain. Still, we could conceivably be in a situation were an uncomputable explanation is far simpler than any computable theory.
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.
Sometimes in mathematics, you can right 20 slightly different definitions and find you have defined 20 slightly different things. Other times you can write many different formalizations and find they are all equivalent. Turing completeness is the latter. It turns up in Turing machines, register machines, tiling the plane, Conways game of life and many other places. There are weaker and stronger possibilities, like finite state machines, stack machines and oracle machines. (Ie a Turing machine with a magic black box that solves the halting problem is stronger than a normal Turing machine)
Human brains are finite state machines. A Turing machine has unlimited memory and time.
Physical laws are generally continuous, but there exists a Turing machine that takes in a number N and computes the laws to accuracy 1/N. This isn’t philosophically forced, but it seems to be the way things are. All serious theories are computable.
We could conceivably be in a universe that wasn’t simulateable by a Turing machine. Assuming our brains are simulatable, we could never know this absolutely, as simulators with a huge but finite amount of compute trying to trick us could never be ruled out. 0 and 1 aren’t probabilities and you are never certain. Still, we could conceivably be in a situation were an uncomputable explanation is far simpler than any computable theory.
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.