Turing-Machine

Mathematical model of computation which is build on Finite Automaton. It's more capable than the Push-Down Automaton.

Structure

Q: States
\Sigma: Input Alphabet
\Gamma: Symbols used on the storage medium (storage tape), which includes \Sigma
\delta: State transitions
q_0: Starting state
q_{reject}: Set of invalid states
q_{accept}: Set of accepting states

The problem with the word

The questions if any given word is part of a Formal Languages is called the word problem.

\begin{aligned} \text{Let $K$ be a class of languages:} \\ L_K \coloneqq \{ \langle L, w \rangle \; | \; L \in K \land w \in L \} \end{aligned}

To determine if a word belongs to regular language, i.e., to solve the following problem:

L_{RA} \coloneqq \{ \langle R, w \rangle \; | \; \text{$R$ is a regular expression and $w \in L(R)$} \}

we have to:

Check the syntax, i.e., check if the input is a valid regular expression
Construct DFA and then DFA from the regular expression
Simulate DFA for input and halt accepting if DFA accepts the input

A similar algorithm can be applied for context free languages.

The problem with making decisions

The word problem is decidable

Not all languages are recognizable by a Turing machine, i.e., they're not decidable.

The problem with halting

Looking at the amount of problems we are having, I wonder if that Turing guy may have gone off in the wrong direction to begin with. Maybe we should rethink this.