On the importance of Turing completeness | Hacker News Reader

On the importance of Turing completeness

lambda-the-ultimate.org

23 pointsd0mine6 comments

Turing completeness may not be that important in everyday programming, but it's at the heart of CS just like (to pick a lame example) conservation of energy is at the heart of physics.

What still baffles me about Turing completeness is how ubiquitous it is. Everything from Conway's Game of Life to C++ template specialization to Ruby is Turing complete. Only the latter has been explicitly designed for general computation; for the others, it just "emerged". It's almost as if Turing completeness is an aspect of nature, and it takes work and artificial restraint to design an interesting, powerful mechanism that is not Turing complete. I find that fascinating.

Yes. How many systems 'jump' to universality when they start getting powerful is one topic of David Deutsch's upcoming book The Beginning of Infinity. (BTW it happens in other fields too, not just computing.)

While waiting for that new book, I recommend reading his previous book The Fabric of Reality.

This is a very interesting question.. In our world, it doesn't really have any practical consequences. Making a Turing complete language is trivial, you only need increment/decrement, zero and a jump instruction. These things are available on just about any platform.

Given infinite memory (which in practice means an infinite number of states), any particular Turing machine computation can be performed by a specifically constructed pushdown automation or even a finite-state machine. The distinction between the capabilities of Turing machines and less general machines is in what types of computation one particular machine description can perform. There is a particular Turing machine that can simulate any Turing machine (taking a machine description and input for this machine as input), so obviously any Turing computation can be performed by this particular machine.

It would probably be really difficult to program an FSM or a PDA to perform "general" computations, but it would be an interesting intellectual exercise. Try making a programming language (with LISP macros, maybe?) that will let you easily describe a finite-state machine to solve a particular computational problem. Given an infinite amount of code and memory, you could do everything a Turing machine could do.

It's like the recent discussion around the halting problem: how much of a problem is it really in the practical world? You can always design a mathematical contradiction around the general case, but for any particular problem it is possible to describe a solution that works. The difference is that any practical benefit of using a language that is not Turing complete is hid very well.

I wonder how many language designers explicitly thought about the goal of turing completeness or just had it happen as they added high level constructs like functions et al.

Certainly turing completeness does not guarantee a nice language (see brainfuck and friends) and I am sure that there are some non-turing complete DSLs which are very nice to work with. It may just be that when people try to design general purpose languages, they end up with turing completeness.

> Certainly turing completeness does not guarantee a nice language

Actually, I would say exactly the opposite. Turing completeness guarantees you the ability to write a Lisp interpreter in that language, and thereby have "a nice language."

Turing-completeness doesn't guaranty any sort of I/O, which I would make a requirement of a nice language. I may be able to write a Lisp interpreter using Conway's Game of Life, but then I have to represent my Lisp code within the cellular automaton. (The same thing applies to, for example, Brainfuck.)

Also, I'd say that any language which requires me to write a Lisp interpreter to be nice is not a "nice language".

Reply on news.ycombinator.com