2009 May 24 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

Carleton College CS 254, Fall 2008, Prof. Joshua R. Davis

Submit your solutions to Problems A, B, C in class on Friday. Do Problem D but do not submit your solution.

A. Do Homework 9 Problem 1.

B. Do Homework 9 Problem 2.

C. Do Problem 103 in the textbook.

D. Describe how to implement arithmetic (+, *, - /) of rational numbers in a Turing machine. For example, if your Turing machine is given input `x+y`

, where `x`

and `y`

are rational numbers, then it should halt with the sum of `x`

and `y`

on its tape. You will need to invent an encoding of arbitrary rational numbers. Elegance and simplicity is preferred to efficiency. When your Turing machine produces fractional answers, they should be in lowest form; you'll need to implement the Euclidean algorithm to accomplish this. (This problem includes Problems 96, 97 in the textbook.)