Class 30 - Modeling Computers


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).


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:

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:

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.