Can any language potentially be used to create any program?

Question

I've heard that given a programmer with enough time and skill in any particular language and enough lines of code, then any program could be created with any given language. I know its certainly not going to be cost-efficient, for instance, to rewrite Adobe Photoshop in BASIC, but could a good enough and patient enough programmer potentially create any program in any language?

Answer 1

If a language is Turing complete, then theoretically you can write any program in it -- However, even this has some limitations, such as user interface and OS APIs. For example, Brainfuck is Turing complete, but there's no way to have a GUI because you can't access video memory, and there's no threading support. However, it is possible to do any computational task with it.

Answer 2

This depends on exactly how you define "any program" and "any language".

Let's start with the first one: "any program". There are many programs (in fact, there are infinitely many programs) that cannot be written at all, regardless of the programming language. One of the most famous ones is the so-called Halting Problem: write a program H, which when given any program P and any input x determines whether P(x) will eventually halt. Alan Turing proved many decades ago that it is impossible for such a program to exist. Ergo, you cannot write this program in any programming language.

Now, let's talk about "any language". There are actually different classes of languages. Some are more powerful than others. For example regular expressions (which are a kind of programming language) can not compute any arbitrary function. They are limited in their computational power. However, most general purpose programming languages are what is generally called "Turing-complete".

Brief bit of history: in order to prove the undecidability of the Halting Problem, Alan Turing invented a hypothetical machine called the Turing Machine. A TM is basically a hypothetical computer with infinite memory, that computes a particular function. It turns out that you can build a Universal Turing Machine which can emulate any other Turing Machine.

At about the same time, Alonzo Church invented the Lambda Calculus. The LC is also an abstract mathematical model of computation, but completely different. People started wondering: which of those two models is more powerful? Is there anything that a UTM can compute that LC cannot and vice versa? Can the LC solve the Halting Problem?

As it turns out, you can write an emulator for a UTM in LC and you can build a TM which interprets LC. This means that a TM can compute everything LC can compute (by simply running it in the interpreter) and LC can compute everything a UTM can compute (by simply running it in the emulator). So, we have

LC ≤ UTM ∧ UTM ≤ LC ⇒ LC = UTM

In English: LC and UTM are exactly equally powerful. In fact, it turns out that every model of computation and every machine and every programming language we have ever found is at most as powerful as LC and UTM and indeed every other model. This leads to the so-called Church-Turing-Thesis which states all sufficiently powerful models of computation are equally powerful and there can be no model of computation that is more powerful than UTM or LC. (There can be models of computation that are less powerful, like for example regular expressions or total functions or a language with only bounded loops.)

We call such models of computation Turing-complete. And, BTW, you don't need much to be Turing-complete.

So, with that out of the way, we can now define what we mean by "any program" and "any language":

If a program can be written in one Turing-complete language, then it can be written in any Turing-complete language.