How is a Turing-complete/equivalent language defined ?

January 27, 2005 8:05 AM

I always thought "Turing-complete programming language" meant you could write a compiler/interpreter/whatever for that language IN that language, ie. XML is not, XSLT is, C++ is for sure, I guess JavaScript could in a way...
Today I tried to check on that, and apparently it's much more abstract... or something... well I don't know for sure.
Was I wrong ? How is a Turing-complete/equivalent language defined ?
posted by XiBe to computers & internet (27 comments total)

I'm certainly no expert, but as I understand it a language is Turing-complete if it can be programmed to do anything a Turing machine can do. The important factor for all practical purposes is that a Turing-complete language can, as a result, be programmed to anything any other Turing-complete language can do, and so compilers/emulators/what-have-you can be written for other languages in that language.
posted by squidlarkin at 8:17 AM on January 27, 2005

Simply: a programming language is considered Turing-complete if it can emulate a Turing machine, and a Turing machine can emulate that language. That's pretty much it.

The problem is that programming languages are restricted my storage size and addressable memory. So, technically, there are no Turing-complete languages. However, if you get loose with the definition (ignoring the problem of finite storage), then there are a ton of Turing-complete languages.
posted by PantsOfSCIENCE at 8:17 AM on January 27, 2005

Thanks, I understood that from the links I put, but what is a Turing Maching supposed to do, then ?
And also, is my original definition of the thing true enough, or completely irrelevant ?
posted by XiBe at 8:24 AM on January 27, 2005

There are lots of qualifications that are equivalent to Turing-complete, and are easier to understand.
My favorite are register machines, because I think they are a lot easier to conceptualize than Turing machines.

Basically, if you can add and subtract integers, and can do it with no limits (ignoring the problem of finite storage,) then your language is technically Turing-complete.

If a language is Turing-complete, then you can write an interpreter for any language including the original one, in principle.

If you can write an interpreter for a language in that same language, it may still not be Turing-complete, I think, but I'm having trouble thinking of a good counter-example.

Technically, I guess, all real programming languages would have to fall into that second category, because their storage is limited.
posted by sonofsamiam at 8:35 AM on January 27, 2005

XiBe: Start simpler: What is a Turing machine? The important thing to gather from that link is that it's an abstraction. To say that a language is Turing-complete is not to say that it implements these basic functions of some historical computer, but rather that it meets an arbitrary set of requirements that computer scientists call "Turing machines".

That's really all there is to it — it's not a measure of the practical usefulness of a computer language, but a way to take a real language and abstract away all of the implementation details. I'd go so far as to say that a regular programmer doesn't need to think about Turing-completeness; it's pretty firmly in the domain of computing science (and remember that "computing science" or "computer science" is the science of computation, and not the science of computing machines.)

You're thinking of "bootstrapping". A compiler written in the language it compiles is a "bootstrapping compiler" or "self-hosting compiler". It's not quite as clear-cut an issue as Turing-completeness. While I'm sure it's possible to write a Perl compiler in Perl, it would be very difficult and inefficient and I doubt anyone other than Damian Conway would try to do it.
posted by mendel at 8:45 AM on January 27, 2005

Basically the idea is this: Anything that can be calculated, can be calculated by a Turing Machine (This is the Church-Turing thesis, and is not yet proven, but it's probably true).

Now, the neat thing is that a Turing Machine is one of the things that can be "calculated", which is to say, a Turing Machine can be programmed to simulate a Turing Machine.

So, if you can prove that your language is capable of fully running a Turing Machine, then it is Turing Complete and can therefore calculate anything that can be calculated.
posted by Capn at 8:47 AM on January 27, 2005

Technically, I guess, all real programming languages would have to fall into that second category, because their storage is limited.

Even more technically, it's probably the implementations that are not Turing complete. The language specifications themselves probably are. (WARNING: not a certified programming language theorist).
posted by casu marzu at 8:48 AM on January 27, 2005

Actually, there are turing complete languages (I think most language standards allow for turing complete implementations, i.e. with unbounded memory), just no turing complete implementations. Then again, due to paper shortage there's also no such thing as a real world turing machine.
posted by fvw at 8:48 AM on January 27, 2005

Now what's really neat is The Halting Problem. Which is, given a Turing Machine and program, will this program complete in a finite amount of time? You can, of course, figure this out on a Turing Machine, but you don't know if _that_ program will complete in a finite amount of time, so you could calculate _that_ on another Turing Machine...

Now, you may say "well, just don't use a Turing Machine, use a Halting Problem Solving Machine", but recall the Church-Turing thesis, which says that if you can do it on any calculating machine, you can do it on a Turing Machine.
posted by Capn at 9:07 AM on January 27, 2005

As I'm familiar with it, Turing completeness can be expressed in (something like) 4 requirements (see page 10 here):

1) It has integer variables and can perform arithmetic on them (it must be able to handle any integer, no bounds, which already makes this impossible in the real world)

2) It sequentially executes statements

3) It supports selection (if statements)

4) It supports recursion (while statements)

The Church-Turing thesis states (I think!) that its not possible to build a machine conceptually more powerful than a Turing machine.
posted by gsteff at 9:24 AM on January 27, 2005

what everyone else said, but also note that people automatically jump from one implementation to another. so given that someone has proven that lambda calculus ("functions", or the functional part of scheme/lisp) is turing complete, and you want to show that language X is turing complete, you can just show that X is equivalent to lambda calculus. there's no need to go all the way back to paper tapes.

incidentally, your definition (implemented in itself) is a pretty good practical definition, since implementing a language is fairly complex and so requires a pretty general language. it would be hard to think of a language for which meeting that conditon wasn't equivalent to proving turing completeness.
posted by andrew cooke at 9:25 AM on January 27, 2005

gsteff: that's sufficient but not necessary. Turing machines don't directly support the first, for instance, and the lambda calculus doesn't support any of the requirements directly. (We know that since both languages are Turing-complete, though, that you can fake those features if you want to, and a goodly portion of a lambda-calculus or computability course will be dedicated to doing just that.)
posted by jacobm at 9:48 AM on January 27, 2005

One of the interesting and surprising results in computer science is how low the barrier is for Turing-completeness -- you'd pretty much have to try to avoid it. Brainfuck, with just 8 commands, is Turing-complete. (It doesn't even need all 8 -- 2 of them are for input and output, which are irrelevant to Turing-completeness.)

There's no kind of about it -- Javascript is Turing-complete, as is every programming language I know of. (XML, HTML, et al, aren't programming languages.)

The Church Thesis says that Turing machines can compute anything that can be computed, i.e. anything for which there is a well-defined algorithm. If there were a computer program that could do something a Turing machine can't, it would mean that we're absolutely wrong about what our idea of "computable" is. No one has any idea of what such a theoretical capability could be, which is why it's generally accepted that computable = computable by a TM.
posted by Zed_Lopez at 9:48 AM on January 27, 2005

(i believe it's only recently - like the last year or so - that xslt was shown to be turing complete. there's a paper somewhere (google turns up a variety of things, but i don't see the original paper in the first few hits)).
posted by andrew cooke at 10:16 AM on January 27, 2005

This paper from 2002, perhaps? It's the first result from scholar.google.
posted by casu marzu at 11:23 AM on January 27, 2005

This thread has brought a question to my mind (I'll ask it in here because it seems to be on-topic and an offshoot of the discussion):

Are Turing machines (the ones with the one-dimensional tape and the read-write head) special in some way (more special than other Turing-complete state machines), or have they become the standard that all other Turing-complete languages are compared just by historical accident?

I know that Turing machines have only four operation rules. Is this the lowest number of operations a Turing-complete machine can support? If so, I guess that would be a reason that Turing machines are more special than other Turing-complete machines.
posted by painquale at 11:33 AM on January 27, 2005

no, it was by construction and didn't include xquery. it was on lambda. hang on...

rats. i was wrong. this is what i was thinking of, and it's not turing completeness, but first class functions. and it was what, 4 and a bit years ago. time flies...

however, while trying to find that, i found this discussion of what turing completness is not.

on preview - i suspect turing machines are like turing machines just because turing was working on hardware that included paper tapes. i think you could argue lambda calculus is a more compact way of adressing the same issues (it has only three "operations")
posted by andrew cooke at 11:38 AM on January 27, 2005

If you're wondering what a Turing INcomplete language looks like, I'm pretty sure the original RPG was not turing complete, lacking things like if statements and such. We're talking the 1940's versions here.

Using the new version I learned on (RPG/IV) it just BARELY managed to do simple things, like loops. When I say BARELY, it supported binary indicators to decide loops. Yes, I know all other languages de-volve into this at some point, but not many force you to manually set these things before the loop restarts.

I really enjoyed learning RPG/IV, not despite this, but because of this. I liked to think of it as doing more with less. Way less. Programming on it was amazing, you would decide what type of command you wanted to do (say, a "calculation"), then you'd look up the column sheet for that command (the "C" sheet) and it would have a list of what type of instruction each column would trigger. Fill in the dots and go! Woohoo!

In comparison, COBOL was just way too overpowered. Rather than "If all you have is a hammer, everything looks like a nail" it was more like "If you have an entire toolbox, all problems look complicated".
posted by shepd at 11:39 AM on January 27, 2005

"first class" wasn't thr right phrase above. sorry.
posted by andrew cooke at 11:40 AM on January 27, 2005

No, Turing Machines really aren't special; they were just first. A different (but equivalent) model could have filled that niche.

(On preview: man, the geeks are all over this one!)
posted by Zed_Lopez at 11:43 AM on January 27, 2005

Yeah, lots of things are Turing complete, like The Game of Life. Think about that for a second- a grid with one simple rule is can compute anything that is computable.

The philosopher Daniel Dennett in Freedom Evolves draws some amazing arguments that talk about computability, free will, and determinism.
posted by gus at 12:14 PM on January 27, 2005

You could devise a really boring language that could implement itself and not be Turing-complete. Like the language 1. It only has one statement: "1". It computes the value 1. It can be used to implement an interpreter which, when supplied with any legal 1 program (consisting of "1"), will compile and run it (ignore it), producing the output of that program, which will be 1. That isn't Turing-complete, but it's a self-interpretation-capable language. (And you can run it in any text editor.)

In the general case, a language being able to interpret itself proves nothing. The failed syllogism:

1. Turing machines can all implement Turing machines (by definition).
2. Language X can implement Language X.
3. Therefore Language X is a Turing machine.

That only works if you assume the proposition, which someone above did when saying it probably holds for "fairly complex" languages. Only if by "fairly complex," you already mean "Turing machine."
posted by sidb at 1:49 PM on January 27, 2005

Oh, and by the way, Postscript and TeX are both turing complete, in case someone wants to use text formatting languages to solve the worlds problems.
posted by JZig at 3:45 PM on January 27, 2005

Thank you, everyone!


Language X can implement Language X.

This seems so obvious to me that I feel I'm lost about the meaning of "implementing" a language. Gah.
Also, reading all this, I'm starting to wonder what's the big deal is about Turing completeness.
I'm having a hard time grasping the importance of it all.
posted by XiBe at 4:54 AM on January 28, 2005

by "implement" they mean you can write a compiler/interpreter in that language. so you could imagine using c to write a c compiler, but you couldn't write "a program" that displayed web pages using html (which is what an "interpreter for html" is, i think).

be careful there. i'm not saying html doesn't describe web pages. i'm saying that is all html does. you can't use html to add numbers (i think, although i'm a bit wary about saying that, because you can add numbers in some surprising ways), for example. so html describes web pages, but can't describe a general process that takes html and generates a picture or some text. you can't write (arbitrarily complex) programs in html, in other words.

now that might be obvious, but xsl, which is used to transform xml (or xhtml, which is a kind of html), is turing complete and so can be used to write programs. so you could write a program in xsl to add two numbers, or to calculate the interest in a loan, or even implement doom (well, turing completeness doesn't really talk about input/output/display/graphics, but that's a detail).

and an example the other way. sql is used to extract information from databases. it turns out (standard) sql is not turing complete. so there are some things you simply can't do with sql, no matter how smart you are, or how powerful a computer you run it on. i don't know what they are, myself, but by simply knowing that sql is "incomplete" i know when i get stuck while programming in sql that i need to bear that in mind - it might not be me being stupid, but that what i'm trying to do is simply impossible.

so the big deal about turing completeness is that (1) it's a more precise way of saying "you can do 'real programming' in this language" (the difference between html and c, for example) and (2) it turns out that there's a way in which all "sufficiently powerful" (ie turing complete) languages are the same (if you can solve a problem using c, you can also solve it using perl, or java, or prolog or... because they're all equivalent, in this sense).
posted by andrew cooke at 6:04 AM on January 28, 2005

it turns out (standard) sql is not turing complete.

This statement is giving me horrible flashbacks to my encounters with database theory. Relational algebra, calculus, and fixpoints, oh my!

This has been an interesting and enlightening discussion... though, ultimately isn't the concept of Turing completeness is irrelevant to lay programmers? Picking the right programming language for a job has almost nothing to do with Turing completeness (almost any reasonable candidate would qualify) and everything to do with application-related considerations. Computational power seems more relevant to PL theorists, PL designers, and optimization researchers (e.g. if you're using some model to prove the correctness of some optimization).

... and, changing gears altogether, natural language theory. ATNs, for instance, are Turing Complete, giving them more expressive power than regular, context-free, or context-sensitive languages. But they aren't used much anymore.
posted by casu marzu at 7:34 AM on January 28, 2005

Yes, casu marzu, working programmers rarely think about Turing-completeness. As you say, we don't have to, as any modern programming language is Turing-complete (I was interested to hear shepd's citations of early non-Turing-complete programming languages.) We're never choosing one language over another or this basis.

But it could be relevant for the reason Andrew Cooke cites.
posted by Zed_Lopez at 11:09 AM on January 28, 2005