6.001 Recitation – April 23, 2003
RI: Konrad
Tollmar
• Analyze – “a compiler”
• Computational &
non-computational processes
1.
(analyze 0) -> (lambda(env)
0)
2.
(analyze x) -> (lambda(env) (lookup-variable-value
x env))
3.
(analyze (> x 0))
->
(lambda(env)
(execute-application
(lambda(env)(lookup-variable-value
‘> env))
((lambda(env) (lookup-variable-value
‘x env)) (lambda(env) 0) ))
4.
(analyze (if (> x 0) x (- x))) ->
5.
(analyze (lambda (x) (if (> x 0) x (- x)))) ->
6.
(analyze ((lambda (x) (if (> x 0) x (- x))) -4)) ->
Add While
e.g (while (x > 10) (display x) (set! x (+ x 1))
Add the following to the cond
statement in analyze:
((while? exp) (analyze-while exp))
And we'll need the following procedure. (We'll
use the same while-test and while-body procedures
given above.)
(define (analyze-while exp)
(let ((test (analyze (while-test exp)))
(body (analyze-sequence (while-body exp))))
(define (w-test env)
(if (test env)
(begin
(body env)
(w-test env))
#f))
w-test))
2. Computational &
non-computational processes
Universal
Machines
If EVAL can simulate any machine, and if EVAL is itself a description of a machine, then EVAL can simulate itself
Meta evaluator could simulate any given machine that :
What kind of problems can we solve with a computer?
Turing machines
Turing proposed a theoretical model of a simple kind of machine (now called a Turing machine) and argued that any “effective process” can be carried out by such a machine
• Each machine can be characterized by its program
• Programs can be coded and used as input to a machine
• Showed how to code a universal machine
• Wrote the first EVAL!
Halting problem:
Used this machine to ask if there are problems that cant be solved by a turing machine – eg, a computer
(define (run-for-ever) (run-for-ever))
(define (try p)
(if (halts? p p)
(run-for-ever)
‘halted))
now try (try try) -> contradiction!!
Other non-describable processes:
- Gödel numbers, any system is incomplete
- NP Complete problems, non-efficient alg
A Turing machine is an abstract representation of a computing device. It consists of a read/write head that scans a (possibly infinite) one-dimensional (bi-directional) tape divided into squares, each of which is inscribed with a 0 or 1. Computation begins with the machine, in a given "state", scanning a square. It erases what it finds there, prints a 0 or 1, moves to an adjacent square, and goes into a new state. This behavior is completely determined by three parameters: (1) the state the machine is in, (2) the number on the square it is scanning, and (3) a table of instructions. The table of instructions specifies, for each state and binary input, what the machine should write, which direction it should move in, and which state it should go into. (E.g., "If in State 1 scanning a 0: print 1, move left, and go into State 3".) The table can list only finitely many states, each of which becomes implicitly defined by the role it plays in the table of instructions. These states are often referred to as the "functional states" of the machine.
A Turing machine, therefore, is more like a computer program (software) than a computer (hardware). Any given Turing machine can be realized or implemented on an infinite number of different physical computing devices. Computer scientists and logicians have shown that Turing machines -- given enough time and tape -- can compute any function that any conventional digital computers can compute. Also, a ‘probabilistic automaton’ can be defined as a Turing machine in which the transition from input and state to output and state takes place with a certain probability (E.g. "If in State 1 scanning a 0: (a) there is a 60% probability that the machine will print 1, move left, and go into State 3, and (b) there is a 40% probability that the machine will print 0, move left, and go into State 2".)