Is it possible to create a quine in every turing-complete language?

views:

241

answers:

+11 Q:

Is it possible to create a quine in every turing-complete language?

I just wanted to know if it is 100% possible, if my language is turing-complete, to write a program in it that prints itself out (of course not using a file reading function)

So if the language just has the really necessary things in order to make it turing complete (I would prove that by translating Brainf*ck code to it), like output, variables, conditions and gotos (hell yes, gotos), can I try writing a quine in it?

I'm also asking this because I'm not sure that a quine directly fits into Turing's law that the turing machine is capable of any computational task. I just want to know so I don't try for years without knowing that it may be impossible.

+9 A:

Any programming language which is Turing complete, and which is able to output any string (by a computable function of the string as program — this is a technical condition that is satisfied in every programming language in existence) has a quine program (and, in fact, infinitely many quine programs, and many similar curiosities) as follows by the fixed-point theorem.

See here

DuoSRX 2010-04-02 17:15:39

Brilliant link. +1

Norman Ramsey 2010-04-03 19:32:50

I think you mean any *computable* string. Some people (using classical logics, no doubt) would have it that there are non-computable strings (of infinite length, obviously ;-)

SamB 2010-04-11 19:58:58

+3 A:

I ran into this issue a couple of months ago.

While writing a quine doesn't necessarily prove that a language is Turing Complete, it is a strong suggestion ;) As far as Turing Completeness goes, if you can (like you said) provide a valid translation from your language to another Turing-Complete language, then your language is Turing Complete.

That being said, any language that is Turing Complete that can output a string should be able to generate a quine. Also, from Wikipedia:

A quine is a fixed point of an execution environment, when the execution environment is viewed as a function. Quines are possible in any programming language that has the ability to output any computable string, as a direct consequence of Kleene's recursion theorem. For amusement, programmers sometimes attempt to develop the shortest possible quine in any given programming language.

Vivin Paliath 2010-04-02 17:22:12

+3 A:

It is possible to have a programming language that cannot print all the symbols in its representation. For example, the I/O may be limited to 7-bit ASCII characters with language keywords in Arabic. That's the only exception I can think of.

David Thornley 2010-04-02 19:17:03

Isn't I/O and encoding more of a hardware/implementation issue? *Theoretically*, if a Turing-Complete is capable of producing arbitrary strings then it should be able to print itself. But you do bring up a good point. For example, the Ook! language is directly mapped to Brainfuck. So is it possible to write a quine in Ook!? What would it print? Would it print Brainfuck code, or Ook! code?

Vivin Paliath 2010-04-03 00:27:52

@David: Well, you could easily have it print out e.g. a URL-encoded UTF-8 representation of a program, perhaps in the form of a data URI (see http://en.wikipedia.org/wiki/Data_URI_scheme). So while you might not be able to write a program that prints its code, you could write a program that prints a permanent URL to its code ;-).

SamB 2010-04-11 20:04:56

@David: If the language only prints out characters within a particular range, and you interpret the output as the solution of any computational problem directly, then the language is not Turing-complete. Turing-completeness refers to the ability to compute functions between natural numbers, not mappings from strings to strings. This is all a matter of input and output encoding though. Even with output using only 7-bit ASCII characters, you can easily encode numerical outputs in them (e.g., trivially, using just the 10 digit range). But the default base-256 encoding will not work.

KirarinSnow 2010-04-27 11:30:12

@SamB: That sounds like cheating. :p

KirarinSnow 2010-04-27 11:31:30

@Vivin: you can have it print either Brainfuck or Ook! code. If the former, then you'd have yourself a Brainfuck/Ook! quine cycle of period 2 if you make the Brainfuck print Ook! code.

KirarinSnow 2010-04-27 11:32:54

@KirarinSnow: it would most likely be cheating if it used a turing-complete URI scheme, but it doesn't, so it's a bit of a gray area... and it's not more cheating than what you proposed to David -- just more convenient ;-)

SamB 2010-04-27 22:56:43

ansaurus

tags:

views:

answers:

Is it possible to create a quine in every turing-complete language?

related questions