# EsoLang Mailing List FAQ

This is the FAQ for the esolang mailing list## List mechanics

**What mailing lists are there?**

x: blah

y: blah

z: blah

## Turing completeness and the Turing mahcine

By Brian Raiter (breadbox at muppetlabs.com)**Turing complete languages**

A given programming language is said to be Turing-complete if it can be shown that it is computationally equivalent to a Turing machine. That is, any problem that can be solved on a Turing machine using a finite amount of resources (i.e., time and tape), can be solved with the other language using a finite amount of its resources.

Typically, one proves a given language is Turing-complete by providing a recipe for translating any given Turing machine program into an equivalent program in the language in question. Alternately, one can provide a translation scheme from another language, one that has already been proven to be Turing-complete.

Nearly every existing computer language is Turing-complete. About the only computer languages that aren't Turing-complete are a handful of special languages that are capable of LESS than a Turing machine -- usually because some limitation is "hard-wired" into the language's structure or definition. (For example, Hofstadter's designed a language called BlooP so that it was impossible for it to have a iteration structure with an arbitrarily high upper bound.)

Because of this fact, the exact definition of a Turing machine isn't particularly important, and in fact any given CS instructor (or textbook) is going to provide a slightly different version of a Turing machine. Basically, a Turing machine is an abstract model for a programmable machine, something that nowadays we would think of as a programming language. It was invented by Alan Turing as a theoretical object which he essentially used to give a concrete basis for proving theorems about algorithms, in the days before electronic computers.

**The Turing machine**

The Turing machine is usually presented as a read-write head over an arbitrarily long (though finite) length of tape. At each position on the tape is recorded a symbol which the head can read and/or overwrite with a new symbol. The machine's programming is mainly determined by a set of states. At each tick of the Turning machine's clock, the Turing machine reads the symbol recorded at its current position on the tape, writes a new symbol at that position (or possibly retains the existing symbol), moves the read-write head one position to the left or right (or perhaps remains at the current location), and determines the new state to be in at the start of the next tick (again, possibly the same as the current one). One state is specially marked as the initial state; the machine begins a run in that state. Any number of states may also be marked as final states; the machine ends its run upon reaching one of those states.

**Turing completeness**

What is interesting in Turing-completeness is that it is the most rigorous definition of "what can be done by algorithmic computation": it is a hypothesis, impossible to prove, that there are no problems that can be solved by mechanical computation but cannot be solved by Turing machines. This is impossible to prove because the concept of "mechanical computation" is an intuitive, not a formal one.

Of course, there are systems that are more efficient at solving problems than Turing machines.

An interesting aside is that there are problems that are proven not to be possible to be solved by a Turing machine. As a result, they are suspected not to be solvable by any mechanical computational system.

- Regular languages, that can be recognised by finite automata

- Context-free languages, that can be recognised by pushdown (aka stack) automata

- Contextual languages, that can be recognised by Turing machines

- Finite automata: regular expressions, all systems that have finite state (such as every concrete system), ...

- Context-free languages: Forth without free storage, LR grammars such as yacc, ...

- Turing machines: Lambda Calculus, Combinatory Logic, Semi Thue Grammars, and most programming languages

## Where can I find out more about...

**Brainfuck**

spec: http://url

compilers: http://url

## Good books related to esoteric languages?

Al. Andreou (ee4299 at ee.teiath.gr) asked:
Can someone provide a list of books that will be useful to the esolang enthusiast with no theoretical CS background.

Markus Kliegl (markus.kliegl at t-online.de) responded thusly:
Besides looking at many esoteric languages, I'd say looking at "normal" languages and their paradigms and theoretical backgrounds is a lot more revealing and interesting than reading some random CS (theory) books. I personally like Common Lisp, Ocaml, and Mercury a lot. Others on this list seem to favor Haskell, Erlang, Scheme, Forth, etc.

Maybe reading about some general concepts like turing machines (or "state" in general), lambda calculus (or the "functional" paradigm), combinators, etc. would be useful. The other popular subject here is of course compilers.

Anyway, here's a list of some of the things I enjoyed reading (some may be rather irrelevant to this list):

http://citeseer.nj.nec.com/hughes84why.html

Search google for many versions

http://members.aol.com/NeoNoetics/MindsBrainsPrograms.html

http://citeseer.nj.nec.com/188611.html

(I'd recommend reading the last two in that order)

http://citeseer.nj.nec.com/mccarthy60recursive.html

http://www.cl.cam.ac.uk/Teaching/Lectures/funprog-jrh-1996/

(This probably comes closest to your request for a good book.)

The first two chapters of

Chris Pressey (cpressey at catseye.mb.ca) also responded:
Maybe reading about some general concepts like turing machines (or "state" in general), lambda calculus (or the "functional" paradigm), combinators, etc. would be useful. The other popular subject here is of course compilers.

Anyway, here's a list of some of the things I enjoyed reading (some may be rather irrelevant to this list):

**Why Functional Programming Matters**by John Hughes.http://citeseer.nj.nec.com/hughes84why.html

**The Principia Discordia**Search google for many versions

**Minds, Brains, and Programs**by John R. Searlehttp://members.aol.com/NeoNoetics/MindsBrainsPrograms.html

**Elephants Don't Play Chess**by Rodney A. Brookshttp://citeseer.nj.nec.com/188611.html

(I'd recommend reading the last two in that order)

**Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I**by John McCarthyhttp://citeseer.nj.nec.com/mccarthy60recursive.html

**Introduction to Functional Programming**by John Harrisonhttp://www.cl.cam.ac.uk/Teaching/Lectures/funprog-jrh-1996/

(This probably comes closest to your request for a good book.)

The first two chapters of

**The Emperor's New Mind**by Roger Penrose might interest you, too.
I understand that the first edition of the "Dragon" book (

http://www.amazon.com/exec/obidos/tg/detail/-/0201100886/

http://www.amazon.com/exec/obidos/tg/detail/-/0471958468/

http://www.amazon.com/exec/obidos/tg/detail/-/019510269X/

Some on this list would probably recommend

http://www.amazon.com/exec/obidos/tg/detail/-/0465026567/

http://www.amazon.com/exec/obidos/tg/detail/-/0679785892/

Plus there was one library book whose title I can't remember, but I think it had the word "Mind" in it, but I'm pretty sure the authors' names were Levine & Levine. Google revealed nothing concrete, but it was a good book overall, covering some *very* early attempts at "programming language" design, like the Principia Mathematica and even earlier stuff.

http://www.amazon.com/exec/obidos/tg/detail/-/0838820905/ ?

This book also comes up from time to time, and is available for free as a PDF:**Compilers: Principles, Techniques, and Tools**by Aho, Sethi, & Ullman) has some pretty esoteric stuff in it. I only have the 2nd edition, it's pretty good too.http://www.amazon.com/exec/obidos/tg/detail/-/0201100886/

**Understanding Programming Languages**by Ben-Arihttp://www.amazon.com/exec/obidos/tg/detail/-/0471958468/

**Patterns in Software**by Gabrielhttp://www.amazon.com/exec/obidos/tg/detail/-/019510269X/

Some on this list would probably recommend

**Goedel, Escher, Bach: an Eternal Golden Braid**by Hofstaedter but it was just too geeky/starry-eyed for my taste. I much preferred**Fear and Loathing in Las Vegas**by Thompson.http://www.amazon.com/exec/obidos/tg/detail/-/0465026567/

http://www.amazon.com/exec/obidos/tg/detail/-/0679785892/

Plus there was one library book whose title I can't remember, but I think it had the word "Mind" in it, but I'm pretty sure the authors' names were Levine & Levine. Google revealed nothing concrete, but it was a good book overall, covering some *very* early attempts at "programming language" design, like the Principia Mathematica and even earlier stuff.

http://www.amazon.com/exec/obidos/tg/detail/-/0838820905/ ?

**Advanced Programming Languages Design**

ftp://ftp.aw.com/cseng/authors/finkel/apld/

## Is Language *x* Turing Complete?

Rune Berge (rune at krokodille.com) asked:
I am currently working on my own minimalistic language and have the following question: Is a working brainfuck interpreter sufficient to prove that the language is Turing complete? I'm pretty sure it is, but it'd be nice to have it confirmed.

Daniel B Cristofani (cristofd at hevanet.com) responded thusly:
Yes, for certain values of "working". :) The most direct way to check whether your interpreter's version of brainfuck is known to be Turing-complete is to use it to run the brainfuck utm available at http://www.hevanet.com/cristofd/brainfuck/utm.b and see what answers you get. There's a simple test case in the second paragraph, and that should test everything except whether the storage is practically inexhaustible.