Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 450
sub Avatar asked Apr 02 '10 17:04

sub


1 Answers

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

like image 76
DuoSRX Avatar answered Sep 20 '22 01:09

DuoSRX