CS计算机代考程序代写 Slide 1

Slide 1

The Unsolvability of the Halting Problem
Chapter 19

Languages and Machines
SD

D

Context-Free
Languages

Regular
Languages
reg exps
FSMs

cfgs
PDAs

unrestricted grammars
Turing Machines

D and SD
● A TM M with input alphabet  decides a language L  * iff,
for any string w  *,
● if w  L then M accepts w, and
● if w  L then M rejects w.

A language L is decidable (in D) iff there is a Turing machine that decides it.

● A TM M with input alphabet  semidecides L iff for any string
w  *,
● if w  L then M accepts w
● if w  L then M does not accept w. M may reject or loop.

A language L is semidecidable (in SD) iff there is a Turing
machine that semidecides it.

Defining the Universe
What is the complement of:

AnBn = {anbn : n  0}

{ : TM M halts on input string w}.

Defining the Universe
L1 = { : TM M halts on input string w}.
L2 = { : M halts on nothing}.
L3 = { : Ma and Mb halt on the same strings}.

For a string w to be in L1, it must:
● be syntactically well-formed.
● encode a machine M and a string w such that M halts
when started on w.

Define the universe from which we are drawing strings to contain only those strings that meet the syntactic requirements of the language definition.

This convention has no impact on the decidability of any of these languages since the set of syntactically valid strings is in D.

Our earlier definition:

L1 = {x: x is not a syntactically well formed pair}

{ : TM M does not halt on input string w}.

We will use a different definition:

Define the complement of any language L whose member strings include at least one Turing machine description to be with respect to a universe of strings that are of the same syntactic form as L.

Now we have:

L1 = { : TM M does not halt on input string w}.
A Different Definition of Complement

The Halting Language H
H = { : TM M halts on input string w}

Theorem: The language:

H = { : TM M halts on input string w}

● is semidecidable, but
● is not decidable.

Does This Program Halt?
Concatenate 0 to the end of input
Halt.

Does This Program Halt?
Concatenate 0 to the end of input
Move right
Go to 1.

Does This Program Halt?
times3(x: positive integer) =
While x  1 do:
If x is even then x = x/2.
Else x = 3x + 1
25
76
38
19
58

40
20
10
5
16
29
88
44
22
11
34
17
52
26
13
8
4
2
1
http://www.numbertheory.org/php/collatz.html

H is Semidecidable
Lemma: The language:

H = { : TM M halts on input string w}

is semidecidable.

Proof: The TM MH semidecides H:

MH() =
1. Run M on w.
2. accept

MH halts iff M halts on w. Thus MH semidecides H.

The Unsolvability of the Halting Problem
Lemma: The language:

H = { : TM M halts on input string w}

is not decidable.

Proof: If H were decidable, then some TM MH would decide it. That is, MH behaves like this:

On input :
If is not encoding a TM and string, then reject.
If M halts on input w
Then accept.
Else reject.

Trouble
Define TM Trouble:
On input x:
Run MH on
If MH accepts, then loop.
Else, halt.
(See picture at right.)

Let’s run now Trouble(). This runs MH on , which decides the behavior of Trouble on . There are two possibilities:
Trouble halts. Then MH accepts, so Trouble loops, a contradiction.
Trouble does not halts. Then MH rejects, so Trouble halts, a contradiction.

Lexicographically enumerate Turing machines: TMi, i = 1,2,3,…
Lexicographically enumerate all possible inputs: ij, j = 1,2,3,…
Build the table[i,j] = 1 if TMi halts on j and 0 otherwise
MH can be used to fill in any cell in the table

If table[Trouble, Trouble] = 1, then MH says that Trouble halts on Trouble, so Trouble loops, a contradiction.
If table[Trouble, Trouble] = 0, then MH says that Trouble does not halt on Trouble, so Trouble halts, a contradiction.
Viewing the Halting Problem as Diagonalization
i1 i2 i3 … …
TM1 1
TM2 1
TM3 1
… 1
Trouble 1 1
… 1 1 1
… 1

If H were in D
Theorem: If H were in D then every SD language would be in D.

Proof: Let L be any SD language. There exists a TM ML that
semidecides it.
H = {, w : TM M halts on input string w}
If H were also in D, then there would exist an O that decides it.

If H were in D
M'(w: string) =
1. Run O on .
2. If O accepts (i.e., ML will halt), then:
2.1. Run ML on w.
2.2. If it accepts, accept. Else reject.
3. Else reject.

So, if H were in D, all SD languages would be.
To decide whether w is in L(ML):

Back to the Entscheidungsproblem
Theorem: The Entscheidungsproblem is unsolvable.

Proof: (Due to Turing)
1. If we could solve the problem of determining whether a given Turing
machine ever prints the symbol 0, then we could solve the problem of
determining whether a given Turing machine halts.
2. But we can’t solve the problem of determining whether a given Turing
machine halts, so neither can we solve the problem of determining
whether it ever prints 0.
3. Given a Turing machine M, we can construct a logical formula F that is
true iff M ever prints the symbol 0.
4. If there were a solution to the Entscheidungsproblem, then we would
be able to determine the truth of any logical sentence, including F and
thus be able to decide whether M ever prints the symbol 0.
5. But we know that there is no procedure for determining whether M
ever prints 0.
6. So there is no solution to the Entscheidungsproblem.

IN SD OUT
Semideciding TM H

D
Deciding TM AnBnCn Diagonalize

Context-Free
CF grammar AnBn Pumping
PDA Closure
Closure

Regular
Regular Expression a*b* Pumping
FSM Closure
Language Summary

>C#L❑MH R

h

MH accepts
M

H
re

je
ct

s

(C# makes a copy
of the input)