7
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @ kebertx So we can say there is an isomorphism between decidable languages and Turing machines? $\endgroup$ – Jerome Aug 18 '16 at 6:59
  • $\begingroup$ There's definitely a surjection from Turing machines to decidable languages, but the inverse isn't true. Every decidable language actually corresponds to an infinite number of Turing machines, which means there can't be an isomorphism there. - Proof: Say you have a program that decides whether an arbitrary string belongs to a language. Then you can write another program that first does any random calculation, then discards the result and makes the same decision as the first program. This tells us that every problem has either zero or infinitely many solutions! $\endgroup$ – kebertx Aug 18 '16 at 7:27
9
$\begingroup$

No, they are not the same thing. A language is a set of words over some finite alphabet. A Turing machine is a 7-tuple as defined in the Wikipedia.

For some languages it is convenient to to characterize them by a TM that recognizes them. For every language that can be recognized by a TM there is an infinite number of TMs that recognize the same language, so you'd have to impose some additional criteria if you want to make that unique.

This might sound like a good start for an isomorphism, but unfortunately there are infinitely many languages that can't be recognized by TMs. This can be seen by a simple counting argument. The set of all possible words over a fixed alphabet is isomorphic to the natural numbers. Hence the set of all languages over that alphabet (=the set of all subsets of the words) is uncountable. On the other hand, there are only countably many Turing machines. So not only can't "recognition" be made into an isomorphism, there can't be an isomorphism of any kind since that would imply that the set of TMs has the same cardinality as the set of languages.

$\endgroup$
  • $\begingroup$ Can't we say that a formal language is necessarily recognised by at least one TM? $\endgroup$ – Jerome Aug 17 '16 at 15:26
  • 2
    $\begingroup$ @Jerome No. There are infinitely many languages that are not even semi-decidable, so are not decided or accepted by any Turing machine. $\endgroup$ – David Richerby Aug 17 '16 at 15:31
  • $\begingroup$ @ adrianN. Right and the other way round? I.e. once you have a TM, can it generate anything else than a formal language? $\endgroup$ – Jerome Aug 17 '16 at 15:44
  • $\begingroup$ @Jerome For every Turing Machine, there is a (possibly empty) language that it accepts, defined as the set of words that the TM halts on in the YES state. There's a language for each TM, but not a TM for each language. $\endgroup$ – jmite Aug 17 '16 at 15:52
  • $\begingroup$ Okay so am I right to say that, for example, that no TM accepts the formal language defined by ZFC? (as there are some statement true in ZFC where no TM halts on) $\endgroup$ – Jerome Aug 17 '16 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.