User talk:Smjg

Quines

About your quine counterexample, I think the loophole you found is because the kind of formulation you quote

As a consequence of the fixed-point theorem, it is possible to write a quine in any Turing-complete programming language that is capable of outputting an arbitrary string by a computable function of the string.

erroneously takes the string as the starting point, rather than the computable function. Here is a formulation that I think lacks the loophole (but I might have ignored other details):

Let there be a Turing computable function f which for every Turing computable function g calculates a program f(g) in a programming language, such that g and f(g) have the same output. Then the programming language has a quine.

Now let g be a function such that its first character output is undecidable! With your counterexample, you will be hard pressed to make the function f terminate and deliver the final program for all such g.

--Ørjan 17:08, 15 Oct 2006 (UTC)

You might want to take a look at David Madore's quine page if you haven't already. It has a somewhat technical proof of the fixed point theorem. (Just don't believe him when he mixes the Church-Turing thesis with the universality theorem.) --Ørjan 17:17, 15 Oct 2006 (UTC)

Yes, I'd seen that before, albeit at the old eleves.ens.fr address. The beginning statement was my attempt at recalling the words of the statement. Indeed, David's page does say:

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.

True, it isn't clear what is meant by "by a computable function of the string as program". My guess is that it's using "function of" when it actually means "function that generates". Otherwise, it would seem that by "computable function of the string" it would mean the quine; in other words, it's basically saying "any language that has a quine has a quine".

But my understanding of what people say is to the effect that if the language is Turing complete and able to output an arbitrary string, then the language has a quine. This is the statement that my essay aims to disprove. (The "able to output an arbitrary string" bit is important - the original INTERCAL is a prime counterexample here.)

To look at your formulation, I'm a little puzzled. How would the first output character of a Turing-computable function be undecidable if no input precedes the first output? -- Smjg 19:03, 15 Oct 2006 (UTC)

Here's a quick counterexample to the TC-quine claim; suppose I have an esoteric programming language defined as follows:

• If the first character of the program is a double-quote, all characters from the second onwards are printed.
• If the program is of length zero, an error message is printed (this idea, borrowed from Homespring, prevents a null quine)
• Otherwise, the program is treated as an Iota program an interpreted.

Iota is Turing-complete, so this language must be too (as no Iota program starts with a double-quote), and it's definitely capable of arbitrary output. On the other hand, a quine is obviously impossible. (The HQ9+ method is pretty good at disproving all sorts of claims; for instance, you can construct a non-TC language that calculates the Ackermann function much the same way.) --ais523 14:51, 16 Oct 2006 (UTC)

Hmmm, that's a nice example. :) However, it seems the language is unquinable only if the output is limited to something like this (like printing all the program code if the first character is something), or making the program output something all the time (like for example Choon, which outputs something all the time).. But if the language is Turing-complete and has a way to print for example a cell's content or just whatever character, it should be able to print its source. Anyways, this example is interesting, as the program can output anything, for example "hello", yet it's still not the same thing than for example making a program in brainfuck to print "hello" -- although there's something similar in them, as neither takes any user input, only the output commands/instructions are different. --Keymaker 16:35, 16 Oct 2006 (UTC)

So either it prints a pre-determined string, or it prints nothing (because Iota has no IO)? A clever circumvention. Maybe we should add a further requirement, that the language must be able to output the result of an arbitrary Turing computation. Hang on, that won't do. Try replacing "Iota" with "INTERCAL-72" in your spec and you'll see. I guess the real claim is: It is possible to write a quine in any language that can output an arbitrary string generated by a Turing-computable function of the input. This indeed describes the family of languages that my disproof is aimed towards. However, the formulation excludes languages that have no input support. What do you think? -- Smjg 21:24, 16 Oct 2006 (UTC)

Another trivial counterexample: the first letter of any program must be a and all programs start by outputting a b. You'll need to add 'without outputting anything else' to the end of the claim. --ais523 08:06, 17 Oct 2006 (UTC)

After having a look at Wikipedia:Kleene's recursion theorem (the fixed point theorem in question) I am starting to think that most of the problem with your "counterexamples" is with the requirement for Turing-completeness. The theorem requires that one has a Gõdel numbering of all computable functions, which translated to normal programming terms means: your programming language must include programs for all Turing-computable functions from input to output.

What the requirement "can output anything" really means is that our programming language is complete with respect to Turing machines with output, perhaps as opposed to the often used simplification of Turing machines which just accept/reject the input. --Ørjan 08:22, 18 Oct 2006 (UTC)

You've just given me the best formulation so far of the set of applicable languages. The only thing it doesn't cover is programmer control over the sequence of input operations and output operations, but this doesn't really matter as the difference that my method produces applies only before any input has happened. And so if the original language contains all Turing-computable functions from input to output, then so does the quineless derivative. -- Smjg 19:34, 18 Oct 2006 (UTC)

I simplified too much again, so let me add that the correspondence from Turing machine programs (or equivalently, whatever "ordinary" Turing-complete language you start with) to the program in your derived language that does the same thing must itself be computable.

With this taken care of, consider the following informal program (you can translate it to any ordinary programming language):

If there is an even integer > 2 that is not the sum of two primes, then take the first such, sum its digits modulo the size of your character set, then output the resulting character.

Otherwise, loop forever.

This is based on the famous unsolved problem, the Goldbach conjecture. I think you will be unable to find a program in your quineless derivative that you can be sure does the same thing. (You can of course find two programs such that one of them does it, but that is not enough - because you need a computable correspondence.) Even if you managed to solve the Goldbach conjecture, it should be possible to use the proof of Kleene's recursion theorem to turn whatever correspondence you choose into an example it doesn't work for. --Ørjan 07:17, 19 Oct 2006 (UTC)

Well pointed out. I think that, together, we've cracked it now. So the application of Kleene's recursion theorem relies on the assumption that there is a Turing-computable function E that maps all Turing-computable input-to-output functions to programs in the language of choice. So while the quineless derivative still has a program for every Turing-computable function mapping input to output, E can no longer be a Turing-computable function. Yet the language itself is still, in theory at least, as powerful as the original. -- Smjg 00:11, 20 Oct 2006 (UTC)

Yes. The new language is still Turing-complete if we allow the use of a different coding of output - say by prepending output with a fixed string. Such codings of results are obviously necessary for Turing-complete formalisms without string output, such as combinatory calculus (just look at the I/O of Lazy K). But when considering what counts as a quine, we fix the output coding at the outset so we don't have this flexibility. --Ørjan 05:32, 20 Oct 2006 (UTC)

I have now updated my Constructing a Quineless Language page to cover the points that have been discussed. -- Smjg 19:08, 6 Nov 2006 (UTC)

My 2 cents on Quineless Language

I have a couple of thoughts on the Quineless Language, most of which I've already e-mailed to Smjg, but I'll try to relate them here too. (Sorry if it's a bit long.)

Given that Turing-complete means (very roughly) "can do anything a Turing machine can do," the exact definition of Turing machine becomes important, and there are several definitions floating out there. If you use the "language recognizer" version, which has no output except for "accept" and "reject" states, then a Quineless Language is Turing-complete as long as it has at least 3 symbols in its output alphabet (call the first symbol "accept", the second symbol "reject", and require that all quines must start with the third symbol.)

But I find this unsatisfying, and I think a more reasonable definition of Turing machine, when dealing with quines, is one that has an output tape (over the same alphabet as the input/work tape) and a "program tape", or at least, some explicit way to specify a finite control with a string over the same alphabet as the output tape. This is so that such a Turing machine can produce another Turing machine as output.

Then the question of Turing-completeness of a Quineless Language becomes interesting. Although, there still seems to be an extremely simple argument that it's not Turing-complete, and it doesn't have to invoke a fixpoint theorem: a Turing machine (as I've just defined it) has quines. A Quineless Language doesn't. Therefore a Quineless Language isn't Turing complete. (Of course, I would need to actually exhibit a quine for the Turing machine to make this a good argument, but I'm pretty confident that can be done given the body of work on quines...)

Let me propose a stronger version of Quineless Language to answer Ørjan's objection. Let the interpreter for such a language allow output of all symbols in the program except the last. If the program attempts to output the last symbol of the program after all the other symbols, i.e. if it attempts to produce a verbatim copy of the program, hold this last symbol in a buffer. If some further symbol is output, output both symbols; if the program halts first, just discard it. This Quineless Language disallows all quines, but allows every other string to be output.

Now, it doesn't much matter if the program outputs symbols on conditions that are undecidable or even random; if such a sequence happens for any reason to produce a copy of the program on the output, it's disallowed and doesn't happen. If it produces any other sequence, it's allowed.

The reason I find the idea of a Quineless Language interesting is that it defines a computational class that is extremely powerful (in terms of the number of programs that can be written, not just the number of languages that can be recognized) yet still not Turing-complete. It seems to be able to do everything except quine. If there are (relatively non-contrived) sub-Turing-complete classes that are more powerful, I'm not aware of them. --Chris Pressey 19:23, 18 June 2007 (UTC)

An interesting discussion. The concept would indeed work just as well if it were defined, rather than to avoid first outputting the first character of the program, to allow the output to be any string other than the program. Even the talk about unsolved mathematical problems would apply here as well - you could bijectively map the even positive integers to strings, not knowing whether the first counter-example to Goldbach's conjecture maps to the string that is the program code.

But quines are relative to the programming language. Programs in general usually aren't. Your argument on a Turing machine as you describe having quines may be valid, but I'm not sure that you can say a quineless language isn't Turing complete on this basis. If the language on which you base your QL is capable of outputting a particular string, then so is the QL. The difference is whether the program code can possibly coincide with the string that is output - but that doesn't make any difference to the fact that a program exists that can output that string.

But maybe depending on how you define it, there's another computational class out there.... -- Smjg 01:30, 19 June 2007 (UTC)

Well, 2 small developments. One is that I'm no longer sure (as I think I suggested above) that you don't have to invoke the fixed-point theorem, in order to show that a Turing-complete language (where the program and the output are both strings over the same alphabet) necessarily has quines. You might need to (in the sense that, if you try to prove it any other way, it turns out to be equivalent to using the fixed-point theorem.)

The other development is that, while thinking about this, I came up with the idea of a narcissist, the decision-problem version of a quine. But since I am so unpracticed at writing quines, I haven't even tried to write a narcissist yet. Any takers? --Chris Pressey 19:28, 12 November 2007 (UTC)

I'm on it. But it'll take at least half a day more as it's middle of middle of night locally and I'll have to sleep and I realized one flaw in my input routine (damn empty strings), and to get the data part considerably smaller (currently about 18k) I'm probably optimizing that as well, so it won't be as crude as the current version. Basically that means rewriting the whole thing. By the way, this is interesting idea, partly like the type of program I've thought of, quinterpreter. I might just as well add that to esowiki as well. --Keymaker 01:18, 13 November 2007 (UTC)

Seems I won't write that page right now, afterall, there's something I'll have to think a bit more, but basically the idea of the quinterpreter is that it's a self-interpreter for the language its written in, but it receives no input, and thus needs to have the nature of a quine. The interpreted part will interpret itself -- or perhaps itself and the outer part too, that is what I haven't decided yet... --Keymaker 01:32, 13 November 2007 (UTC)

It isn't that difficult to turn a quine (in a suitable language) into a narcissist. You basically need to change the output statements to write to an internal buffer, and then compare the input with this. I've written one in D, which basically works in this way. I'll publish it soon and see what else I can do. Of course, the classic BASIC cheat quine isn't going to be easy to convert.... -- Smjg 02:02, 13 November 2007 (UTC)

Well, yes, it's easy if the language is suitable... :] Anyways, I've now finished the one I started yesterday in brainfuck (and thus the result is in brainfuck as well), I linked it on the Talk:Narcissist page. --Keymaker 15:05, 13 November 2007 (UTC)

Smjg, I think I *finally* see what you're getting at with the quineless language idea!

Say a programming language is Turing-complete if there is a homomorphism between Turing machines and that language. That is, we have some semantics-preserving function that takes Turing machines to programs. Or, to put it another way, we have a compiler that inputs a TM description and outputs code in this programming language, and our compiler has been proven correct. I think this is a reasonable definition, even when the Turing machine is defined to produce output of some kind...

Now, what you're saying (I think) is that you can define a homomorphism that always takes a Turing machine to some program that is not a quine. Or, to put it another way, you can write a compiler that always avoids generating output code that outputs itself.

Presumably the compiler does this by checking if the output code does output itself, and if so, modifying it slightly (just add NOPs at the beginning of the output code, or whatever.)

I'm worried that maybe the compiler would have to deal with the Halting Problem here. To check if the output code does output itself, it has to run it. Might it never terminate? In the general case this is a possibility, but, if your homomorphism/compiler is defined as a slight modification of an existing homomorphism that you know is total (always halts,) then, you can probably extend that property to your quine-avoiding compiler, if you define it carefully.

At any rate, wow. My head is spinning! --Chris Pressey 02:34, 13 November 2007 (UTC)

You're almost there. "That is, we have some semantics-preserving function that takes Turing machines to programs." That's more or less how I'd define it. The problem is your next sentence: "Or, to put it another way, we have a compiler that inputs a TM description and outputs code in this programming language, and our compiler has been proven correct." This requires that the function mapping TMs to programs not only exists, but also is itself Turing-computable. Consequently I believe that, for a quineless language as I've defined it (or by the variation you proposed), the function mapping TMs to programs will not be Turing-computable. However, this function still exists in principle, and therefore by my interpretation, the language is still Turing complete.

But your idea of a narcissist brings along new challenges. I'll have a think about it sometime.... -- Smjg 13:54, 13 November 2007 (UTC)

I think I'm pretty much there now... your suggestion that this mapping function is not Turing-computable is the same as my worry that the compiler that implements it has to overcome the HP somehow when it generates its quine-avoiding output code. (You know, I'm not actually convinced that the homomorphism isn't computable, but then, I haven't been thinking about it as long as you have.) As for the function still existing in principle... yes, OK, but then that possibly means that the language is only Turing-complete in principle - whatever, exactly, that means. (I get the feeling that when you start using noncomputable homomorphisms for reductions, things get ugly.) I'll have to ponder it. --Chris Pressey 21:14, 13 November 2007 (UTC)

Quineless languages -- another view

Note: The external link on your user-page is dead, but I managed to google a cached copy of your "Constructing a Quineless Language". There you (Smjg) write ...

"Take any programming language satisfying the supposedly sufficient criteria. Then modify it so that, until an input or output operation has actually been executed, any instruction to output a character equal to the first character of the program code is ignored. Of course, if this character is output as the first character of a string or number, then the same rule applies."

The following seems more straighforward: Take a Turing-complete language, say Python (assuming unbounded storage), and (1) add the requirement that the first character of a valid program must be, say, a space-character, and (2) strip the language of all output capability except the following "dequining print" function:

def DequiningPrint(s):
     #remove any initial blanks from s
     while s[0]==' ':
          s = s[1:] 
     print s
     return

The resulting language is still universal, but there are no quines in it (or am I missing something?). Since quines would exist if Kleene's fixed-point theorem held, and that theorem holds for any so-called acceptable programming system (APS), the conclusion is that this quineless language doesn't produce an APS. (Furthermore, since the programming system is still universal, its failing to be an APS must be due to not satisfying the s-m-n theorem, as s-m-n & universality are all that's needed for an APS.) --r.e.s. (Talk) 02:28, 14 November 2007 (UTC) [EDIT: extensive rewording for clarity] --r.e.s. (Talk) 11:48, 14 November 2007 (UTC)

EDIT: Strike the above line of mistaken reasoning — A "literal" quine (a program that takes no input, and literally outputs its own source code) is not guaranteed by Kleene's F.P. theorem, because that theorem implies the existence only of "quine-functions", f_n()=n, among the functions computable in the language, but these generally depend on an arbitrary i/o coding scheme, unlike literal quines — so it doesn't guarantee existence of the literal type of quine. IOW, literal quines can be prevented by trivially modifying the language without losing Turing-completeness nor preventing quine-functions in a different (non-literal) coding scheme. --r.e.s. (Talk) 01:04, 15 November 2007 (UTC)

That language doesn't meet even the most basic prerequisite for a quine: ability to output a program in itself. The original INTERCAL is another example of this.

As for your opening comment, Portland seems to have been on holiday for the last however long. WWWEP now has a new home. I'm in the process of updating the links. -- Smjg 23:56, 14 November 2007 (UTC)

I'm glad we agree on that first point :). But maybe I've misunderstood your overall motivation for modifying a language to make it "quineless". Scratch that -- I forgot that your purpose was to give a counterexample to someone's claim. --r.e.s. (Talk) 01:04, 15 November 2007 (UTC)

Quineless Language Quest Redux

It's been a while, but: there may, in fact, be quineless "languages", although you may need to stretch the definition of "language" somewhat. I just found out about this: http://www.jstor.org/discover/10.2307/2964290?uid=3738032&uid=2&uid=4&sid=21101408663091 The "Friedberg numbering" in "III. Enumeration without Duplication" apparently (I don't have access to the fulltext so I can't confirm this) maps every computable function to a unique code -- which fails to be an "acceptable programming system" -- which in turn fails to support the F.P. theorem -- which in turn means it can't have quines. But it would still be TC, if it maps all the computable functions. However, as I said, the description of this mapping as a useful "language" is not beyond critique; for example, I don't know if it's possible to easily find a particular code for a particular purpose. But I thought I'd mention it here as a possible lead. I may write more about it here if I manage to learn more about in the future. Chris Pressey (talk) 00:22, 24 November 2012 (UTC)

Trying to expand on this:

Replace "possible to easily find a particular code..." with "computable". I don't know if Friedberg numbering is computable. If it's not, well. I lost interest in this the first time around because Smjg seemed content with there being a quineless language in principle, and there are a lot of wild languages in principle, like a language which rejects all non-halting programs. If Friedberg numbering isn't computable then this is still just quineless in principle.

I'm not sure I totally appreciate what it means to be an "acceptable programming system" but it seems to capture at least one notion we've identified as important: the language must be able to work with the same kinds of values that programs are expressed as. But it doesn't necessarily involve output; you can write a "quine" that sets a local variable to the contents of the program instead. (It also requires it be possible to write an eval, but that's a property of any TC language.)

I don't know if failing to support the FP theorem actually prevents you having quines, or whether it simply fails to require that you have quines.

I'll have to re-read this talk page at some point. Maybe it can be digested into an article. Chris Pressey (talk) 12:13, 24 November 2012 (UTC)

The general problem of determining whether two algorithms compute the same function is undecidable, since it relies on the halting problem. So it seems to me that Friedberg numbering is uncomputable. And what do you mean exactly, when you say "support" the FP theorem? — Smjg (talk) 17:23, 31 December 2012 (UTC)

Reply to what you wrote on Graue's talkpage

Keymaker's deleted the junk pages, and I've blocked the spambot; cleaning up after spambots is the main job that we do as our capacity as Esolang administrators. If you come across a junk page or spambot edit, it can help to blank the page/revert the edit with an edit summary note that administrator help is needed, although we're likely to notice the spambot anyway. Thanks for helping! --ais523 21:00, 16 April 2008 (UTC)

Re: Spam

My guess is that either User:Graue (who's the bureaucrat (= above admin in user rank) and owns the server), or someone at the hosting company he uses, added a new spam filter that caused trouble with the spam page in question. --ais523 13:36, 9 July 2009 (UTC)

And with respect to the pages you wanted protection of, I'm not convinced protecting either is a good idea. The Main Page spammers wouldn't be blocked by semiprotection based on the pattern they're working on, and they're not that heavy compared to other spammers, so it's probably better just to revert. As for the language list, it's important that people contributing new languages, even anons, can post there. The language list spammers are using IPs for which the range can be easily determined, so I can actually aim blocks at them, and just have done so. So leaving the page unprotected is actually making it easier for me to stop spam; if the page were semiprotected, I wouldn't be able to discover the spammer's IPs. --ais523 19:07, 27 January 2012 (UTC)