Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can these sorts of programs exist in every Turing-complete language?

In every Turing-Complete language, is it possible to create a working

  • Compiler for itself which first runs on an interpreter written in some other language and then compiles it's own source code? (Bootstrapping)

  • Standards-Compilant C++ compiler which outputs binaries for, e.g.: Windows?

  • Regex Parser and Evaluater?

  • World of Warcraft clone? (Assuming the language gets the necessary API bindings as, for example, OpenGL and the WoW source code is available)

(Everything here theoretical)

Let's take Brainf*ck as an example language.

like image 993
I can't tell you my name. Avatar asked Apr 08 '10 15:04

I can't tell you my name.


2 Answers

In every Turing-Complete language, is it possible to create a working...

If one Turing-complete language can do it, then they all can. In this sense, they're all equally "powerful". Since everything you described already exists in at least one Turing-complete language, any of these programs can be written in any other Turing-complete language.

However, merely because something is possible doesn't mean it's easy, or even feasible. That's a hugely important distinction, and it's the crux of why different programming languages exist. They're not all equally good at making specific kinds of software -- if they were, we'd only need one language!

like image 187
John Feminella Avatar answered Sep 28 '22 17:09

John Feminella


Turing-Complete only express computation capability, nothing about I/O capability !

like image 36
Rhangaun Avatar answered Sep 28 '22 16:09

Rhangaun