Assignment 12: Uncomputability and Complexity

This assignment is due Monday, December 3 at 11:59 pm.

What to submit

There is no programming in this assignment.  You should write up your answers (proofs or analyses) in a plain-text or Microsoft Word file and submit it as hw12.txt or hw12.doc. 

1. (Un)computing at Nanosoft (40 Points)

   You have been hired by Nanosoft. Your boss, Gill Bates, drops by your spacious cubicle sipping a refreshing and stimulating Jolt Cola ("All the sugar, and twice the caffeine!"). Gill begins by reminding you that a decider is a program that takes an input and eventually halts and accepts (says "yes" to its inputs) or rejects (says "no" to its input). For example, a decider for the prime numbers would take a number, perhaps encoded in binary, as input and would eventually halt saying "yes" (it's prime) or "no" (it's not prime).

   • "OK, so here's your first task," says Gill. "We have decided to change our interview process -- we're going to ask all of our job candidates to see if they can write a decider which takes as input a string of 0's and determines whether the number of 0's present is a power of 2."
     
     You sigh, realizing that this would have made for a much less stressful interview than you'd had, what with the complete rewrite of the company's "Vasta" operating system you'd had to build... .
     
     "Here's what I need from you," continues Gill. "I need a program which we'll call a Power of Two Decider Tester (POTDT). The POTDT takes as input a program. The POTDT then decides whether P is a legitimate decider for strings whose length is a power of 2. That is, the POTDT eventually halts and says yes if the program it received was a correct submission for this competition and otherwise the POTDT halts and says no. I need this POTDT program written by tomorrow at 6 AM."
     
     Prove to Gill that this cannot be done, not by 6 AM and not EVER! You may use diagrams to help explain your proof, but your proof must be clear, precise, and rigorous. Your submission on this and the following problem will be graded on clarity and precision of explanation.
     
     Here is a link to an example write-up of the proof we did in class, that the blank-tape halting problem is undecidable.
     
     
   • "Drat!" says Gill upon hearing the news. "OK, then, in that case, I'd like you to write a program called a Regularity Checker (RC). The Regularity Checker takes as input a program P (e.g., a Turing Machine) and it needs to determine whether or not the set of strings accepted by P is a regular language. The RC must always halt with an answer of yes or no!" Prove to Gill that this too is impossible. Again, you may use pictures to help you explain your proof, but your proof must be clear, precise, and rigorous.
     
     Note that if a turing machine runs forever on an input, that input is considered REJECTED for the purposes of defining the language that the TM accepts. This might help!
     
   
   
   
   
   Algorithm analysis
   
   

   Through this part of the assignment, you will be analyzing the running time of algorithms. We will be interested in worst-case analysis. (The best case isn't interesting and the average case is usually difficult to quantify.) You will need to express the worst-case running time using big-O notation. Finally, make sure to show all of your work in each written problem. Explain each step carefully.

2. Warmup! [20 Points]
   
   This problem involves finding the big-O running-time analysis of both iterative (looping) and recursive code.
   
   
   • What is the big-O running time of this portion of code, in terms of n? Explain your analysis clearly and carefully. (Notice how i is increasing!)

             for (int i=1 ; i≤n ; i *= 2)
                for (int j=0 ; j<i ; ++j)
                   // constant time work here
             

   • What is the big-O running time of this portion of code, in terms of n? Explain your analysis clearly and carefully. (Notice how j is increasing!)

             for (int i=1 ; i≤n ; ++i)
                for (int j=1 ; j<i ; j *= 2)
                   // constant time work here
             

   • Consider a directed graph represented as a prolog list of edges, with each edge a [source, destination] pair. For example, G = [ [a,b], [b,a] ] is a two-node graph, with each node connected to the other.
     
     The reachability problem asks whether it is possible to get from one node to another particular node within a given graph. The following is one possible prolog solution, named reach to this reachability problem:
     
     

     reach(A,A,_).     % any node is reachable from itself
                       % below we ask you to explain what this next line is "saying"
     reach(A,B,[[X,Y] | R]) :- reach(A,B,R) ; (reach(A,X,R), reach(Y,B,R)).
             

     For example, here are two representative runs:

     ?- reach( b, a, [[a,b],[b,c],[c,d],[d,e],[e,f],[f,g],[g,a]]).
     Yes
     
     ?- reach( b, h, [[a,b],[b,c],[c,d],[d,e],[e,f],[f,g],[g,a]]).
     No
             

     Note that we are not concerned with generating any bindings here, we are only concerned with checking reachability for a fully-bound set of inputs.
     Briefly explain in English what the second reach rule is "saying". Then, write a recurrence relation for T(n), the running time of the above reach function in terms of n, the number of edges in the graph G. Then, use the recurrence-unwinding strategy to "unroll" this recurrence relation in order to find a big-O running time of this version of reachability. Count each logical operation ; (or) and , (and) as one step. Show all of your work!