UW CSE
Spring 1999
CS599: Alternative Computing Paradigms
Instructor: C. Diorio

Homework Set 2
DUE: April 12,1999, 6:30 pm

Collaboration Policy:
Unless noted otherwise, you may collaborate with other CSE599 students on the homework. You must spend at least 15 minutes working on a problem before seeking assistance. Collaboration means that you may discuss the problems and make notes during the discussion, but you may not look at other student’s work when writing up your homework. Your homework represents your own work—the homework must show that you understand the material and have worked as an individual on every problem. You may not divide up the task of doing the problem sets in the interpretation of collaboration.

Late Homework Policy:
The weekly assignments are due at the beginning of class. Assignments handed in after class will incur a 10% penalty; the penalty will increase by 10% for each additional day late.

Reading:
Feynman pgs. 52–129

Please show all of your work, and remember, your solutions must be legible. The points for each problem are noted on the problem statement.

1. (10 pts) Design two DFAs (deterministic finite automata). Both take serial binary strings as their input, and compute the parity of the digits indicated below. All strings are terminated by an "e" symbol (i.e. an "end" symbol). Both automata should halt and output "even" or "odd" when they see the symbol "e". (Instructor’s note: These DFAs form a part of a machine that generates parity bits for a Hamming error-correcting code).

a) Compute the parity of the odd digits in the string (i.e. of digits 1,3,5,7,9…)   b) Compute the parity of alternating blocks of 2 digits (i.e. digits 2,3,6,7,10,11…)   2. (10 pts) Design a Turing Machine (TM) that recognizes sequences of the form s01001100011100001111…0n1ne. "s" indicates the start of the tape, and "e" is the end symbol. Your machine should start at the first symbol to the right of the "s" (the "0"). The machine should end in the accept or reject state. Describe your algorithm in words, using a picture of the tape (e.g. like on pg. 73 of Feynman) to explain what is going on. Also draw a diagram of your TM, like that shown in Fig. 3.11 on p. 70 of Feynman.
 
 
3. (10 pts) Design a TM to convert a base-4 encoded tape to a base-2 encoded tape. The base-4 encoded tape can contain symbols (0, 1, 2, 3); the base-2 encoded tape should only contain (0,1). Describe your algorithm in words, using a picture of the tape to explain what is going on. Also draw a diagram of your TM. Is the base-4 encoding any more powerful than the base-2 encoding (i.e. can you compute anything in base-4 that you cannot compute in base-2)? (Instructor’s note: DNA is a base-4 encoding).
 
 
4. (20 pts) Philosophical questions (explain your reasoning clearly): (a) Can you construct a deterministic finite automaton (DFA) that takes as input a string of 1’s (i.e. 111111111…), and computes whether the number of 1’s in the string is prime?

(b) Can you construct a TM that computes whether two DFAs are equivalent?

(c) Can you construct a TM that, given the radius of a circle, computes the area.

(d) Suppose that you have two unclocked spiking circuits (i.e. circuits that generate delta functions—zero-width voltage spikes—at some arbitrary times t), two delay lines (also of arbitrary length), and a coincidence detector that generates an output spike when its two input spikes are coincident. Can you simulate this arrangement with a DFA? How about with a Turing machine? Does your answer change if the spikes have finite width?