L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}*, where t is the string after s in a lexicographic ordering of {a,b}*}.
IN SD OUT
Semideciding TM H Memory: infinite
unconstrained
D
Deciding TM anbncn Diagonalize
Memory: |w|, or
infinite unconstrained
Context-Free Pumping
Closure
CF grammar anbn Memory: infinite
PDA stack
Closure
Regular
Regular Expression a*b* Pumping
FSM Closure
Finite Memory: none
Onion Diagram/Chomsky Hierarchy
Semideciding a Language
Let SM be the input alphabet to a TM M. Let L Í SM*.
M semidecides L iff, for any string w Î SM*:
● w Î L ® M accepts w
● w Ï L ® M does not accept w. M may either:
reject or
fail to halt.
A language L is semidecidable iff there is a Turing machine that semidecides it. SD is the set of all semidecidable languages, and is the outermost ring on the onion diagram. The SD languages are also called the recursively enumerable languages, more about enumerability later.
M decides L iff, for any string w Î SM*:
● w Î L ® M accepts w
● w Ï L ® M rejects w.
A language L is decidable iff there is a Turing machine that decides it. D is the set of all decidable languages, and is the next ring in from SD on the onion diagram. The D languages are also called the recursive languages.
Given L ∈ D, is L ∈ SD?
• Sample language hierarchy questions that could easily appear on an exam:
T/F If L contains a finite number of elements then it must be semidecidable.
Because all finite languages are RLS, and if L ∈ RLs then L ∈ SD
However, our focus is on the D and SD languages involving string encodings of TMs, and whose characteristic function defines the behavior of the encoded machine.
T/F L ∈ SD → L ∈ D
Because D ⊂ SD. We will prove that there is a language L such that L ∈ SD and L ∉ D.
Are We Done?
FSM Þ PDA Þ Turing machine
● There is a countably infinite number of Turing machines
since we can lexicographically enumerate all the strings
that correspond to syntactically legal Turing machines.
● There is an uncountably infinite number of languages over
any nonempty alphabet. Using diagonalization, we proved that if |S| = ℵ₀, then |ℙ(S)| = ℶ₁. If ∑ ≠ Ø, then |∑*| = ℵ₀. (For example, if ∑= {a}, ∑* = { ℇ, a, aa, …}.) Let S = { L : L is a language over ∑*}. Then L ∈ ℙ(∑*), and |S| = ℶ₁.
● So there are more languages than there are Turing
machines, as there are more real numbers (||ℝ| = ℶ₁) then there are natural numbers (|ℕ| = ℵ₀).
Lower bound = ℵ₀, since every CFL could be recognized by a distinct TM.
Upper bound: = ℵ₀, since the cardinality of a set that can be lexicographically enumerated is at most a countable infinity.
Apologia pro Turing Machina
Turing machines are powerful enough to describe all computable things — for example, smartphone apps and expert systems — stuff far beyond the capacity of FSMs and PDAs.
☺
Turing machines are a lot harder to program than real computers, and, they have no practical applications! And we have much better formalism for expressing all computable things — for example, Python, Swift, Java.
☹
Why bother?
☺
The very simplicity that makes it hard to program Turing machines makes it possible to reason formally about what they can do — just like FSMs and PDA.
But is there a more powerful computational model, or algorithm, than a TM? Suppose there was such a model, a TM+, that could decide or semidecide languages that were beyond the capacity of a TM. If a TM+ has a finite description then it could be encoded as a string, so, TM+'s could be ordered lexicographically, |TM+| = ℵ0, and there must be an infinite number of languages over a ∑ ≠ Ø that even a TM+ could not recognize.
Turing and Church assumed that any algorithm required a finite description, and the Church-Turing thesis posits that formalisms such as TMs and Church's λ-calculus are powerful enough to express any algorithm. It's really just a conjecture, although widely accepted in Computer Science. If correct, it means a TM+ is not possible.
What Can Algorithms (e.g., TMs) Do?
Make all true statements theorems?
Decide whether a statement is a theorem? In 520, we usually pose the questions as is w ∈ L?
Gödel’s Incompleteness Theorem
Kurt Gödel showed, in the proof of his Incompleteness Theorem [Gödel 1931], that the answer to question 1 is no — there will always be true statements that can not be proven from a set of axioms (incompleteness), or the axioms cannot be proven to never entail both P and ¬P (inconsistency). In particular, he showed that there exists no decidable axiomatization of Peano arithmetic that is both consistent and complete.
1. 0 is a natural number.
2. For every natural number x, x = x. That is, equality is reflexive.
3. For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric.
4. For all natural numbers x, y and z, if x = y and y = z, then x = z. That is, equality is transitive.
5. For all a and b, if b is a natural number and a = b, then a is also a natural number. That is, the natural numbers are closed under equality.
6. For every natural number n, Succesor(n) is a natural number.
7. For all natural numbers m and n, m = n if and only if Successor(m) = Successor(n). That is, Successor is an injection.
8. For every natural number n, Successor(n) = 0 is false. That is, there is no natural number whose successor is 0.
Axioms for Peano Arithmetic
so simple, yet incomplete or inconsistent
The Entscheidungsproblem
The Decidability Problem
Equivalent formulations to deciding if w ∈ L, when L is a set
of strings
Does there exist an algorithm to decide, given an arbitrary sentence w in first order logic, whether w is valid? (Recall that first order logic includes quantifiers, ∃, ∄, and ∀.)
Given a set of axioms A and a sentence w, does there exist an algorithm to decide whether w is entailed by A?
Given a set of axioms, A, and a sentence, w, does there exist an algorithm to decide whether w can be proved from A?
Church's Thesis (Church-Turing Thesis)
All formalisms powerful enough to describe everything we think of as a computational algorithm are equivalent.
All such formalisms allow unrestricted access to unlimited memory. In chapter 24, Rich describes the Chomsky Hierarchy (see slide 1), which classifies languages based on the memory they require to process strings in the language.
This isn’t a formal statement, so we can’t prove it. But many different computational models have been proposed and they all turn out to be equivalent.
Universal TMs (UTMs)
"Universal" does not mean they can semidecide any language. It means they can emulate any TM on any input: given input <M,w> — that is, a TM M encoded as a string M, and an arbitrary string w — a UTM does what M would do on input w. It's like the concept of a stored program computer, which as programmers you know well. The UTC could be a considered a platform, and M is a program run on that platform.
A Turing machine M is a sixtuple (K, S, G, d, s, H):
● K is a finite set of states;
● S is the input alphabet, which does not contain ⧠
● G is the tape alphabet, which contains ⧠. S ⊂ G
● s Î K is the initial state;
● H Í K is the set of halting states;
● d is the transition function
( (K - H) ´ G) to (K ´ G ´ {®, ¬} )
non-halting ´ tape state ´ tape ´ action
state char char (R or L)
Because δ is function, this is a deterministic TM — but nondeterministic TMs accept the same set of languages as deterministic TMs (like FSMs, and unlike PDA). Also, multi-tape TMs accept the same set of language as single-tape TMs.
Useful TM Facts
1. The input tape is infinite in both directions.
2. d must be defined for all possible (state, input) pairs unless the state is
a halting state. But unlike DFSM diagrams, which show transitions from every state for every symbol in ∑, transitions on a symbol in Γ that could not occur from a particular state may be omitted.
3. TM's can completely ignore their input, and do not necessarily halt (unlike FSM's and PDAs). For example, a TM could simply replace a ⧠ with an a, and move one square to the left or right, ad infinitum. Remember, to halt a TM must enter a halting state, but there is no requirement that they do so.
4. The contents of the tape when a TM halts could be considered as the output of a function.
5. By convention, a TM starts with it's R/W head on the ⧠ the left of the input. But we could use other conventions if convenient.
6. At every step, a TM writes a symbol from Γ on the tape, and moves one square to the left or right.
7. At any stage in a computation, a tape can contain only a finite number on non-⧠ symbols.
8. ⧠ ∉ ∑, but is always ∈ Γ, and can be read and written just like any other symbol in the tape alphabet.
The definition of a TM configuration is at the bottom of p. 369:
q × the active tape, where q ∈ K, the states of the TM, and the formula for the active tape to the left of the r/w head is {ℇ} ∪ ((Γ - {⧠})Γ*), and {ℇ} ∪ (Γ*(Γ - {⧠})) for the active tape on the right:
{ℇ} ∪ (Γ* (Γ - {⧠}))
^ ^ ^
| | |
No active tape | a ¬⧠ square
on the right |
|
zero or more symbols
from Γ, the tape
alphabet
In words, active tape to the right of the R/W is either ℇ, or zero or more symbols from Γ (which could include ⧠), followed by a symbol from Γ that is not ⧠). Thus the active tape could include ⧠'s interspersed with symbols from ∑. That is the active tape is the smallest possible tape that includes all the non-blank squares.
Example Configurations
A configuration is a 4-tuple:
state
active tape to left of R/W head
symbol under R/W head
active tape to right of R/W head
By convention, the initial configuration is (s, ⧠w).
Compare to FSMs, where a configuration is (state,input-to-process, or a a PDA, (state, input-to-process,stack-contents)
Yields
Defined over TM configurations in the same manner as yields is defined over configurations of CFLs and regular languages.
For any TM M, let |-M* be the reflexive, transitive closure of |-M.
Configuration C1 yields configuration C2 if: C1 |-M* C2.
A path through M is a sequence of configurations C0, C1, …, Cn for some n ³ 0 such that C0 is the initial configuration and:
C0 |-M C1 |-M C2 |-M … |-M Cn.
A computation by M is a path that halts.
If a computation is of length n or has n steps, we can write:
C0 |-Mn Cn
Turing Machines as Language Recognizers
Input tape:
…⧠⧠⧠w⧠⧠⧠…, and w contains no ⧠'s
The initial configuration of M will then be:
(s, ⧠w) The symbol underneath the read/write head is underlined. Initially, the read/write head is positioned to the left of the input w.
Let M = (K, S, G, d, s, {y, n}). Note the two halt states, y and n.
● M accepts a string w iff (s, ⧠w) |-M* (y, w¢) for some string w¢. That is, if M ends in a halting accept state when processing w, no matter what w' is left on the tape.
● M rejects a string w iff (s, ⧠w) |-M* (n, w¢) for some string w¢. That is, if M ends in a halting reject state when processing w, no matter what w' is left on the tape.
Example TM input/output
M takes as input a string in the language:
{aibj, 0 £ j £ i},
and adds b’s as required to make the number of b’s equal the number of a’s.
The input to M will look like this (the up arrow indicates the current position of the read/write head) :
The output should be:
If the input tape contains …⧠aab⧠…, what is left on the tape when the computation completes?
Specifying a TM using the graphical language
TM Programming Notes
The machine has a strong procedural feel, with one phase coming after another.
There are common idioms, like scan left or right until you find a particular symbol, often ⧠.
There are two common ways to scan back and forth matching symbols a and b. After matching the first a with the first b, the other a's can be matched in either left-to-right or right-to-left order.
Often there is a final phase to fix up the output, after earlier phases where symbols in Γ - ∑ are used to mark off symbols in ∑.
Even a very simple machine is a nuisance to write.
If the input tape contains …⧠aab⧠…, what is left on the tape when the computation completes?
Specifying a TM using the graphical language
This TM computes a function on binary numbers. What is that function?
×
Turing Machines as Language Recognizers
Input tape:
…⧠⧠⧠w⧠⧠⧠…, and w contains no ⧠'s
The initial configuration of M will then be:
(s, ⧠w) The symbol underneath the read/write head is underlined. Initially, the read/write head is positioned to the left of the input w.
Let M = (K, S, G, d, s, {y, n}). Note the two halt states, y and n.
● M accepts a string w iff (s, ⧠w) |-M* (y, w¢) for some string w¢. That is, if M ends in a halting accept state when processing w, no matter what w' is left on the tape.
● M rejects a string w iff (s, ⧠w) |-M* (n, w¢) for some string w¢. That is, if M ends in a halting reject state when processing w, no matter what w' is left on the tape.
A Macro Notation for Turing Machines
(1) Define some basic machines
● Symbol writing machines
For each x Î G, define Mx, written just x, to be a machine that writes x.
● Head moving machines
R: for each x Î G, d(s, x) = (h, x, ®)
L: for each x Î G, d(s, x) = (h, x, ¬)
● Machines that simply halt:
h, which simply halts.
n, which halts and rejects.
y, which halts and accepts.
Next we need to describe how to:
● Check the tape and branch based on what character
we see, and
● Combine the basic machines to form larger ones.
To do this, we need two forms:
● M1 M2
● M1 <condition> M2
Checking Inputs and Combining Machines
A Notation for Turing Machines, Cont'd
Example:
>M1 a M2
b
M3
● Start in the start state of M1.
● Compute until M1 reaches a halt state.
● Examine the tape and take the appropriate transition.
● Start in the start state of the next machine, etc.
● Halt if any component reaches a halt state and has no place
to go.
● If any component fails to halt, then the entire machine may fail
to halt.
a
M1 M2 becomes M1 a, b M2
b
M1 all elems of G M2 becomes M1 M2
or
M1M2
Variables
M1 all elements of G M2 becomes M1 x ¬ Øa M2
except a and x takes on the value of
the current square
M1 a, b M2 becomes M1 x ¬ a, b M2
and x takes on the value of
the current square
M1 x = y M2
if x = y then take the transition
e.g., > x ¬ Ø⧠ Rx if the current square is not blank, go right and copy it.
Shorthands
Some Useful Machines
Find the first blank square to
the right of the current square.
Find the first blank square to
the left of the current square.
Find the first nonblank square to
the right of the current square.
Find the first nonblank square to
the left of the current square
R⧠
LØ⧠
RØ⧠
L⧠
More Useful Machines
La Find the first occurrence of a to
the left of the current square.
Ra,b Find the first occurrence of a or b
to the right of the current square.
a
La,b M1 Find the first occurrence of a or b
to the left of the current square,
b then go to M1 if the detected
character is a; go to M2 if the
M2 detected character is b.
Lx¬a,b Find the first occurrence of a or b
to the left of the current square
and set x to the value found.
Lx¬a,bRx Find the first occurrence of a or b
to the left of the current square,
set x to the value found, move one
square to the right, and write x (a or b).
---------------------------------------------
| |
v a a |
>Ra,⧠ --------------> $L⧠Ra,⧠ -------------->$L⧠
| |
| |⧠
| |
| v
|⧠ y
|
v ∑ = {a,b}
L⧠ Γ = {a,b,⧠,$}
| H = {y,n}
| L(M) = {w : w = ?}
|
|
v b
R -------------------> n
|
|⧠,$
|
v
y
Input: ⧠w w Î {1}*
Output: ⧠w3
Example initial configuration: …⧠⧠⧠11⧠⧠⧠…
Halting configuration: …⧠⧠⧠111111…
6
A Shifting Machine S¬
Input: uw
Output: uw
Example: baabba
Another example of a TM that decides a language
Input tape: …⧠⧠⧠aabbcc⧠⧠⧠…
Halts in y or n?
Input: ⧠⧠⧠112233⧠⧠⧠…
⧠⧠⧠123c⧠⧠⧠… abcc is not in L(M), so L(M) is not a*b*c*
a*b*cn where n % 2 ≠ 0 abc, aabbcc is in the language
Halts in y or n? n
L(M) = ?
Input tape: …⧠⧠⧠abbcabb⧠⧠⧠…
Halts in y or n?
Input tape: …⧠⧠⧠acabb⧠⧠⧠…
Halts in y or n?
L(M) = ?
------------------------------------------------------
| |
v a b |
>Ra,⧠ ----------------------------->$L⧠Rb,⧠ ---------->#L⧠
| |
|⧠ |⧠
| |
| |
v v
L⧠ L⧠
| |
|------------#<-------- |------------$<-------
v b | b v a |a
Rb,⧠ ------>#Rb,⧠------- Ra,⧠ ------->$Ra,⧠------
| | | |
|⧠ |⧠ |⧠ |⧠
| | | |
v # $ v v $ # v
L-------> y <-------L L-------> y <------L
| | | |
|⧠,$ |⧠,# |⧠,# |⧠,$
| | | |
v v v v
n<------------------- n <-----------------