Over a million developers have joined DZone.
Platinum Partner

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

· DevOps Zone

The DevOps Zone is brought to you in partnership with New Relic. Improving the performance of your app is easy with New Relic's SaaS-based monitoring.

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.

The DevOps Zone is brought to you in partnership with New Relic. Know exactly where and when bottlenecks are occurring within your application frameworks with New Relic APM.


Published at DZone with permission of Shannon Behrens , DZone MVB .

Opinions expressed by DZone contributors are their own.

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

{{ parent.tldr }}

{{ parent.urlSource.name }}