TM M is shown in the diagarm below,with Σ={a,b}, Γ = Σ ∪ {☐,$,#}, and H = {y,n}.

The halting states y and n are the accepting and rejecting states for M when it decides whether

or not a string is in L(M).

Derive a characteristic function for L(M).

see the attachment…

there is the question and class material for your understand.deliver the answer plain Text (*.txt) formet

CSC 520 Spring 2020
Lab #8

(5 points) TM M is shown in the diagarm below,with ∑={a,b}, Γ = ∑ ∪ {☐,$,#}, and H = {y,n}.
The halting states y and n are the accepting and rejecting states for M when it decides whether
or not a string is in L(M).

Derive a characteristic function for L(M).

———————————
| |
v a b |
>Ra,☐ ———>$L☐Rb,☐ ——–>#L☐
| |
| |
| ☐ v a a ☐ a
| L☐Ra,☐——>Ra,☐——>Ra,☐——>L——>y
| | | | |
v |☐ |☐ |a |¬a
n | | | |
v v v v
n n n n

Onion diagram slide 1

• We’ve reached the outer two rings of the language hierarchy

† What it means to decide a language– deciding means yes or no,
a string is definitely in the language or definitely not
TMs can decide aⁿbⁿcⁿ but a PDA cannot — aⁿbⁿcⁿ ∉ CFLs
accepts w if w ∈ L
rejects w if w ∉ L

† What it means to semidecide a language
accepts w if w ∈ L
if w ∉ L, it may reject w, or it may loop forever

• Sample language hierarchy questions that could easily appear on an exam:

T If L contains a finite number of elements then it must be semidecidable.
What is the inner-most layer of the the onion diagram that L belong to?
key concept: the subset relationship of the onion diagram layers

F L ∈ SD → L ∈ D
D is a proper subset of SD, so there must be at least one L in SD that is not in D

T = { J : J is Java source code that declares all variables before using them}
L ∈ D It’s equivalent to saying that L ∈ D, L= { wcw : where w is some word}

F L = { : J is Java source code that compiles into code that halts on string w}
L ∈ D — stay tuned for next time, it’s semi-decidable.
You can tell if ∈ L — compile J, run it, supply w as input, and see if it halts.
If you run it, and wait a long time and nothing happens, does that the program never halt?
It could just be taking a long time. So you can’t tell the diffence between ∉ L,
and the program just taking a long time

T = { : J is Java source code that compiles into code that outputs “a”}
L ∈ SD
L ∉ D

program 1 ∈ L: System.out.println(“a”); – this one line program is in L

program 2 ∉ L: System.exit(1); //not in J

program 3 may or not be in L: while(true) {
continue;
}

program 4 may or not be in L:
int j
while(j < 2,400,00) { System.out.println(math.factorial(j++)); }

TMs raw lecture notes Page 1

System.out.println(“a”);

F L = { : J is Java source code that compiles into code that only outputs “a” one time}
L ∈ SD

program 1 ∈ L: System.out.println(“a”); – this one line program is in L

program 2 ∈ L: System.out.println(“aa”); – this one line program is not in L

program 3 L : System.out.println(“a”);
while(true) {
continue;
}

program 4:
System.out.println(“a”);
int j
while(j < 2,400,00) { System.out.println(math.factorial(j++)); } System.out.println("a");

If you were running these programs, you would not necessarily be able
to tell the difference between 3, which is in the language, and 4, which
is not. So you would only function as a semi-decider.

So not only could you not decide if J ∉ L, you couldn’t even decide if J ∈ L.

In these thought experiments, you who run the programs, play the role of deciding
of semideciding (hopefully) TM.

Recall the lab we did on the first day of course.

You can consider J in the last 4 examples to be equivalent to a TM, a
formalism for expressing an algorithm. (A much more expressive formalism!)

• TMs are a conceptual device used to explore the question of
what can be computed. Since all problems can be translated into
language recognition problems, “what is computable” is equivalent to
a decidable language.

† Gödel’s Incompleteness Theorem — 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). (see Peano axioms on slide 10)

† The Entscheidungsproblem (“Decision problem”). In 520, we call it
deciding a language, equivalent to deciding if a 1st order (including
the ∀ and ∃ quanifiers) can be proven from a set of axioms.

TMs raw lecture notes Page 2

† The mathematician Alan Turing developed his machines as a mechanical way
of computing any computable function.

• Formal definition of TM

A Turing machine M is a sixtuple (K, Σ, Γ, δ, S, H):

• K is a finite set of states;
• Σ is the input alphabet, which does not contain ☐
• Γ is the tape alphabet, which contains ☐. Σ ⊂ Γ
• S ∈ K is the initial state;
• H ⊆ K is the set of halting states;
• δ is the transition function

( (K – H) × Γ) → (K × Γ × {→, ←} )

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.

Are we done? Is there anything beyond the outer ring? (see slides 6 and 7).
Would another ring representing languages s semidecided by quantum computers

The Church-Turing thesis: There is nothing beyond the outer ring. 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.

Most computer scientists accept the CTT, but there are dissenters. (See
“The Church- Turing Thesis: Logical Limit or Breachable Barrier?)

Example TM langauge recognizers in slides 33 & 34, 23 for an advanced one.

Example TM to compute a function (see slide 24)

Fun TM Facts
1. The input tape is infinite in both directions.

2. δ 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.

TMs raw lecture notes Page 3

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.

Definition of active tape (see slide 16)

• Universal Turing Machines (UTMs). Think of them as being like general
purpose computer. A UTM can emulate any other TM, just like a stored
program computer can run any program that compiles into its machine
language.



TMs raw lecture notes Page 4

In: ℇ, a, ab, ba
Out: b, baab
☐☐☐☐ℇ☐☐☐☐ for ℇ ∈ L(M), then M must end up in the “y” state when processing ℇ.
^
☐☐☐☐b$b☐☐☐☐
^
L(M) { w : #a(w() % 2 = 1 and w cannot start with a 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

TMs raw lecture notes Page 5

IN SD OUT

Semideciding TM H Memor

y

: 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 Machin

a

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?

1. Make all true statements theorems?

2. 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 — 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 |-M
n 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 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: u w

Output: uw

Example: ba abba

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 <-----------------