snippetMinor
Are there infinite state machines, and how do their computational power relate to turing machines?
Viewed 0 times
infinitearecomputationalrelatepowerturingstatemachineshowand
Problem
From the internet:
Are there infinite (countable/uncountable) state machines where I change every "finite" to "infinite" in the previous definition? If I do so, how are they different to turing machines in terms of computational power? Why was the turing machine not defined in this way, considering the fact that the TM used an infinite sized tape?
A finite-state machine is formally defined as a 5-tuple (Q, I, Z, ∂, W) such that:
Q = finite set of states
I = finite set of input symbols
Z = finite set of output symbols
∂ = mapping of I x Q into Q called the state transition function, i.e. I x Q → Q
W = mapping W of I x Q onto Z, called the output function
A = set of accept states where F is a subset of QAre there infinite (countable/uncountable) state machines where I change every "finite" to "infinite" in the previous definition? If I do so, how are they different to turing machines in terms of computational power? Why was the turing machine not defined in this way, considering the fact that the TM used an infinite sized tape?
Solution
Turing machines aren't defined this way simply because automata with an infinite number of states aren't effective.
The definition of effective procedures tries to capture our intuitive understanding of algorithms, and Turing machines are meant to formalize effective calculability (and there's reason to believe that they do).
But to be effective, a method must be finite.
An infinite "algorithm" isn't very useful, since you can't really give a full description of it.
The major problem of formal language/automata theory is to find finite descriptions of infinite languages.
These automata also don't really capture the same class of languages as TMs do.
Indeed, if you generalise FAs to infinite states you can recognise any language $L = \{a_1, a_2, ...\}$ by combining the finite automata of the summands $\{a_i\}$ in
$$L = \bigcup_{i \in \mathbb{N}} \{a_i\}.$$
This makes sense, since if we allow infinite "algorithms" then there's an algorithm to compute any function by simply listing all values of the function.
The definition of effective procedures tries to capture our intuitive understanding of algorithms, and Turing machines are meant to formalize effective calculability (and there's reason to believe that they do).
But to be effective, a method must be finite.
An infinite "algorithm" isn't very useful, since you can't really give a full description of it.
The major problem of formal language/automata theory is to find finite descriptions of infinite languages.
These automata also don't really capture the same class of languages as TMs do.
Indeed, if you generalise FAs to infinite states you can recognise any language $L = \{a_1, a_2, ...\}$ by combining the finite automata of the summands $\{a_i\}$ in
$$L = \bigcup_{i \in \mathbb{N}} \{a_i\}.$$
This makes sense, since if we allow infinite "algorithms" then there's an algorithm to compute any function by simply listing all values of the function.
Context
StackExchange Computer Science Q#167267, answer score: 6
Revisions (0)
No revisions yet.