\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Answer
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
Math and science::Theory of Computation

Turing-recognizable and Turing-decidable

The following four propositions are true:

Every [Turing-...able] language is [Turing-...able].

There exist [Turing-...able] languages that are not [Turing-...able].

Every language [can/can't?] be recognized by multiple turing machines.

There [does/doesn't] exist languages which are not Turing-decidable. There [does/doesn't] exist languages that are not Turing-recognizable.

[Every/not every] Turing machine has a language that it recognizes.

See the back for some explanations. The rest of this card builds up terminology used in the above propositions.

The concepts of recognizable and decidable rely on the concept of a configuration. The initial state of a Turing machine is typically described by a 7-tuple, but while operating, the head will move, and the tape will change, and a configuration is used to specify the current state of the tape and head.

Configurations

The tuple [what is sufficient to keep track of the state?] is called a configuration. Configurations are often written like so: 1011q701111. This configuration represents a Turing machine with the the following state:

  • the tape contents is [...]
  • the state machine's state is [...]
  • the head is at [what position?].

Accept, reject or loop

The essence of the Turing machine is captured in the transition function, \( \delta \), as it shows how and with what limits the machine can change from state to state.

There are three outcomes possible after starting a Turing machine on an input:

  1. the machine may end and accept the input string by entering state \( q_{accept} \),
  2. the machine may end and reject the input string by entering state \( q_{reject} \),
  3. or the machine may never end.

Comparison to finite automata

A noteworthy difference between Turing machines and finite automata is that finite automata stop once they have consumed the whole input. Turing machines can continue indefinitely after passing over all or only part of the input.

Languages reconized by a Turing machine

Let \(M = (Q, \Sigma, \Gamma, \delta, q_{accept}, q_{reject}) \) be a Turing machine. The collection of strings that [...] is called the the language recognized by \( M \), or simply the language of \( M \), denoted \( L(M) \).

An alternative description of the above concept highlights the nature of the correspondence:

TM M recognizes language L iff:

  1. The strings in L put M into the accept state.
  2. The strings NOT IN L either:
    1. [...], or
    2. [...].

The second type of language associated with a Turing machine:

Languages decided by a Turing machine

Let \(M = (Q, \Sigma, \Gamma, \delta, q_{accept}, q_{reject}) \) be a Turing machine that [meets some condition]. The collection of strings that [...] is called the the language decided by \( M \).

Categorizing languages

Any language can be categorized as to whether there exists a Turing machine that recognizes it or not; similarly, all languages can be categorized as to whether there exists a Turing machine that decides it.

A language is called Turing-recognizable iff [...].

Alternative terminology for Turing-recognizable language: recursively enumerable language.

A language is called Turing-decidable (or just decidable) iff [...].

Alternative terminology for Turing-decidable language: recursive language.