34

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.

sub
  • 2,653
  • 3
  • 27
  • 29

4 Answers4

33

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
  • 4,179
  • 3
  • 26
  • 32
  • 1
    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 Apr 11 '10 at 19:58
5

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
  • 94,126
  • 40
  • 223
  • 295
4

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
  • 56,304
  • 9
  • 91
  • 158
  • 4
    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 Apr 03 '10 at 00:27
  • @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 Apr 11 '10 at 20:04
  • @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 Apr 27 '10 at 11:30
  • @SamB: That sounds like cheating. :p – KirarinSnow Apr 27 '10 at 11:31
  • @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 Apr 27 '10 at 11:32
  • @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 Apr 27 '10 at 22:56
4

Well, technically, not always. According to the proof on Wikipedia, the programming language has to be an admissible numbering. Practical and sane Turing-complate programming languages are all admissible numberings. And a Turing-complate programming language is an admissible numbering if it's possible to translate between that and another admissible numbering.

An example Turing-complete programming language that is not an admissible numbering:

The source code always contains one or two doublequoted escaped strings. If the input is empty, output the first string if there are two strings, or loop forever if there is one. Otherwise, evaluate the last string in Python, using the original input as input.

It's not an admissible numbering because, given a Python program, we have to know its behavior when the input is empty, to translate it into this language. But we may never know if it is an infinite loop, as we cannot solve the halting problem. We know a translation always exists, though.

It's impossible to write quines in this language.

user23013
  • 586
  • 5
  • 13