Shortest Universal Turing Machine Implementation
Posted: 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.
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.