Page 1 of 2

Shortest Universal Turing Machine Implementation

Posted: Thu Oct 08, 2009 8:57 pm
by ebie
I'm new to programming and have been reading up on fundamental programming theory. So, Turing machines are the first thing I stumble upon. I believe I understand on a very basic level the idea of a Universal Turing Machine (what it is and how it works, it's significance, etc.).

I became intrigued by the idea of it and it seemed like a simple enough setup. I read that lambda calc is equivalent to a turing machine, so I went looking for some examples in lisp and came across The Shortest Universal Machine Implementation Contest http://www.mathrix.org/experimentalAIT/ ... chine.html

The first thing that surprised me was that there wasn't a Common Lisp implementation. Then I saw the one done with mathematica and became skeptical. I don't know much about programming languages, but it seems that a lot can be built into a language. If so, isn't mathematica sort of cheating?

Also, what would a Universal Turing Machine implementation look like in Common Lisp and how would you actually use it? I though I'd be able to find more information on this topic. Any help at all would be greatly appreciated. Thanks.

Re: Shortest Universal Turing Machine Implementation

Posted: Fri Oct 09, 2009 12:33 am
by ramarren
ebie wrote:The first thing that surprised me was that there wasn't a Common Lisp implementation. Then I saw the one done with mathematica and became skeptical. I don't know much about programming languages, but it seems that a lot can be built into a language. If so, isn't mathematica sort of cheating?

Also, what would a Universal Turing Machine implementation look like in Common Lisp and how would you actually use it? I though I'd be able to find more information on this topic. Any help at all would be greatly appreciated. Thanks.
I am not surprised that there is no implementation in CL, since CL was designed as a more industrial/practical language and an Universal Turing Machine is as academic as it gets. While it is extremely important part of computation theory, an actual implementation is not actually useful for anything. Therefore if you want more information about Turing Machines you should start reading about mathematics, not programming.

Re: Shortest Universal Turing Machine Implementation

Posted: Fri Oct 09, 2009 8:09 am
by TheGZeus
see brainfuck (programming language)

Re: Shortest Universal Turing Machine Implementation

Posted: Fri Oct 09, 2009 10:54 am
by nuntius
See http://echochamber.me/viewtopic.php?f=1 ... 86&start=0

Or search for the HQ9+ family of languages (including HQ9+B).

Re: Shortest Universal Turing Machine Implementation

Posted: Fri Oct 23, 2009 9:16 am
by methusala
In my opinion, the below is probably the best example of the shortest meaningful Turing machine code. Church and Turing discovered that the 'lamba machine' invented by Church was equivalent in expressiveness to the Turing machine. It was also invented before the Turing machine, but the Turing machine is less elegantly expressed and thus easier to understand for most people, so to this day students and programmers still study and use the inferior register machine model.

;from http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp
;explained here: http://lib.store.yahoo.net/lib/paulgraham/jmc.ps
; The Lisp defined in McCarthy's 1960 paper, translated into CL.
; Assumes only quote, atom, eq, cons, car, cdr, cond.
; Bug reports to [email protected].

Code: Select all

(defun null. (x)
  (eq x '()))

(defun and. (x y)
  (cond (x (cond (y 't) ('t '())))
        ('t '())))

(defun not. (x)
  (cond (x '())
        ('t 't)))

(defun append. (x y)
  (cond ((null. x) y)
        ('t (cons (car x) (append. (cdr x) y)))))

(defun list. (x y)
  (cons x (cons y '())))

(defun pair. (x y)
  (cond ((and. (null. x) (null. y)) '())
        ((and. (not. (atom x)) (not. (atom y)))
         (cons (list. (car x) (car y))
               (pair. (cdr x) (cdr y))))))

(defun assoc. (x y)
  (cond ((eq (caar y) x) (cadar y))
        ('t (assoc. x (cdr y)))))

(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
       ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
       ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'cond)  (evcon. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list. (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))

(defun evcon. (c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval.  (car m) a)
                  (evlis. (cdr m) a)))))

Re: Shortest Universal Turing Machine Implementation

Posted: Sat Oct 31, 2009 9:22 pm
by ebie
methusala wrote: ; Assumes only quote, atom, eq, cons, car, cdr, cond.
So, this means that defun, quote, atom, eq, cons, car, cdr, and cond are the bare minimum constructs in Common Lisp?

Re: Shortest Universal Turing Machine Implementation

Posted: Sat Oct 31, 2009 9:35 pm
by methusala
Common Lisp is a huge language. Using those primitives one could write all of Common Lisp, but it would be a big undertaking.

Are those primitives all that is needed to reasonably and quickly write the simplest Lisp? Yes, as shown above.

This brings up the question 'what is Lisp'? Lisp is (a version of) the lambda calculus in a programming language form. It was created as an academic exercise/theory in theoretical form, similar to above, by MIT Professor John McCarthy. Steve Russell than created a machine language version of McCarthy's theoretical form. As shown above, the minimum Russell had to do was create machine language equivalents of the above primitives, and the rest could be written in those primitives.

What is 'lambda calculus'? It's a math system which attempted to use functions and recursion as a basis for describing/axiomatizing all of math. It failed to do that because this was later found to not be logically possible. However while it can't do that impossible task it can do any task that is computable. Functional-recursive-combinatory is a much faster way to program than the step by step with side-state approach of the turing maching and all the imperative languages. Probably the only real competitor to Lisp in this 'smart and speedy' approach is the 'combinatory' language Haskell. Prolog is significant but perhaps can be considered a dsl.

Because lambda calculus is computation by recursive 'first class' functions, in programming language terms this means that the defining characteristic of Lisp is it's ability to write itself in itself. In other words it embodies the definition of 'recursive first class function.' You could write Perl in itself, but the code for that would look so ridiculous as to be beyond human comprehension. Whereas with focus you could understand the above within 2 or 3 hours at most. It's the most reasonably concise turing complete self writable language, and thus the most powerful in terms of fast and effective programmer output, which is really the thing that matters most.

Btw-Here's a language that is turing complete when using a subset of only 3 keywords:

Unlambda is a minimal, but impure functional programming language invented by David Madore. It is based on combinatory logic, a version of the lambda calculus that omits the lambda operator. It relies mainly on two built-in functions (s and k) and an "apply" operator (written `, the backquote character). These alone make it Turing-complete, but there are also some I/O functions to make it possible to interact with the user, some shortcut functions and a function for lazy evaluation.

http://en.wikipedia.org/wiki/Unlambda

Recommended Reading:

'To Mock a Mockingbird' by Raymond Smullyan-who was a student of Alonzo Church, inventor of Lambda Calculus. Smullyan also wrote a key modern version of Godel's theorem.

http://en.wikipedia.org/wiki/Raymond_Smullyan

Deep inside the forest dwells the Mockingbird, which imitates other birds hearing themselves. The resulting cascade of calls and responses analogizes to abstract models of computing. With this analogy in hand, one can explore advanced topics in the mathematical theory of computability, such as Church-Turing Computability and Gödel's Theorem.
http://en.wikipedia.org/wiki/To_Mock_a_Mockingbird

http://books.google.com/books?id=6_CcsK ... q=&f=false

Re: Shortest Universal Turing Machine Implementation

Posted: Mon Nov 02, 2009 10:58 am
by ebie
So, to name a value using only these primitives I would use defun like this?

(defun x () 10)

Re: Shortest Universal Turing Machine Implementation

Posted: Mon Nov 02, 2009 12:44 pm
by methusala
That would return 10 from (x) but not x.

To add variables and the set command the eval function would have to be modified. Something like creating a list of variable names and values, and checking unquoted atom names against that list when evaluated. As pg mentioned in the above linked paper, scheme added additional features for handling variables, like lexical scope and a single namespace for functions and variables. Without the ability to use variables, the above lisp is a completely functional programming language. A big advantage of that is that it makes debugging easier, because you don't have to keep track of the state of a variable, or what changed it.

Re: Shortest Universal Turing Machine Implementation

Posted: Tue Nov 03, 2009 12:48 pm
by ebie
I see. So, practically speaking, in order to really be able to use just these primitives, one would need to add SETQ, and if you wanted lexical scoping, LET. I suppose LAMBDA as well, for convenience sake.
methusala wrote:...scheme added additional features for handling variables, like lexical scope and a single namespace for functions and variables.
After reading up on these terms, I think I understand. Scheme uses DEFINE for both bindings and function definitions, because there's no separation between the namespaces. I found this helpful :

http://stackoverflow.com/questions/1020 ... sus-scheme

Thanks.