Class 30 - Modeling Computers

Schedule

The target date to complete Project 5 is today, but if you haven't finished it it is okay to submit it on Wednesday, 13 April. After that, if you are able to complete Problems 1-7, you should move on to Project 6, even if you were not able to complete Problem 8 of Project 5 (playing Go).

Project 6 is now posted. To be eligible for automatic Red Belt promotion, you need to complete Project 6 (including a good answer to its bonus Problem 8) by Friday, 22 April, and have also completed Project 5 (including Problem 8).

Otherwise, you may qualify for the Red Belt exam by completing Problems 1-7 of both Project 5 and Problem 6. If you do this by Friday, 22 April, you will be able to take the Red Belt exam starting Monday, 25 April (and have an opportunity to ensure at least an A- in the course before the end of the semester).

Slides

Notes and Questions

What makes a good model?

What would a good model of a computer enable?

Turing Machine

A Turing Machine is an abstract model of a digital computer devised by Alan Turing in 1936.

It consists of:

• An infinitely long tape, divided into squares. (The tape is usually thought of as infinitely long only in one direction, but it is equivalent in power to a tape that is infinitely long in both directions.)

• A finite alphabet of symbols. There is a finite set of symbols that can be written into squares on the tape.

• A tape head that can read the alphabet symbol on a single square of the tape. For each step, the tape head reads the symbol at the current tape position, and can move one square either left or right.

• A finite state machine that controls the tape head.

A Finite State Machine is a very simple model of a machine that has a finite amount of memory (unlike the Turing Machine model which has an infinite amount of memory since the tape is infinitely long). A Finite State Machine consists of:

• A finite alphabet of symbols. There is a finite set of symbols that can be written into squares on the tape.

• A finite set of states. Some of the states may be distinguished (for the FSM for a Turing Machine, we typically have a distinguished state called “Halt” where the machine stops if that state is reached).

• A set of decision rules. Each rule is a triple of the form: (state, symbol) → nextstate.

If the machine is currently in state and the next input symbol is symbol, after reading the symbol the state is now in nextstate.

Unlike a Turing Machine, a Finite State Machine can see each input symbol only once. You can think of it as a machine that starts with the input on a finite tape, and process that input from left to right, reading one square at a time.

Parity Machine. Design a finite state machine that checks the parity of a binary number. Your machine should end in state 0 if the input has an even number of 1’s, and end in state 1 if the input has an odd number of 1’s.