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