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

views:

218

answers:

+7 Q:

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.

+2 A:

Yes, of course, all of those. That's what "Turing-complete" means, after all: it can compute everything that can be computed.

Michael Borgwardt 2010-04-08 15:16:40

I can't find a reference backing this up right now, but IIRC it is an open question whether or not there are computable problems that can't be solved by a turing machine. I think this is mostly due to a nebulous definition of what "computable" actually means.

rmeador 2010-04-08 16:00:46

@rmeador Turing invented his idealised machine precisely so that he could reason about what is and is not computable. The paper that introduced the TM concept was called "On Computable Numbers..."

anon 2010-04-08 17:20:16

@Neil Butterworth - but Turing's work on computability does involve a "hand-waving" aspect, in that it *assumes* that anything computable can be computed by a Turing machine, or equivalently it *defines* a computable algorithm as one for which a Turing machine program exists. The work of Kleene and Church is equivalent, and as Kleene said, it's all a bit vague and intuitive.

Daniel Earwicker 2010-04-08 18:45:43

@Daniel: They taught me about the "Church-Turing Thesis", which says that anything reasonably describable as computation can be represented by a Turing machine or equivalent form. So far, nobody's come up with a counterexample, but unless we can find a precise definition for "computable" it's not possible to prove it.

David Thornley 2010-04-08 18:53:36

@David Thornley - exactly, it's also called a "conjecture". It *is* a precise definition of "computable", as yet unchallenged, but it leaves open the far-fetched possibility that some useful form of algorithmic computability might require some capability not present in a Turing machine or (equivalently) the Church lambda calculus.

Daniel Earwicker 2010-04-08 19:26:18

Any algorithm that can be implemented in one Turing-Complete language can be implemented in any other. Your questions have more to do with the operating system services and APIs which must be made available through the language in question.

In short, the answer is yes to all of the above from a formal language point of view.

rixin 2010-04-08 15:18:14

+8 A:

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!

John Feminella 2010-04-08 15:19:15

i don't see why it could be not feasible, if it's possilbe doesn't that mean that's feasible ? Do you have an example ?

LB 2010-04-08 15:25:59

@John +1. Q: Why is there more than one database? A: Because they all suck.

Aaron Digulla 2010-04-08 15:28:39

@LB: Possibility doesn't equal feasibility. Here's a trivial example. Imagine a Turing-complete language in which writing down the instruction "assign value x to symbol y" requires more memory than exists in the entire world. Such a language makes it _possible_ to write Turing-complete programs, but it's not _feasible_ to write them because it's not practical to actually encode the information you want.

John Feminella 2010-04-08 15:29:37

@LB: With Hypersonic, you can create a GUI from SQL. You can add 3D functions. But do you really want to write World of Warcraft in SQL?

Aaron Digulla 2010-04-08 15:29:40

SQL is not Turing-Complete, may be extensions like PL/SQL

hiena 2010-04-08 15:37:46

Agreed. Computational completeness is not linguistic completeness. Even if the language can carry out any computation, it may still be restricted in terms of applicability. In traditional implementations of most esoteric languages, no WoW clone is possible.

Jon Purdy 2010-04-08 16:11:47

John +1: i didn't know the difference, thanks for the insight. I didn't see the nuance between the two words. I thought you were speaking in terms of expressivity. but now i understand your point

LB 2010-04-08 17:52:00

@John: There's also potential performance issues. Does it count as a WoW clone with a frame rate of about 15 per century? Or are you going to say it's not a real clone if you can't go raiding with friends?

David Thornley 2010-04-08 18:59:07

Unfortunately, you completely miss the difference (as does the OP) between computational capability and interface capability...

RBarryYoung 2010-04-09 06:01:38

@RBarryYoung: I stand by the answer. I'm also not sure your conception of Turing machines is correct, based on your comment in the OP's post that BF "cannot do any of these except the third bullet". It can do all of them, but it can't do them _well_. Note the distinction between **capability** and **feasibility**.

John Feminella 2010-04-09 12:49:28

@John: Incorrect. You are confusing the ability to execute *algorithims* with the ability to create and execute *programs*. Turing-machines do the former, they can *not* do the later because they lack that architectural capability. This is an * architectural* limitation, and not an algorithmic one.

RBarryYoung 2010-04-09 14:06:28

Theoretical, yes. But a much more interesting question is if it would be practically possible given a certain "esoteric" programming language.

JesperE 2010-04-08 15:19:16

Every Turing-Complete language could compute the same set of functions. So, a turing-complete language could do all what you wrote because that things are computed with other turing-complete languages.

Jonathan Barbero 2010-04-08 15:19:47

+1 A:

All that being Turing-complete really requires is that you can do simple math, have some variables, and can do a while loop. Or any number of equivalent things. If you want to do real programs, you need a bit more (notably syscalls) and you have to worry about efficiency too (turing machines can be very slow...) In theory there's no difference between turing-equivalent systems, but in practice there is.

If anyone does a WoW client in BF, I will be very impressed!

Donal Fellows 2010-04-08 15:25:52

+3 A:

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

Skeptic 2010-04-08 18:38:28

Typical StackOverflow: the wrong answers are mindlessly voted-up, and the only correct answers languish in obscurity.

RBarryYoung 2010-04-09 06:03:30

+1 A:

No, Turing completeness have nothing to do with I/O and hardwares. However, you can pretend I/O, hardware systems and graphic systems existed by using variables (or the "memory tape"). In BF, you could use the first 2 cells (x, y) for the "pretended" screen resolution, then another x times y cells for all pixels on the screen, then next cell (n) for the "pretended" filesystem size, then next n cells for the filesystem content...

SHiNKiROU 2010-04-09 01:37:35

The first correct answer I've seen here.

RBarryYoung 2010-04-09 06:02:35

ansaurus

tags:

views:

answers:

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

related questions