Agile Zone is brought to you in partnership with:

JJ is a developer advocate for YouTube APIs. His goal is to foster a rich set of third-party applications built on YouTube APIs. He's a well-known member of the Python community. He blogs at on topics such as Python, Ruby, Linux, open source software, the Web, and lesser-known programming languages. Shannon is a DZone MVB and is not an employee of DZone and has posted 18 posts at DZone. You can read more from them at their website. View Full User Profile

Being Turing Complete Ain't All That and a Bag of Chips

  • submit to reddit

I was talking to someone the other day. He said that given two Turing Complete programming languages, A and B, if you can write a program in A, you can write a similar program in B. Is that true? I suspect not.

I never took a class on computability theory, but I suspect it only works for a limited subset of programs--ones that only require the features provided by a Turing machine. Let me provide a counterexample. Let's suppose that language A has networking APIs and language B doesn't. Nor does language B have any way to access networking APIs. It's entirely possible for language B to be Turing Complete without actually providing such APIs. In such a case, you can write a program in language A that you can't write in language B.

Of course, I could be completely wrong because I don't even understand the definitions fully. Like I said, I've never studied computability theory.

Published at DZone with permission of Shannon Behrens, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)


Lester Burnham replied on Mon, 2014/06/02 - 2:21pm

Yes, you are wrong. Turing completeness is about a low level, not about anything on top of that (like any high-level APIs). Arguing that anything on a higher level (like a networking API) could not be implemented indicates that you're not clear on what a "language" is in this context (hint: it's not what you seem to think it is).

Nathan Green replied on Thu, 2014/06/05 - 12:11pm

If two languages are Turing-complete, yes, equivalent versions of the same program can be written in each language. But the proof is even simpler than that, as you don't need to rewrite a program at all. Proof in a single sentence:

Given two Turing-complete languages, A and B, and given a program, P, if P is written in language A, write an interpreter for A in B, otherwise P must be written in language B, therefore write an interpreter for B in A.

Note that Turing-completeness does not imply anything about performance characteristics (execution speed may be unacceptably slow, consume too much memory, etc.). It also does not imply anything about a programming language's suitability for any particular computing task that one might wish to do, how easy it is to learn, etc. Plenty of problems can be solved using languages that are not Turing-complete, and plenty of Turing-complete languages are impractical for most uses.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.