5

I have created a turing-complete programming language (already proven) so it must be possible to write a quine for it, right?

But all quines I know store their source code in a string and then replace a special character in it using something like chr and ord.

My language only has the following

  • Basic arithmetics
  • Int and string types
  • Variables
  • == operator
  • Conditional gotos

I have no idea how I could write a quine as I have no real string manipulation available, I can only output constant strings. Yet, it is 100% turing-complete.

Nifle
  • 11,745
  • 10
  • 75
  • 100
ads
  • 53
  • 2
  • 3
    You don't understand what Turing complete means. It doesn't mean you can write any program. –  Apr 11 '10 at 18:53
  • @Neil, I'd stand the question in a different way: does such an encoding of a Turing machine exist, such that it's impossible to write a quine for it? (However, it belongs on mathoverflow) – P Shved Apr 11 '10 at 19:20
  • @PAvel: not sure what you mean by "encoding" of a Turing machine. @Neil: sure it means that you can write **any** program, even if the result may be difficult to read. That's the definition of an universal computer. – kriss Apr 11 '10 at 19:40
  • @kriss Turing complete means you can use the language to calculate any computable result. It doesn't mean you can use it to write Doom or even print "hello world" on the screen. –  Apr 11 '10 at 19:51
  • @kriss: By encoding here I mean "input format for some Universal Turing machine"--i.e. for a Turing machine interpreter. 1st link in google seems to explain this http://www.rci.rutgers.edu/~cfs/472_html/TM/TuringEncodings/TuringEncodings.html – P Shved Apr 11 '10 at 19:51
  • 1
    @PAvel: the answer to your question is already on SO http://stackoverflow.com/questions/2568020/is-it-possible-to-create-a-quine-in-every-turing-complete-language – kriss Apr 11 '10 at 19:53
  • @Neil: I agree with you for programs interacting with users like Doom. But you could write any non interactive part of doom using any turing complete language. Pixels, strings and whatever you use on a computer are mere bits in the end there is no difference between numbers and anything else in a computer (even numbers are **not** numbers but bits). – kriss Apr 11 '10 at 19:58
  • @Pavel: Is there a mathoverflow? What does that name even mean? – SamB Apr 11 '10 at 20:08
  • @kriss, no, SO doesn't contain the answer -- a different question was asked there. But the article linked from the accepted answer contains it: for *each* Turing machine interpreter there exists a quine. – P Shved Apr 11 '10 at 20:12
  • @SamB: there is several sites like stack overflow with different subject matters like MathOverflow for maths [http://mathoverflow.net]. See also SuperUser for system administration related questions. – kriss Apr 11 '10 at 20:15
  • @Pavel: yes, the answer is the link... – kriss Apr 11 '10 at 20:16
  • @anon, I think the OP is referring to the Recursion Theorem, which states that any Turing Machine can obtain its own description. – AlcubierreDrive Nov 18 '10 at 03:28

3 Answers3

3

If you have integers you can encode or decode strings (schemes as simple as A=1, B=2 etc. are enough to do that). You only need to be able to compare constant strings or to compare int. Hence there seems to be no fundamental problem.

You work with numbers and write things like

if (n == 1) print "A"
if (n == 2) print "B"
...

There can be some practical difficulties. The thing with strings is not that you have characters in it but that they are equivalent to very large numbers. What you need here is either to have access to unlimited precision numbers or to some kind of array of fixed size numbers, or other large data structure. An array of numbers will do for you what a string can do. But if your language is Turing complete it should have a way to easily access some large chunk of memory

A Turing complete language limited to a 32 bits tape (or where you must give a new name to each different memory space of 32 bits) would be a pity, not sure you could write a quine with such restriction. By the way it would be interesting to know how you proved that your language was Turing complete if you don't have arrays or similar structure. The common method I usually use is to implement some Turing Machine using my language. But to do this I need some kind of array to simulate the band.

This kind of encoding is basically what Gödel did in it's theorem of incompletude, find some way to encode logical expressions as integers and then reason on that.

If you give some more elements of syntax, we could even try to do it (if you do not have functions but only gotos, that also will be a problem, but you can also simulate that). The basic problem is that you have to find a way to "compress" your encoded source code. If you have long string constant available it can probably help.

kriss
  • 23,497
  • 17
  • 97
  • 116
  • 1
    Either you need an unlimited program (to print all possible finite strings), or you need to use several prints (that's string concatenation), or you need something that works like an array. And how do they call an array of integer-encoded characters? ;-) – P Shved Apr 11 '10 at 20:35
  • 1
    @PAvel: the OP also said he has basic arithmetics available, hence the n in my above example can be extracted from some larger number. I propose to call a function that print one character (or to simulate one with gotos, basic idea here is to pass in the return point, like when programming using Continuation Passing Style for languages that support it). From this function I can write another that print a string encoded as a large number (or an array). I agree what you do on these numbers is isomorph to string manipulation, but you do not need that supported by strings from the language. – kriss Apr 11 '10 at 21:04
3

If your language is Turing complete and there is one quine, there most likely are infinitely many of them. Here's a way to construct just some of them:

  1. Implement a Brainfuck (or some other simple Turing complete language) interpreter in your language. Write your program such that the source X1<brainfuck source>Y1 when run, interprets the Brainfuck program.
  2. Write an algorithm string f(string a, string b) in any language of your choice that when given any a and b outputs a Brainfuck program that when run outputs the string a, the entire Brainfuck source code, then the string b. You can adapt an existing Brainfuck quine to do this.
  3. Calculate f(X1, Y1) and then embed the resulting Brainfuck program into your program from 1.

Step one is the most difficult, but you might already have done it because one of the easiest ways to prove that something is Turing complete is to implement an interpreter for another language that has already been proven to be Turing complete.

Step two is proven to be possible already and is independent of your program language.

Step three is a simple calculation.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
0

Apparently, a program in your programming language is a string. An output of a quine is a program.

Therefore, an output of a quine is a string. If you don't have any string manipulation it's impossible to write one.

You should either encode your program in numbers (instead of simple humen-readable text encoding) or implement string manipulation.

P Shved
  • 96,026
  • 17
  • 121
  • 165
  • 1
    That's not true; see kriss' answer. Basically, you can simulate string manipulation using string constants and conditional GOTOs that print them. – SLaks Apr 11 '10 at 19:30
  • @SLaks, there is nothing in kriss's answer what contradicts mine. I know that strings are encoded in integers (it's true for any computer nowadays), but implementing this would be implementing "string manipulation". – P Shved Apr 11 '10 at 19:35
  • @Pavel: the OP stated he **has** string constants. That's enough to implement all strings manipulation. Your answer would be accurate if he only had integers or some restricted output. (I wonder if anybody ever tried to implement a Quine in Intercal [http://en.wikipedia.org/wiki/INTERCAL] ... outputs are only numbers encoded as roman numbers). There we would need to consider output is encoded. – kriss Apr 11 '10 at 19:48
  • @kriss, the most important thing to have is not string constants, but (a) print statement; and (b) `string[x] = y`. That would be enough, but that's what they call "string manipulation", isn't it? – P Shved Apr 11 '10 at 20:16
  • @Pavel: ok, you need print statement. But string[x] = y is not necessary, numbers and conditional control flow are enough. I thought it was obvious but apparently it's not. I should edit my answer to give example. – kriss Apr 11 '10 at 20:20
  • @kriss, What can you suggest instead of `string[x]=y`? Using consecutive `print` statements -- which is effectively string concatenation? – P Shved Apr 11 '10 at 20:23
  • @Pavel: working with numbers all the way and using string constants for outputs only. – kriss Apr 11 '10 at 20:29