CS 60, Assignment 12

Computer Science 60
Principles of Computer Science
Spring 2011

Assignment 12: More JFLAP, Proofs of Uncomputability, and a little review [100 Points]
Due Monday, April 25 11:59pm

This week's homework is a combination of several ideas you've learned so far in CS60. First you'll practice building a Turing Machine, and then prove that some languages are not computable at all. Next you'll have a chance to write the same (simple) program in 3 different languages.

This is the second-to-last (required) homework in CS60. There will be one more required assignment, and then a totally optional extra credit assignment offered during projects week.

A note about partners: This week problem 1 should be done individually, though as always you can discuss your general approach with anyone else, especially the grutors and profs. For problem 2 you should again feel free to discuss your approach, but you must write up both proofs individually. Problem 3 may be done individually or with a partner (and you only need to submit one version between the two of you).

The problems

Problem 1: Turing Machines

(20 points -- this must be done individually)
Build a Turing Machine to accept the langage:

  L = { w | w contains only 0's and the length of w is a power of 2 }.

Although it is not regular, it is decidable. That is to say, there is a Turing machine that accepts it.

We highly recommend spending some time thinking about this problem and sketching a solution on paper before using JFLAP. If you design the Turing Machine carefully, you can build it using fewer than nine states. (Perhaps far fewer -- see the extra credit...)

Save your Turing Machine in a file called part1.jff.

To create a turing machine, select Turing Machine option from the initial JFLAP window. You may want to read the instructions on Turing Machines from the JFLAP on-line tutorial.
Notice that the transitions are of the form Read, Write, Move. If you leave the Read or Write value alone (it will show a lambda initially) it will mean read or write a blank (which is what the tape is made up of, with the exception of the input). The lambda will disappear and the blank will be displayed by a square.
You can assume that the input will be a single, contiguous block of all 0s. Also, you may assume that if there are any 0s on the turing machine's tape, that the read/write head starts at the leftmost zero. Remember that there may be zero 0s!
Remember that Turing Machines can write any symbols they like on the tape. Your Turing Machine may need to write symbols other than 0. Any symbol on your keyboard is a valid symbol to write. Try not to use too many different types of symbols as this gets confusing.
JFLAP allows you to specify multiple states as accepting states and doesn't have an explicit rejecting state. However, your machine should have exactly one accepting state. In order to have a rejecting state, simply make a state that doesn't have any transition rules coming out of it. If you end up in this state, JFLAP will reject the input.

Problem 2: (Un)computing at Nanosoft

(40 points - everyone must submit their own writeup, but you may discuss your approach with any other student, or the grutors or profs)

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 recent 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!
Note: the idea in both of these problems is similar to the examples we did in which we reached a contradiction by creating a halt-checker out of the program that we hope to prove uncomputable. In this case, you'll want to create a halt-checker from a POTDT and a RC. Keep in mind that you can build any function/program/machine you like in order to coax the POTDT and RC into deciding whether a program P halts on an input w.
For this reason, simply citing Rice's theorem isn't allowed for this problem :-)
Submitting these proofs Submit both of your proofs in a plain-text file named part2.txt.

Part 3: languages review...

(40 points - may be done individually or in a pair)

For this problem, you'll submit programs that solve the "best investing strategy problem" in each of the programming languages we have used this term: Prolog, Java, and Scheme. You may remember this problem from CS 5: here the goal is to review each of the languages we have used (not to challenge your algorithmic-design skills). However, see the extra-credit for an extension of this problem that might offer a greater algorithmic challenge - and other big-O fun, as well! We will also review these languages in the final week of CS 60 (with some additional algorithm-design challenges involved!)

The problem is one you may remember from CS 5: given a list of stock prices, one per day, find the maximum profit you can obtain with a single buy and a single sell transaction. If you could buy and sell on any of the days, then you could buy at the lowest price and sell at the highest one. Here, that is not permitted: you may only sell on a day that is on or after the day you buy. Because you can sell the same day that you buy, the smallest profit you might earn is 0.

As an example, consider the prices represented by this list:

[60, 100, 17, 33, 21, 20, 43, 59, 55, 18, 2]

in which day 0's price is 60, day 1's price is 100, and so on. Although the maximum price is 100 and the minimum price is 2, the maximum (per-share) profit you can obtain by selling on a day after purchasing is 42: by buying on day 2 at a price of 17 and selling on day 7 at a price of 59. Here is the same list of 11 prices without commas for copy-and-paste into Scheme and Java:

60 100 17 33 21 20 43 59 55 18 2

In a comment in each of your files, state the big-O running time of your solution in terms of the number of prices N in the list. In a sentence or two, justify your running time claim - however, you do not have to formally analyze your code.

Each of these programs should find the maximum profit possible for a list of prices - while respecting the constraint that the sell day is the same or later than the buy day. Here are some details for each of the three languages:

Prolog In a file named hw12.pl, create a predicate named maxProfit( PriceList, BestProfit ) that takes in a list PriceList of at least two prices and that binds BestProfit to the value of the maximum obtainable profit according to that list of prices. PriceList will always be bound - it does not have to be generated! (I found it helpful to write a couple of helper predicates - feel free to do this!) Be sure to comment all of your predicates - even maxProfit; place a header comment with your name, the filename, and the purpose (Hwk 12, problem 3) at the top of the file.

Racket In a file named hw12.rkt, create a function named (max-profit pricelist) that returns the maximum obtainable profit according to that list of prices, pricelist. You may assume that pricelist has at least two elements (though you may also create base cases that don't make that assumption). Here, too, I found helper functions useful - be sure to comment all of the functions you create and to put a header comment at the top of your file!

Java In a file named hw12.java, create a class named hw12 that has a main method which
1. Prompts the user for the number of stock prices.
2. Then takes in those prices and stores them in an array.
Afterwards, the main method should compute the maximum obtainable profit - and the best buy day and sell day - and then print out all three of those pieces of information (you may break ties arbitrarily). Helper functions are welcome; you may use data members or you may simply use local variables to store data.

For example, here is a possible format for a run of the program:
```
> java hw12
Enter the number of prices:  11
Now, enter the prices: 60 100 17 33 21 20 43 59 55 18 2

Your strategy:
Buy on day 2 and sell on day 7 ...
 ... for a maximum profit of 42 !
  
```
and here is some starting code for obtaining input from the command-line:
```
import java.util.Scanner;

class hw12
{
  public static void main(String[] args)
  {
    Scanner s = new Scanner(System.in);

    System.out.print("Enter the number of prices: ");
    int num_prices = s.nextInt();
    
    int[] prices = new int[ num_prices ];
  }
}
  
```
Again, be sure your methods are commented and that the file also has a suitable header comment.

3 totally optional and fun extra credit challenges...

ExCr 1 [up to +5 points] Extra credit is available for turing machines that accept problem 1's language with as few as possible states. The minimum possible in three states (including the accepting state!), for which +5 points of extra credit is available. Four states = +3, five states = +1. For a further challenge (or "fun"?), you might consider how few symbols you can use once you've minimized the number of states... . Save and submit this turing machine in a file named excr1.jff.
ExCr 2 [up to +5 points] A surprise...?! In the sampleProof.txt file we've shown that the language
```
  {w | w contains an equal number of 0's and 1's in any order.}
  
```
is not regular.
However, now consider the following closely related language:
```
  {w | w contains an equal number of occurrences of the substrings 01 and 10.}
  
```
The substrings may overlap -- thus, this language contains 0110, which contains the pattern 01 once and the pattern 10 once, as well as 101 (this contains the pattern 10 once and the pattern 01 once - they overlap, but that's fine!).

Amazingly, this language is regular! Show that this is true by building a DFA or NFA for this language using JFLAP. Save and submit your solution in a file named excr2.jff.
ExCr 3 [up to +5 points] of extra credit is available for a big-O(N) algorithm for the Java version of the maximum-profit problem, above... (The "default" algorithm is not usually big-O(N).

If you use a O(N) algorithm, be sure to add a comment explaining how you did so - and to be sure the graders don't miss it! No separate file to submit here. Just include your comment in your hw12.java file.

Computer Science 60 Principles of Computer Science Spring 2011