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

It's all a question of time, isn't it? The lack of suitable libraries and APIs to use for BASIC may make the Adobe Photoshop project take forever, and it might not run very smoothly when finished, but is theoretically doable.

Answer 3

The language has to be Turing-complete and would also need a way to access the native OS for many different operations like files,sockets etc...

Answer 4

Sure(sorta). There is a trade off, performance. Also some languages may not be able to access certain functions of the system making them unable to do certain tasks on the machine. Some languages are just... weaker than others and it would take a while.

Answer 5

You could also re-create Windows 95 by typing bit for bit into a hex editor but what's the point?

Answer 6

You have to be careful with what you mean by "any program". For example, if you were asked to write a program that creates a text file on disk containing "Hello world", and you were asked to write it in pure Javascript, it would be impossible because pure Javascript has no facility to write anything to disk.

For a thorough discussion of this idea, you may wish to read about computability.

Answer 7

I guess if your language has means to access all the input and output necessary then yes.

Answer 8

If you added "... on a powerful enough computer, and given that the language has libraries that can handle whatever the program needs to do", then the answer would still be no. Some languages can drive programmers so crazy that they kill themselves. If I was ever forced to go back to Visual Basic 3 (no classes or collections) I wouldn't know how to rewrite Notepad.

Answer 9

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.

Answer 10

I think if you add "creative enough" and you include exploitations to be considered programming and the definition of "any program" to be any program that aready exsists, then the answer is yes.