CS 575, Spring '20, Homework 2
Due on Thursday, January 30th, at the beginning of class
Give two TM programs that each takes as input two binary strings (interpreted
as integers) and outputs the sum of those numbers. One TM will be a
single-tape TM and the other a multi-tape TM. (You may choose the number of
tapes, but use at least 2.) You may use JFLAP or another TM simulator.
To submit:
For each TM,
- High-level descriptions of your TMs, including the format for your inputs
(how they appear on the tape(s)) and output, and how the subtraction is done.
-
The actual TM in the form of a table or diagram.
- The time complexity of your algorithms.
An argument that the extra tape(s) do/don't speed up computation time.