185

Corollary G = { M, w | w L(M) } is not Turing-recognizable.

Proof. = ERR, where ERR is the easy to decide language:

ERR = { x { 0, 1 }* | x does not have a prefix that is
a valid code for a Turing machine }.

Counter-assumption: is Turing-recognizable
• Then by Theorem B, ERR = is Turing-recognizable.
• U is known to be Turing-recognizable (Th. E) and now also is
Turing-recognizable. Hence, by Theorem 4.22, U is decidable.

This is a contradiction with Theorem F and the counter-assumption

does not hold. I.e., is not Turing-recognizable.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

186

The Halting Problem is Undecidable

• Analogously to the acceptance problem of DFAs, we can pose

the halting problem of Turing machines:
Does the given Turing machine M halt on input w?

• This is an undecidable problem. If it could be decided, we could

easily decide also the universal language

Theorem 5.1 HALTTM = { M, w | M is a TM and halts on input w } is

Turing-recognizable, but not decidable.

Proof. HALTTM is Turing-recognizable: The universal Turing

machine MU of Theorem E is easy to convert into a TM that
simulates the computation of M on input w and accepts if and
only if the computation being simulated halts.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

1
 187

HALTTM is not decidable: counter-assumption: HALTTM = L(MHALT)

for the total Turing machine MHALT.

Now we can compose a decider for the language U by combining

machines MU and MHALT as shown in the next figure.

The existence of such a TM is a contradiction with Theorem F.

Hence, the counter-assumption cannot hold and HALTTM is not
decidable.

Corollary H = { M, w | M is a TM and does not halt on input w }

is not Turing-recognizable.

Proof. Like in corollary G.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

188

M, w
MU
MHALT

A total TM for the universal language U

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

2
 189

Chomsky hierarchy

• A formal language L can be recognized with a Turing machine if

and only if it can be generated by an unrestricted grammar

• Hence, the languages generated by unrestricted grammars are

Turing-recognizable languages.

• They constitute type 0 languages of Chomsky hierarchy

• Chomsky’s type 1 languages are the context-sensitive ones.

It can be shown that they are all decidable

• On the other hand, there exists decidable languages, which

cannot be generated by context-sensitive grammars

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

190

D, , , … D, , , …

0: Turing-recognizable languages

Decidable languages

U, HALTTM, …
1: Context-sensitive languages

2: Context-free languages ADFA, EDFA, …

3: Regular languages e.g. { akbkck | k 0 }

Finite lang. e.g. {akbk | k 0 }

e.g. { ak | k 0 }

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

3
 191

Halting Problem in Programming Language

The correspondence between Turing machines and programming

languages:

All TMs ~ programming language

One TM ~ program
The code of a TM ~ representation of a program in machine code
Universal TM ~ interpreter for machine language

The interpretation of the undecidability of the halting problem in

programming languages:

``There does not exist a Java method, which could decide

whether any given Java method M halts on input w''.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

192

Let us assume that there exists a total Java method h that returns
true if the method represented by string m halts on input w and
false otherwise:
boolean h(String m, String w)

Now we can program the method hHat

boolean hHat( String m )
{ if (h(m,m))
while (true) ;}

Let H be the string representation of hHat. hHat works as follows:

hHat(H) halts h(H,H) = false hHat(H) does not halt

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

4
 193

5. Reducibility

• The proof of unsolvability of the halting problem is an example of

a reduction:
• a way of converting problem A to problem B in such a way
that a solution to problem B can be used to solve problem A
• If the halting problem were decidable, then the universal
language would also be decidable
• Reducibility says nothing about solving either of the problems
alone; they just have this connection
• We know from other sources that the universal language is
not decidable
• When problem A is reducible to problem B, solving A cannot be
harder than solving B because a solution to B gives one to A
• If an unsolvable problem is reducible to another problem, the
latter also must be unsolvable

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

194

Non-emptiness Testing for TMs

(Observe that the book deals with ETM.)

The following decision problem is undecidable:

``Does the given Turing machine accept any inputs?'’
NETM = { M | M is a Turing machine and L(M) }

Theorem (5.2) NETM is Turing-recognizable, but not decidable

Proof. The fact that NETM is Turing-recognizable will be shown in

the exercises.
• Let us assume that NETM has a decider MTNE
• Using it we can construct a total Turing machine for the
language U
• Let M be an arbitrary Turing machine, whose operation on input
w is under scrutiny

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

5
 195

• Let Mw be a Turing machine that replaces its actual input with the
string w = a1a2…ak and then works as M
• Operation of Mw does not depend in any way about the actual
input.
• The TM either accepts or rejects all inputs:

*
w 0,1 , if w L( M )
L( M )
0 if w L( M )

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

196

*/*, L

*/A, R */a2, R */ak, R */ ,L

……

A/a1, L

The Turing machine Mw

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

6
 197

• Let MENC be a TM, which

• Inputs the concatenation of the code M for a Turing machine
M and a binary string w, M, w , and
• Leaves to the tape the code Mw of the TM Mw

Mw
M, w
MENC

• By combining MENC and the decider MTNE for the language NETM
we are now able to construct the following Turing machine MUT

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

198

Mw
M, w
MTNE
MENC

A decider MUT for the universal language U

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

7
 199

• MUT is total whenever MTNE is, and L(MUT) = U because

M, w L(MUT)
Mw L(MTNE) = NETM
L(Mw)
w L(M)
M, w U

• However, by Theorem F U is not decidable, and the existence of

the TM MUT is a contradiction
• Hence, the language NETM cannot have a total recognizer MTNE
and we have, thus, proved that the language NETM is not
decidable.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

200

TMs Recognizing Regular Languages

• Similarly, we can show that recognizing those Turing machines

that accept a regular language is undecidable by reducing the
decidability of the universal language into this problem

The decision problem is:

'‘Does the given Turing machine accept a regular language?''

REGTM = { M | M is a TM and L(M) is a regular language }

Theorem 5.3 REGTM is undecidable.

Proof.
• Let us assume that REGTM has a decider MTREG

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

8
 201

• Using MTREG we could construct a decider for the universal

language U
• Let M be an arbitrary Turing machine, whose operation on input
w we are interested in
• The language corresponding to balanced pairs of parenthesis
{ 0n1n | n 0 } is not regular, but easy to decide using a TM
• Let Mparenth be a decider for the language
• Now, let MENC be a TM, which on input M, w composes an
encoding for a TM Mw, which on input x
• First works as Mparenth on input x.
• If Mparenth rejects x, Mw operates as M on input w.
• Otherwise Mw accepts x

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

202

x
start
Mparenth

w M

Deciding a regular language: the TM Mw

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

9
 203

• Thus, Mw either accepts the regular language { 0, 1 }* or non-

regular { 0n1n | n 0 }
• Accepting/rejecting the string w on M reduces to the question of
the regularity of the language of the TM Mw

*
0,1 if w L( M )
L( M w ) n n
0 1 |n 0 if w L( M )

• Let MENC be a TM, which

• inputs the concatenation of the code M for a Turing machine
M and a binary string w, M, w , and
• Leaves to the tape the code Mw of the TM Mw
• Now by combining MENC and MTREG would yield the following
Turing machine MUT

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

204

Mw
M, w
MTREG
MENC

A decider MUT for the universal language U

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

10
 205

• MUT is total whenever MTREG is and L(MUT) = U, because

M, w
L(MUT)
Mw L(MTREG) = REGTM
L(Mw) is a regular language
w L(M)
M, w U
• By Theorem F, U is not decidable, and the existence of the TM
MUT is a contradiction
• Hence, language REGTM cannot have a decider MTREG
• Thus, we have shown that the language REGTM is not decidable

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

206

Rice’s Theorem

• Any property that only depends on the language recognized by a

TM, not on its syntactic details, is called a semantic property of
the Turing machine
• E.g.
• ''M accept the empty string'',
• ''M accepts some string'' (NE),
• ''M accept infinitely many strings'',
• '‘The language of M is regular” (REG) etc.

• If two Turing machines M1 and M2 have L(M1) = L(M2),

then they have exactly the same semantic properties

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

11
 207

• More abstractly: a semantic property S is any collection of Turing-

recognizable languages over the alphabet { 0, 1 }

• Turing machine M has property S if L(M) S.

• Trivial properties are S = and S = TR
• Property S is solvable, if language
codes(S) = { M | L(M) S }
is decidable.

Rice’s theorem All non-trivial semantic properties of Turing

machines are unsolvable

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

208

Computation Histories

• The computation history for a Turing machine on an input is

simply the sequence of configurations that the machine goes
through as it processes the input.
• An accepting computation history for M on w is a sequence of
configurations C1, C2, …, Cl, where
• C1 is the start configuration q0 w,
• Cl an accepting configuration of M, and
• each Ci legally follows from Ci–1 according to the rules of M

• Similarly one can define a rejecting computation history

• Computation histories are finite sequences
if M doesn’t halt on w, no accepting or rejecting computation
history exists for M on w

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

12
 209

Linear Bounded Automata

• A linear bounded automaton (LBA) is a Turing machine that

cannot use extra working space
• It can only use the space taken up by the input
• Because the tape alphabet can, in any case, be larger than the
input alphabet, it allows the available memory to be increased up
to a constant factor
• Deciders for problems concerning context-free languages
• If a LBA has
• q states
• g symbols in its tape alphabet, and
• an input of length n,
then the number of its possible configurations is q · n · gn

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

210

Theorem 5.9
The acceptance problem for linear bounded automata
ALBA = { M, w | M is an LBA that accepts string w }
is decidable.

Proof. As M computes on w, it goes from configuration to

configuration. If it ever repeats a configuration, it will go on to
repeat this configuration over and over again and thus be in a
loop.

Because an LBA has only q·n·gn distinct configurations, if the

computation of M has not halted in so many steps, it must be in a
loop.
Thus, to decide ALBA it is enough to simulate M on w for q·n·gn steps
or until it halts.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

13
 211

Theorem 5.10
The emptiness problem for linear bounded automata
ELBA = { M | M is an LBA and L(M) = }
is undecidable.

Proof. Reduction from the universal language (acceptance

problem for general TMs).

Counter-assumption: ELBA is decidable; i.e., there exists a decider

MET for ELBA.

Let M be an arbitrary Turing machine, whose operation on input w

is under scrutiny. Let us compose an LBA B that recognizes all
accepting computation histories for M on w.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

212

Now we can reduce the acceptance problem for general Turing

machines to the emptiness testing for LBAs:

L( B ) if w L( M )
L(B ) if w L( M )

The LBA B must accept input string x if it is an accepting

computation history for M on w.

Let the input be presented as x = C1#C2# #Cl.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

14
 213

B checks that x satisfies the conditions of an accepting computation

history:
• C1 = q0 w,
• Cl is an accepting configuration for M; i.e. accept is the state in
Cl, and
• Ci-1 M Ci:
• configurations Ci-1 and Ci are identical except for the position
under and adjacent to the head in Ci-1, and
• the changes correspond to the transition function of M.

Given M and w it is possible to construct LBA B mechanically.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

214

By combining machines B and MET as shown in the following figure,

we obtain a decider for the acceptance problem of general Turing
machines (universal language).

M, w L(MUT)
B L(MET)
L(B)
w L(M)
M, w U

This is a contradiction, and the language ELBA cannot be decidable.

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

15
 215

B
M, w
MET
MENC

A decider MUT for the universal language U

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

216

5.3 Mapping Reducibility

• Let M =(Q, , , , q0, accept, reject) be an arbitrary standard

Turing machine
• Let us define the partial function fM: * * computed by the
TM as follows:
*
u, if q0 w u q,
M
f M ( w) q {accept, reject }
undefined otherwise

• Thus, the TM M maps a string w * to the string u, which is

the contents of the tape, if the computation halts on w
• If it does not halt, the value of the function is not defined in w

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

16
 217

Definition 5.20

• Partial function f is computable, if it can be computed with a total

Turing machine. I.e. if its value f(w) is defined for every w

• Let us formulate the idea that problem A is ”at most as difficult

as'' problem B as follows

• Let A *, B * be two formal languages

• A is mapping reducible to B, written
A m B,
if there is a computable function f: * * s.t.
w A f(w) B w *
• The function f is called the reduction of A to B

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

218

• Mapping an instance w of A computably into an instance f(w) of B

and
'’does w have property A?''
'’does f(w) have property B?''

f
*

f B
A

Department of Software Systems OHJ-2306 Introduction to Theoretical Computer Science, Fall 2011 27.10.2011

17