COMP712 Tutorial #2: - Calculus & Turing Machines
1. What is the number on this tape?
0
1
1
1
1
1
1
1
1
1
1
0
9
2. What is the role of a state table in a Turing machine?.
It is equivalent to your modern day program – it is an effective procedure
3. What is an “effective” procedure?
A method whereby each step is precisely predetermined that when executed will definitely give you an answer in a finite number of steps
4. What do -calculus and Turing machines have in common? What is the key difference between the two approaches?
They are both effective procedures for computing a function. One is hardware based and the other is not.
5. If LISP is so good, why isn’t it a popular language in the commercial world?
Because not everyone is a problem solver. Many use programming languages to get the machines to perform some mundane tasks (such as web page design) and these machines are usually loaded with some other popular languages. By popular, it is meant that languages that many are familiar with, rather than languages best for the task on hand. Note too that other languages are now having many useful features that were once found only in LISP.
One historical reason is that when LISP was invented, the machines were not powerful enough to support such a powerful language. Consequently, earlier versions of LISP were slow and many were trained to use the imperative languages instead. An analogy here would be that many people in Hanoi ride bicycles not because bicycles are more powerful than cars but because they can’t afford to buy cars.
6. Despite LISP being such a wonderful programming language, why do we say LISP is no more powerful than Java?
By that we meant it cannot be used to compute more computable functions than Java.
7. Give an example of an abstraction provided in a high-level language.
The idea of a record or a string.
8. Using Church numerals, write the number 4. What does fx. f x stands for?
fx.f (f (f (f x))) 1
9. Reduce the following lambda expressions:
(a) (x. x) y y
(b) (x. z) y z
(c) (x. (y. y x) z) v z v
(d) (x. xxy) (x. xxy)
(d) reduces to (x. xxy) (x. xxy) y (x. xxy) (x. xxy) yy (x. xxy) (x. xxy) yyy ……. and so on – non-terminating.
10. In -calculus, you are given a function: SUCC = nfx.f (n f x). Show how Succ 1 is derived.
Succ 1 = λnfx.f(n f x) (λfx. fx)
= λfx.f((λfx. fx) f x)
= λfx.f((λx. fx) x)
= λfx.f (f x)
11. What is a Turing Test?
A test designed to evaluate how intelligent a program is.
12. Explain how imperative languages are virtual machine models of a Turing machine.
A TM uses a state table to control the change of states in a program and a tape as memory. The model for designing imperative languages is about state to state changes (e.g, it provides variables to capture a state and assignment statements for changing the states of variables and loop constructs for controlling the flow of the program. Henceforth, it is a virtual machine model of Turing machines.
COMP712 Tutorial #2: LISP
1. For each of these functions, give an example of its use.
(a) Car (car ‘(a b c))
(b) Cdr (cdr ‘(a b c))
(c) caddar (caddar ‘((1 2 3) a b c)) 3
(d) cons (cons ‘(a b) ‘(c d)) ((a b) c d)
(e) append (append ‘(a b) ‘(c d)) (a b c d)
(f) list (list ‘(a b) ‘(c d)) ((a b) (c d))
(g) reverse (reverse ‘((a b) (c d))) ((c d) (a b))
(h) length (length ‘((a b) (c d))) 2
(i) member (member ‘x ‘(a b x c d)) (x c d) ;;why not just x?
(j) setf (setf x ‘(2 3 4)) (2 3 4) ;;why does it return (2 3 4)?
(k) Cond (cond ((= 3 4) 5) ((zerop x) 2) (t nil)) ;;if not sure, ask.
(l) Last (last ‘(a b c)) (c) ;; but try (last (last ‘(a b c)))