Quines and Turing Completeness

[Pradyot Prakash]

I was reading about Quines and somewhere on the wikipedia page it was mentioned that it is somehow related to whether the programming language was Turing Complete.

To quote wikipedia, "Quines are possible in any Turing complete programming language, as a direct consequence of Kleene's recursion theorem."

I have a couple of doubts regarding this:

• Why is it non-trivial to design a quine? I mean write a code that reads in the same source file and prints it back!
  
• How does Turing completeness imply that a programming language can be used to write a Quine?

I did not follow through the proof involving Turing completeness. So if anyone could present it in simpler terms, it would be great.

[Manish Goregaokar]

> I mean write a code that reads in the same source file and prints it back!

Not always possible. Not all languages/implementations can read from a file, and many consider this "cheating" in quine design.

If you look at the examples on that page none of them use files (though some use reflection, which is also considered cheating by some).

I'll have to look at that proof later, but an alternate road to go down is by implementing a brainfuck interpreter in your language (assuming string manipulation), and writing a quine-ish thing in brainfuck that outputs the interpreter too. Just a rough sketch, not sure how to do this concretely.

-Manish Goregaokar

[Dilawar Singh]

> - Why is it non-trivial to design a quine? I mean write a code that

> reads in the same source file and prints it back!

Partly because then it would be no-brainer to design a quine, and there wont
be any use in wondering about them.

Formally, in languages where 'side-effects' are not allowed (untyped lambda
calculus, pure Haskell), you can not open a file but still write a quine. These
things are easier to argue about if one have a shared vocabulary such as Lambda
calculus. Else in plain English, things are hard to explain and easy to confuse.

> - How does Turing completeness imply that a programming language can be

> used to write a Quine?

Turing completeness implies that

Any Turing complete computer A (hardware+Turning complete language) can simulate
any other Turing complete computer B. Now if you are writing your quine on the
same machine, then a program P0 can be mimicked by a another program P1 which can
be mimicked by another program P2 and so on. Somewhere you will get a program Pn
which is character by character same as P0.

Above proves the existence of quine in any Turing complete language (ultimately
you gonna get it). Or you can simply say that P(Q) prints the code of program
Q. There exists a program Q which does the same thing as P(Q), print
the source code of Q => Quine. Assumption that printing the source code is a
computable function. [1]

[1]: http://www.madore.org/~david/computers/quine.html

best,
Dilawar

[Dilawar Singh]

I think DNAs are (almost) quine. DNA are the source code and nucleus is your computer
(hardware+computer language), chemical reactions are basically your computation
elements here. A DNA replicates itself.

Now does it follow that chemical reactions in nucleus are Turing complete?

Probably a good read: http://www.computer.org/csdl/mags/co/2009/01/mco2009010047-abs.html

best,
Dilawar

On Sat, Apr 25, 2015 at 04:26:17AM -0700, Pradyot Prakash wrote:
>I was reading about Quines and somewhere on the wikipedia

><http://en.wikipedia.org/wiki/Quine_%28computing%29> page it was mentioned

>that it is somehow related to whether the programming language was Turing
>Complete.
>To quote wikipedia, "Quines are possible in any Turing complete programming
>language, as a direct consequence of Kleene's recursion theorem."
>I have a couple of doubts regarding this:
>

> - Why is it non-trivial to design a quine? I mean write a code that

> reads in the same source file and prints it back!

> - How does Turing completeness imply that a programming language can be

> used to write a Quine?
>
>I did not follow through the proof involving Turing completeness. So if
>anyone could present it in simpler terms, it would be great.
>

>--
>--
>The website for the club is http://wncc-iitb.org/
>To post to this group, send email to wncc...@googlegroups.com
>---
>You received this message because you are subscribed to the Google Groups "Web and Coding Club IIT Bombay" group.
>To unsubscribe from this group and stop receiving emails from it, send an email to wncc_iitb+...@googlegroups.com.
>For more options, visit https://groups.google.com/d/optout.