# CS代考 COMP30026 Models of Computation – cscodehelp代写

COMP30026 Models of Computation

Decibale and Undecibale Problems

/ Lecture Week 11. Part 2

Semester 2, 2021

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 1 / 27

Decidable Problems

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 2 / 27

was born in 1912. At that time, “computer” was a job title: a human employed to do tedious numerical calculations.

Legacy: “Turing machine”, the “Church-Turing thesis”, “Turing reduction”, the “Turing test”, the “Turing award”, and much more.

One of Turing’s great accomplishments was to put “computability” on a firm foundation and to establish that certain important problems do not have an algorithmic solution.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 3 / 27

We Have Many Models of Computability

Turing machines (A. Turing, 1936)

Lambda calculus (A. Church, 1936)

Partial recursive functions (S. Kleene, 1936)

Post systems (E. Post, 1943)

Markov algorithms (A. Markov, 1954)

While programs

Register machines

Horn clauses .

Church Kleene

Post Markov

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems

© University of Melbourne 4 / 27

The Church-Turing Thesis

The class of computable functions is exactly the class of functions that can be realised by

⟨insert your favourite model here⟩

External evidence: All the above models are “equivalent” in spite of the fact that they all look very different, and were developed independently.

Internal evidence: It seems that no matter how we “extend” any of them, we fail to get something that is more powerful.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 5 / 27

Decidable Problems

We can phrase these problems as language decidability problems. For example, the acceptance problem for DFAs is whether, given a

DFA D and a string w, D accepts input w.

Since we can encode the DFA as a string, the acceptance problem

can be seen as testing for membership of the language ADFA = {⟨D,w⟩ | D is a DFA that accepts w}

By ⟨D, w⟩ we mean a (string) encoding of the pair D, w.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 6 / 27

DFA Acceptance Is Decidable

Theorem: ADFA is a decidable language.

Proof sketch: The crucial point is that it is possible for a Turing

machine M to simulate a DFA D. M finds on its tape, say

1…n##ab…z##1a2#…#nbn## 1 ## 3 7 ##baa…$

Q Σ δ q0 F w First M checks that the first five components represent a valid DFA,

and if not, rejects.

Then M simulates the moves of D, keeping track of D’s state and

the current position in w, by writing these details on its tape, after $. When the last symbol in w has been processed, M accepts if D is in

a state in F, and rejects otherwise.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 7 / 27

TMs as Interpreters

We won’t give the details of how the Turing machine simulates the DFA. Many tedious low-level programming steps are involved.

However, it should be clear that it is possible for a Turing machine to mimic DFA behaviour this way.

The description of D is nothing but a “program” and the claim is that a Turing machine can act as an interpreter for this language.

Turing machines themselves can be encoded as strings, and then a Turing machine can interpret Turing machines.

This is no more strange than the fact that we can write an interpreter for Haskell, say, in Haskell.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 8 / 27

NFA Acceptance Is Decidable

ANFA = {⟨N,w⟩ | N is an NFA that accepts w} is a decidable language.

Proof sketch: The procedure we gave for translating an NFA to an equivalent DFA was mechanistic and terminating, so a halting Turing machine can do that job.

Having written the encoding of the DFA on its tape, the Turing machine can then “run” the machine M from the previous proof.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 9 / 27

DFA Equivalence Is Decidable

EQDFA = {⟨A,B⟩ | A and B are DFAs and L(A) = L(B)} is decidable.

Proof sketch: We previously saw how it is possible to construct, from DFAs A and B, DFAs for A∩B, A∪B, and Ac.

These procedures are mechanistic and finite—a halting Turing machine M can perform them.

Hence from A and B, M can produce a DFA C to recognise L(C) = L(A) ∩ L(B)c ∪ L(A)c ∩ L(B)

Note that L(C) = ∅ iff L(A) = L(B).

So M just needs to use the emptiness checker on C.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 10 / 27

Generation by CFGs Is Decidable

ACFG = {⟨G,w⟩ | G is a CFG that generates w} is decidable.

The proof relies on the fact that we can rewrite any CFG to a particular equivalent form, Chomsky Normal Form.

In Chomsky Normal Form, each production takes one of two forms: A→BC or A→a

(With one exception:

We also allow S → ǫ, where S is the grammar’s start variable.)

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 11 / 27

Generation by CFGs Is Decidable

For every grammar in Chomsky Normal Form form, if string w can be derived then its derivation has exactly 2|w | − 1 steps.

So to decide ACFG , we can simply try out all possible derivations of that length, in finite time, and see if one generates w.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 12 / 27

Every CFL Is Decidable

Two slides back we saw that it is decidable whether a CFG G generates a string w.

The decider, call it S, took ⟨G,w⟩ as input.

Now we are saying that any particular CFL L0 is decidable: Theorem: Every context-free language L0 is decidable.

Proof: This is just saying that we can specialise the decider S.

Let G0 be a CFG for L0. The decider for L0 simply takes input w and runs S on ⟨G0,w⟩.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 13 / 27

Every CSL Is Decidable

Theorem: For every context-sensitive language L there is a linear bounded automaton (TM with a bounded tape) M, such that M recognises L.

Theorem: If M is a linear bounded automaton, then L(M) is decidable.

Proof: The number of configurations of M on an input of length n is at most |Q| · n · |Γ|n, where |Q| is the number of states and |Γ| is the size of the tape alphabet (the tape has at most n symbols).

If M accepts w of length n then M does so within at most

|Q| · n · |Γ|n steps. Any computation of length more than |Q| · n · |Γ|n is “cycling” and so cannot accept w. If M can’t accept w within

|Q| · n · |Γ|n steps, it rejects this string.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 14 / 27

The Hierarchy of Language Classes

The diagram shows the relations amongst language classes established so far.

But are there Turing recognisable languages that are not decidable?

As it turns out, yes.

Context-free

Context- sensitive

Turing recognisable

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 15 / 27

Undecidable Problems

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 16 / 27

An Undecidable Language

Now let us study undecidable problems/languages.

We start by showing that it is undecidable whether a Turing machine accepts a given input string. That is,

ATM = {⟨M,w⟩ | M is a TM and M accepts w} is undecidable.

The main difference from the case of ACFG , for example, is that a Turing machine may fail to halt.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 17 / 27

TM Acceptance Is Undecidable

ATM = {⟨M,w⟩ | M is a TM and M accepts w} is undecidable.

Proof: Assume (for contradiction) that ATM is decided by a TM H: H⟨M, w⟩ = accept if M accepts w

reject if M does not accept w Using H we can construct a Turing machine D which decides

whether a given machine M fails to accept its own encoding ⟨M⟩:

1 Input is ⟨M⟩, where M is some Turing machine.

2 Run H on ⟨M,⟨M⟩⟩.

3 If H accepts, reject. If H rejects, accept.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 18 / 27

TM Acceptance

In summary:

D(⟨M⟩) = accept if M does not accept ⟨M⟩

reject if M accepts ⟨M⟩ But no machine can satisfy that specification!

Why? Because we obtain an absurdity when we investigate D’s behaviour when we run it on its own encoding:

D(⟨D⟩) = accept if D does not accept ⟨D⟩ reject if D accepts ⟨D⟩

Hence neither D nor H can exist.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 19 / 27

Comparing Sizes of Sets: Cantor’s Criterion

So what does ‘equals’ and ‘less’ mean for infinite cardinality?

How do we compare the “sizes” of infinite sets? Cantor’s criterion:

card(X) ≤ card(Y) iff there is a total, injective f : X → Y. card(X) = card(Y) iff

card(X) ≤ card(Y) and card(Y) ≤ card(X). As a consequence, there are (infinitely) many degrees of infinity.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 20 / 27

To Infinity and Beyond

X is countable iff card(X) ≤ card(N).

X is countably infinite iff card(X) = card(N).

Examples: Z, Nk , and N∗ (the set of all finite sequences of natural numbers) are all countably infinite.

Importantly, Σ∗ is countable for all finite alphabets Σ, including the alphabet of printable characters on your keyboard.

P(N), N → N, and Z → Z are uncountable, as can be shown by diagonalisation.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 21 / 27

Diagonalisation Showing Z → Z Is Uncountable

Theorem: There is no bijection h : N → (Z → Z). Proof: Assume h exists. Then

h(0),h(1),h(2),…,h(n),… contains every function in Z → Z, without duplicates.

Now construct f : Z → Z as follows:

f (n) = h(n)(n) + 1

Then f ̸= h(n) for all n, so we have a contradiction.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 22 / 27

Why This Is Called Diagonalisation

Here is some hypothetical listing of all the functions h(0), h(1), . . . that make up Z → Z:

h(0) h(1) h(2) h(3) h(4)

19 3 42 42 42 42 42 43 44

6 93 17 45 18 -8

9 … 42 … 47 … 93 …

Models of Computation

(Sem 2, 2021)

Decibale and Undecibale Problems

© University of Melbourne

Why This Is Called Diagonalisation

Here is some hypothetical listing of all the functions h(0), h(1), . . . that make up Z → Z:

f is defined in such a way that it cannot possibly be in the listing: 012345…

f 20 43 45 85 64 … …

3 42 0 7 9 … 42 42 42 42 42 … 43 44 45 46 47 … 93 17 84 6 93 … 18 -8 -5 63 -9 …

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 24 / 27

Algorithms vs Functions

Consider the set of algorithms that realise functions f : Z → Z. How large is that set?

It is infinite, but we can enumerate it. It is contained in Σ∗, where Σ is the set of (printable) characters on my keyboard and that set is countable.

So there cannot be any more, say, Haskell functions, of type Integer -> Integer than there are integers. Namely, each Haskell function is represented finitely, as a finite sequence of symbols from a finite alphabet.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 25 / 27

Algorithms vs Functions

However, we saw that Z → Z is not countable.

In other words, there are number-theoretic functions (in fact, lots of

them) that do not have a corresponding algorithm.

So are there any “important” functions that are not computable? As it turns out, yes, very much so!

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 26 / 27

Problems that Have No Algorithmic Solution

Some undecidable problems:

Are two given CFGs equivalent?

Are there strings that a given CFG cannot generate?

Is a given CFG unambiguous?

Will a given Python program halt for all input?

Will a given Java program ever throw a certain exception?

Next week we will explore some other undecidable problems.

Models of Computation (Sem 2, 2021) Decibale and Undecibale Problems © University of Melbourne 27 / 27