HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Are there infinite state machines, and how do their computational power relate to turing machines?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
infinitearecomputationalrelatepowerturingstatemachineshowand

Problem

From the internet:

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 Q


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?

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.

Context

StackExchange Computer Science Q#167267, answer score: 6

Revisions (0)

No revisions yet.