[Solved]: Are turing machines and formal languages the same mathematical object?

Problem Detail: 

Turing's objective while building his concept was to formalise how humans do abstract reasoning.

Now correct me if I am wrong but that reasoning seems just an exercise where you manipulate a set of formal statements i.e. strings with no semantics attached to it.

So if Turing machines is the same as reasoning, is there an isomorphism (or something like that) between formal languages and Turing machines?

Asked By : Jerome

Answered By : kebertx

Not quite. A Turing machine is described by this mathematical object:

$$(Q,\Sigma,\delta,\mathcal H, q_0, b)$$

Where

• $Q$ is a finite set of states
• $\Sigma$ is an alphabet, a finite set of symbols
• $\delta : Q \times \Sigma \rightarrow Q \times \Sigma \times\{\Leftarrow, \Rightarrow\}$ is a transition function
• $\mathcal H \subseteq Q$ is the set of halting states
• $q_0 \in Q$ is the initial state
• $b \in \Sigma$ is the "blank" symbol

The machine takes some input string, $x \in \Sigma*$, and uses the transition function to iteratively update individual symbols in that string until $\delta$ returns a state belonging to $\mathcal H$. At that point we say the machine has halted - which it may or may not ever do.

Compared to all that, formal languages are much more simple objects. A language is just a subset of the set of all strings over some alphabet. In other words, $\mathcal L \subseteq \Sigma^*$, where $*$ is the Kleene star operator.

The connection is that Turing machines can be used to define formal languages. For example:

$$ \mathcal L = \{x \in \Sigma^* | \mathcal M \text{ halts when given } \langle x \rangle \text{ as input }\} $$

Defines the formal language $\mathcal L$ in terms of the Turing machine $\mathcal M$. For a language, $\mathcal L$, if there exists a Turing machine that halts if and only if its input belongs to $\mathcal L$, then the language is called Turing-recognizable. Some languages cannot be defined by any Turing machine, which means they are not-computable - no finite process can decide whether an arbitrary string belongs to the language or not.

Formal languages are not the same as Turing machines, but the Turing recognizability does have an interesting place in the study of formal languages. In the Chomsky hierarchy, a Type-0 language is a language that can be enumerated by any formal grammar, and this turns out to be equivalent to being recognizable by a Turing machine! Formal grammars and Turing machines are just two of many models of computation that are all equally powerful!

It's generally believed that every model of computation makes the same distinction between computable and non-computable languages - this notion is called the Church-Turing thesis.

EDIT: My terminology was off when I initially wrote this. A Turing decidable language can be decided by a machine that always halts, and gives a definitive yes or no as to whether its input belongs to the language. When we only require that the machine accepts member's, but can't necessarily reject non-members, the associated language is called Turing recognizable, or, more commonly, recursively enumerable. Turing recognizable languages are equivalent to the languages that can be generated by unrestricted grammars.

Some languages are not even recursively enumerable - for example, the set of all Turing machines that don't halt is totally unrecognizable. There's a language corresponding to this set that couldn't be generated by any grammar at all, but that still might be called a "formal language." By this definition, there's no complete mapping from Turing machines to formal languages, and definitely no isomorphism between the two.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62668

3.2K people like this

 Download Related Notes/Documents