Turing Machines and Sequential Interpretation

3/19/98


Click here to start


Table of Contents

Turing Machines and Sequential Interpretation

Recap: Control and Datapaths

Unbounded Space Computations

Turing Machine

Turing Machine Operation

Turing Machine Operation Example - I

Turing Machine Operation Example - II

Algorithm for Checking anbn Form

Turing Machine for anbn Checking (n > 0)

Computing x + y

Church-Turing Thesis

Universal Turing Machine (UTM)

UTM Viewed as an Interpreter

8-Bit “Toy” Datapath

b on Toy

mCode for b AND

mCode for b ADD

b Instruction Dispatch

Interpretation: Practical Benefits

Next Time: Direct-Execution b Processor

Author: Srinivas Devadas

Email: devadas@mit.edu

Home Page: http://cag-www.lcs.mit.edu/6.004

Download presentation postscript