Platinum Partner
java,agile,devops,tips and tricks

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

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 {{ articles[0].authors[0].realName }}, DZone MVB. (source)

Opinions expressed by DZone contributors are their own.

{{ tag }}, {{tag}},

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}
{{ parent.authors[0].realName || parent.author}}

{{ parent.authors[0].tagline || parent.tagline }}

{{ parent.views }} ViewsClicks
Tweet

{{parent.nComments}}