Shortest Universal Turing Machine Implementation

Discussion of Common Lisp
ebie
Posts: 14
Joined: Thu Jun 11, 2009 11:11 pm

Shortest Universal Turing Machine Implementation

Post by ebie » Thu Oct 08, 2009 8:57 pm

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.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Shortest Universal Turing Machine Implementation

Post by ramarren » Fri Oct 09, 2009 12:33 am

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.

TheGZeus
Posts: 79
Joined: Mon Jun 30, 2008 10:46 am

Re: Shortest Universal Turing Machine Implementation

Post by TheGZeus » Fri Oct 09, 2009 8:09 am

see brainfuck (programming language)

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Shortest Universal Turing Machine Implementation

Post by nuntius » Fri Oct 09, 2009 10:54 am

See http://echochamber.me/viewtopic.php?f=1 ... 86&start=0

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

methusala
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Shortest Universal Turing Machine Implementation

Post by methusala » Fri Oct 23, 2009 9:16 am

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

ebie
Posts: 14
Joined: Thu Jun 11, 2009 11:11 pm

Re: Shortest Universal Turing Machine Implementation

Post by ebie » Sat Oct 31, 2009 9:22 pm

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?

methusala
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Shortest Universal Turing Machine Implementation

Post by methusala » Sat Oct 31, 2009 9:35 pm

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

ebie
Posts: 14
Joined: Thu Jun 11, 2009 11:11 pm

Re: Shortest Universal Turing Machine Implementation

Post by ebie » Mon Nov 02, 2009 10:58 am

So, to name a value using only these primitives I would use defun like this?

(defun x () 10)

methusala
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Shortest Universal Turing Machine Implementation

Post by methusala » Mon Nov 02, 2009 12:44 pm

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.

ebie
Posts: 14
Joined: Thu Jun 11, 2009 11:11 pm

Re: Shortest Universal Turing Machine Implementation

Post by ebie » Tue Nov 03, 2009 12:48 pm

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.

Post Reply