Computer Language
Chapter 4: Decidability
Last modified 4/7/21
Copyright By PowCoder代写加微信 assignmentchef
Limitations of Algorithmic Solvability
In this chapter we investigate the power of algorithms to solve problems
Some can be solved
algorithmically
unsolvability
Useful because then can realize that searching for an algorithmic solution is a waste of time
Perhaps the problem can be simplified
In my view also related to complexity (Chapter 7)
Why we study
perspective on computability and its limits
we study whether there is an algorithmic solution and then we
study whether there is an “efficient” (polynomial
Chapter 4.1
Decidable Languages
Decidable Languages
We start with problems that are decidable
We first look at problems concerning regular
languages and then those for context
free languages
Decidable Problems for Regular Languages
We give algorithms for testing whether a finite automaton accepts a string, whether the language of a finite automaton is empty, and whether two finite automata are equivalent
languages (not FAs)
We represent the problems by
The problem of testing whether a DFA B accepts a specific
input w is the same as testing whether (
language A
={(B, w)|B is a DFA that accepts string w} DFA
) is a member of the
Showing that the language is decidable is the same thing as showing that the computational problem is decidable
the elements of A DFA
So do you understand what A
represents? If you had to list what would they be?
is a Decidable Language
Theorem: A
is a decidable language
◼ ProofIdea:PresentaTMMthatdecidesA
), where B is a DFA and w is a string:
1. Simulate B on input w
2. If the simulation ends in an accept state, then accept; else reject
M = On input (
Outline of Proof
Must take B as input, described as a string, and then simulate it
This means the algorithm for simulating any DFA must be embodied in the TM’s state transitions
Think about this. Given a current state and input symbol, scan the tape for the encoded transition function and then use that info to determine new state
The actual proof would describe how a TM simulates a DFA
Can assume B is represented by its 5 components and then we have w
Note that the TM must be able to handle
Keep track of current state and position in w by writing on the tape
any DFA, not just this one Initially current state is q0 and current position is leftmost symbol of w
The states and position are updated using the transition function
When M finishes processing, accept if in an accept state; else reject. The implementation will make it clear that will complete in finite time.
not the same as DFA B’s
◼ ProofIdea:
◼ Because we have proven decidability for DFAs, all we need to do is convert the NFA to a DFA.
is a Decidable Language
◼ N = On input (
1. Convert NFA B to an equivalent DFA C, using the procedure for conversion given in Theorem 1.39
) where B is an NFA and w is a string
) using the theorem we just proved 3. If M accepts, then accept; else reject
◼ Running TM M in step 2 means incorporating M into the design of N as a subroutine
◼ Note that these proofs allow the TM to be described at the highest of the 3 levels we discussed in Chapter 3 (and even then, without most of the details!).
2. Run TM M on input (
Computing whether a DFA accepts any String
it is possible to reach the accept state from
= { | A is a DFA and L(A) =
is a decidable language
A DFA accepts some string
the start state. How can we check this?
We can use a marking algorithm similar to the one used in Chapter 3.
T = On input (A) where A is a DFA:
1. Mark the start state of A
2. Repeat until no new states get marked:
3. Mark any state that has a transition coming into it from any state already marked
4. If no accept state is marked, accept; otherwise reject
In my opinion this proof is clearer than most of the previous ones because
the pseudo
code above specifies enough details to make it clear how to
– implement it
is a Decidable Language
={(A,B)|A and B are DFAs and L(A)=L(B)} ◼ Proofidea
Construct a DFA C from A and B, where C accepts only those strings accepted by either A or B but not both (symmetric difference)
◼ If A and B accept the same language, then C will accept nothing and we can
use the previous proof (for ◼ So,theproofis:
to check for this. ◼ F = On input (A,B) where A and B are DFAs:
Construct DFA C that is the symmetric difference of A and B (details on how to do this on next slide)
Run TM T from the proof from last slide on input (C)
If T accepts (sym. diff=
then accept. If T rejects then reject
How to Construct C
Complement symbol
L(C) = (L(A) ∩ L(B)’)
We used proofs by construction that regular
languages are closed under
, ∩ , and complement
We can use those constructions to construct a FA that accepts L(C)
Wait a minute! The book is quite cavalier! We never proved regular languages are closed under ∩
Regular Languages Closed under Intersection
If L and M are regular languages, then so is L ∩ M
Proof: Let A and B be DFAs whose regular languages are L and M, respectively
Construct C, the “product automation” of A and B
More on this in a minute, but essentially C tracks the states in A and B (just like when we did the proof of union without using NFAs)
Make the final states of C be the pairs consisting of final states of both A and B
In the union case we the final state any state with a final state in A or B
Proof Idea:
For CFG G and string w want to determine whether G generates w. One idea is to use G to go through all derivations. This will not work, why?
Because this method a best will yield a TM that is a recognizer, not a decider. Can generate infinite strings and if not in the language, will never know it.
But since we know the length of w, we can exploit this. How?
is a Decidable Language
A string w of length n will have a derivation that uses 2n
CFG is in Chomsky
1 steps. If any generates w, then This is a variant of breadth first search, but instead of extended the
depth 1 at a time we allow it to go 2n extension, we are okay
1 steps if the
Normal Form.
So first convert to Chomsky
Normal Form
Then list all derivations of length 2n accept, else reject.
1 at a time. As long as finite depth
How can you do this? What is the brute force approach?
Try all possible strings w. Will this work?
The number is not bounded, so this would not be decidable
Instead, think of this as a graph problem where you want to know if you can reach a string of terminals from the start state
Do you think it is easier to work forward or backwards? Answer: backwards
is a Decidable Language
Proof Idea:
Can the start variable generate a string of terminals?
Determine for each variable if it can generate any string of terminals and if so, mark it
is a Decidable Language (cont)
any rule has only marked items, then mark the LHS
Keep working backwards so that if the right
For example, if X mark X
YZ and Y and Z are marked, then
If you mark S, then done; if nothing else to mark and S not marked, then reject
You start by marking all terminal symbols
We cannot reuse the reasoning to show that
is not a Decidable Language
undecidable
not closed under complement and intersection
is a decidable language since CFGs are
As it turns out, EQ
is not decidable!
We will learn in Chapter 5 how to prove things
Every Context
Free Language is Decidable
Note that a few slides back we showed A This is almost the same thing
We want to know if A, which is a CFL, is decidable.
is decidable.
◼ A will have some CFG G that generates it
◼ Now we use this TM and run it on input <it rejects, we reject.◼ This is so close to the prior proof it is confusing. It comes from the fact that a CFL is defined by a CFG.This leads us to the following picture of the hierarchy of languages is decidable, we constructed a TM S that would tell us if any CFG accepts a particular input w.◼ When we proved that A CFG> and if it accepts, we accept, and if
Hierarchy of Classes of Languages
We proved Regular Context-free since we can convert a FA into a CFG
We just proved that every Context-free language is decidable
From the definitions in Chapter 3 it is clear that every Decidable language is trivially Turing-recognizable. We hinted that not every Turing-recognizable language is Decidable. Next we prove that!
Context-Free Decidable
Turing-recognizable
Chapter 4.2
The Halting Problem
The Halting Problem
One of the most philosophically important theorems in the theory of computation
There is a specific problem that is algorithmically unsolvable. In fact, ordinary/practical problems may be unsolvable
Software verification
Given a computer program and a precise specification of what the program is supposed to do (e.g., sort a list of numbers)
Come up with
an algorithm to prove the program works as required This cannot be done!
But wait, can’t we prove a sorting algorithm works?
Note: the input has two parts: specification and task. The proof is not only to prove it works for a specific task, like sorting numbers.
Our first undecidable problem:
Does a TM accept a given input string?
Note: we have shown that a CFL is decidable and a CFG can be simulated by a TM. This does not yield a contradiction. TMs are more expressive than CFGs.
Halting Problem II
= {(M,w)|M is a TM and M accepts w}
Note that this is Turing recognizable:
Simulate M on input w and if it accept, then accept; if it ever rejects, then reject
We start with the diagonalization method
is undecidable
It can only be undecidable due to a loop of M on w.
If we could determine if it will loop forever, then could reject.
is often called the halting problem.
As we will show, it is impossible to determine if a TM will always halt (i.e., on every possible input).
Diagonalization Method
In 1873 mathematician Cantor was concerned with the problem of measuring the sizes of infinite sets.
How can we tell if one infinite set is bigger than another or if they are the same size?
We cannot use the counting method that we would use for finite sets. Example: how many even integers are there?
What is larger: the set of even integers or the set of all strings over {0,1} (which is the set of all integers)
Cantor observed that two finite sets have the same size if each element in one set can be paired with the element in the other
This can work for infinite sets
Function Property Definitions
From basic discrete math (e.g., CS 1100)
Given a set A and B and a function
from A to B
(i.e., f(a) = b for every b
same element in B
one if it never maps two elements in A to the
The function
is onto if every item in B is reached from some value in a
one whereas
For example, if A and B are the set of integers, then
but if A and B are the positive integers, then it is not onto since b = 1 is never hit.
is onto one)
This allows all items in each set to be paired
A function that is one correspondence
one and onto has a (one
An Example of Pairing Set Items
Let N be the set of natural numbers {1, 2, 3, …} and let E be the set of even natural numbers {2, 4, 6, …}.
Using Cantor’s definition of size we can see that N and
E have the same size.
The correspondence f from N to E is f(n) = 2n.
This may seem bizarre since E is a proper subset of N, but it is possible to pair all items, since f(n) is a 1:1 correspondence, so we say they are the same size.
Definition:
N, the set of natural numbers
if either it is finite or it has the same size as
Example: Rational Numbers
Let Q = {m/n: m,n Rational Numbers
N}, the set of positive
Q seems much larger than N, but according to our definition, they are the same size.
Here is the 1:1 correspondence between Q and N
We need to list all of the elements of Q and then label the first with 1, the second with 2, etc.
We need to make sure each element in Q is listed only once
Correspondence between N and Q
To get our list, we make an infinite matrix containing all the positive rational numbers.
That is, N=1 corresponds to 1/1, N=2 corresponds to 2/1, N=3 corresponds to 1⁄2 etc.
Instead use the diagonals, not adding the values that are equivalent
– infinite, would never get to the second row
row. Since 1 This yields a correspondence between Q and N
Bad way is to make the list by going row
So the order is 1/1, 2/1, 1⁄2, 3/1, 1/3, …
Theorem: R is Uncountable
A real number is one that has a decimal representation and R is set of Real Numbers
Includes those that cannot be represented with a finite number of digits, like Pi and square root of 2
Will show that there can be no pairing of elements between R and N
Will find some x that is always not in the pairings and thus a proof by contradiction
Finding a x
◼ To the right is an example mapping ◼ Assume that it is complete
◼ I now describe a method that will be guaranteed to generate a value x not already in the infinite list
◼ Generate x to be a real number between 0 and 1 as follows
◼ To ensure that x ≠ f(1), pick a digit not equal to the first digit after the decimal point. Any value not equal to 1 will work. Pick 4 so we have .4
◼ To x ≠ f(2), pick a digit not equal to the second digit. Any value not equal to 5 will work. Pick 6. We have .46
◼ Continue, choosing values along the “diagonal” of digits (i.e., if we took the f(n) column and put one digit in each column of a new table).
◼ When done, we are guaranteed to have a value x not already in the list since it differs in at least one position with every other number in the list.
Implications
The theorem we just proved about R being uncountable has an important application in the theory of computation
It shows that some languages are not decidable or
Because each Turing machine can recognize a single language and there are more languages than Turing machines, some languages are not recognized by any Turing machine.
uncountably many languages yet only countably
recognizable, because there are many Turing Machines.
even Turing
Corollary: some languages are not Turing
recognizable
Some Languages are Not Turing
∑* is countable
recognizable I
The set of all strings
The set of all Turing Machines M is countable since each TM M has an encoding into a string
Order by length and omit strings that do not represent valid TM’s and we have a countable list of Turing Machines
A finite number of strings of each length, so we can list them by increasing length and hence they are countable
Some Languages are Not Turing
The set of all languages L over ∑ is uncountable
Recall a language is made up of a set of strings, so different from what we just counted on last slide.
Each language is represented by an infinite binary sequence B, where
recognizable II
each position in the sequence corresponds to a string
The set of all infinite binary sequences B is uncountable
Can prove uncountable using same proof used to prove real numbers not countable
L is uncountable because it has a correspondence with B
Since B is uncountable and L and B are of equal size, L is uncountable
◼ So set of TMs is countable and the set of languages is not
◼ Means we cannot put set of languages into a correspondence with set of TMs.
◼ Therefore
is a member of the
…}. We can encode any language as a characteristic binary
Assume ∑* = {s
sequence, where the bit indicates whether the corresponding language. Thus, there is a 1:1 mapping.
some languages do not have a corresponding Turing machine
some languages not Turing
Recognizable
Common Sense Explanation
Comparing languages, a potentially infinite set of strings, versus number of strings
Each language is represented by a sequence of infinite length whereas each individual string is of finite (but unbounded) length
String is to Language as Natural number is to Real Number
Halting Problem is Undecidable
Prove that halting problem is undecidable
We started this a while ago …
M,w Proof Technique:
>| M is a TM and accepts w}
A diagonalization proof
is decidable and obtain a contradiction
Proof: Halting Problem is Undecidable
is decidable
Let H be a decider for A
>, where M is a TM and w is a string, H halts and accepts
if M accepts w;
On input <it rejects◼ Construct a TM D using H as a subroutineD calls H to determine what M does when input string is its own description
Like running a C
D then outputs the opposite of H’s answer
D(
Now run D on its own description
D(
contradiction. Thus, neither TM D or TM H can exist.
++ program where
is the program represented as a
See next slide.
The Diagonalization Proof
The TM D must invert the value on the diagonal. It can do this for
needs to be accept. Contradiction. Similar to proof that Real numbers not countable.
A More Satisfying Proof for CS Majors
The last proof uses some mathematical tricks and is not very intuitive
concrete to most of us
naturally is about programs and
infinite loops
After teaching this many times, I developed
a find less arbitrary since it focuses
programs and infinite loops.
will nonetheless
the same steps as the prior proof
You write a program, halts(P, X) in
more Concrete
Your program halts(P, X) analyzes P and retu
程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.