CS70, Fall 2003 Discussion #12 Amir KamilUC Berkeley 12/5/03Topics: Computability, Quantum Factoring1 ComputabilityIn this section, we take a look at some advanced topics in computational theory. Besides the halting problem,our discussion is for entertainment purposes only. You are not responsible for the rest of the material here.1.1 IntroductionIn computability and complexity theory, all problems are reduced to language recognition, where a languageis defined as a set of strings over some alphabet, typically {0, 1}. For example, L1= {10, 11, 101, · · · } is thelanguage that contains all prime numbers, represented in binary. Then the problem of determining whetheror not a number x is a prime is the same as determining whether or not x ∈ L1.As a more complicated example, consider the problem of factoring a number N . The language corre-sponding to this problem is L2= {hx, ki : x has a nontrivial factor ≤ k}, where hx, ki denotes an encodingof (x, k) in binary. Then we can determine the factors of N by repeatedly determining whether hN, mi ∈ L2,doing a binary search on m. (For example, in the case of N = 35, we check h35, 35i, h35, 17i, h35, 8i, h35, 4i,h35, 6i, and finally h35, 5i in order to determine that 5 is a factor of 35.)With this formulation of a problem, we show that there exist problems that are not computable.1.2 Uncomputability of ProblemsIt may seem at first that any problem we can come up with can be solved on a computer. This is not thecase, and we can give a non-constructive proof from basic countability theory. Later, we will see actualexamples of uncomputable problems.Consider the set of all problems P . In our formulation above, this is the set of all languages over thealphabet {0, 1}. We prove that P is uncountable using diagonalization. Suppose that P is countable. Thenthere exists an enumeration over P , {L1, L2, · · · }. We construct a new language L0not in this enumerationas follows. If i ∈ Li, then let i 6∈ L0, but if i 6∈ Li, then let i ∈ L0. Note that since L0differs from each Lionthe string i, L0must not be in the enumeration. But L0is a language, since it is a set of strings. This is acontradiction, so no such enumeration can exist, and P is uncountable.Now consider the set of all algorithms A. Any algorithm can be represented as a bit string, since it isjust a sequence of symbols. Thus the set of algorithms is a subset of the set of all bit strings. Since thelatter is countable, A is also countable.Since there are more problems than there are algorithms, there must be problems that are algorithmicallyunsolvable. In fact, there are uncountably infinitely many more problems that are unsolvable than there arethat are solvable.1.3 The Halting ProblemThe classic example of an uncomputable problem is that of determining whether or not a program P haltson a given input x. We show that there is no algorithm to solve this problem.Suppose an algorithm halts(P , x) exists to solve the halting problem. Then consider the followingfunction:Turing(P ):1. If halts(P , P ) then: loop forever;2. Else: halt;1This program is very simple. It checks if its input, which is a program, halts when given itself as aninput. It then does the opposite.Now what happens when we call Turing(Turing)? Well if Turing(Turing) halts, then in line 1,Turing(Turing) will go into an infinite loop, which is a contradiction. And if Turing(Turing) loops,then Turing(Turing) halts in line 2, which is also a contradiction. The only assumption that we made wasthat halts(P , x) exists, so this assumption must have been invalid.1.4 Program MinimalityConsider another interesting question. Given a program P(x) with a particular behavior (where behavioris defined by the output and side effects of a program given a particular input), is it the minimal program(in terms of size) that behaves in this way? Here we show that no algorithm exists that can answer thisquestion.Suppose that there does exist an algorithm minimal(P ) that solves the minimality problem. Then wewrite the following function:paradox(x):1. Let y = own source code.2. For i := y + 1 to ∞ do:3. If i is a valid program and minimal(i) then:4. Simulate i on x;5. Halt;There are a few subtle points about this program. First, the program can obtain its own source code,by reading itself from disk or memory. (If you are familiar with Turing machines, the recursion theoremallows a Turing machine to obtain a description of itself.) Second, a program is just a bit string, so wecan add a number to this bit string to obtain another program. We can also check that a bit string is avalid program by running a compiler on it. Lastly, it is possible for a program to simulate another, usingsomething similar to the metacircular evaluator you’ve seen in CS61A. Thus this is a valid program.Now let’s turn to the behavior of this program. It searches for a program longer than itself that it isminimal. Note that it will always find one, since the sets of possible programs and program behaviors are(countably) infinite. Once it finds one, it simulates that program.But this is a contradiction! The program i that paradox(x) found must be minimal, and it also mustbe longer than paradox(x). But paradox(x) simulates i, so i cannot be minimal. Thus minimal(P ) mustnot exist.1.5 MembershipConsider the set of boolean programs that take in a bit string as input1, i.e. of the formboolean prog (x):· · ·return true ;· · ·return false ;We can define the language Lprogthat corresponds to such a program as the set of strings that the programaccepts, i.e for which it returns true . The inputs the program rejects, or returns false for, and thosefor which it loops are not in its language. (Notice that two programs that have the same behavior haveequivalent languages.) The membership question, then is, given a particular program P and its input x, isx ∈ LP? We prove that this problem is uncomputable. Note that the language corresponding to membershipis A = {hP, xi : P accepts x}.1We could always convert a function that takes in no inputs to one that does and ignores its input. Similarly, we couldconvert a program that takes in multiple inputs to one that takes in only one, by using a sufficient encoding of the inputs.2Suppose we had a function accepts(P , x) that solves the membership problem. Recall that the set of allprograms is countable, so we can enumerate it as {P1, P2, · · · }. Then we can construct the following program:boolean P0(x):1. If
View Full Document
Unlocking...