Talk:Narcissist

A disturbing difference between narcissists and quines

Say you have some total (known to always halt) program P.

Recognizing if P is a quine is decidable:

• Run P.
• Compare P's output to P's source code. If they're equal, P is a quine. If they're not, P is not a quine.

Recognizing if P is a narcissist appears to be undecidable:

• Run P on P.
• If P rejects P, P is not a narcissist.
• If P accepts P, P might be a narcissist, so:
• Run every other string through P. If P rejects them all, P is a narcissist.

Of course, trying every string can't be done in finite time. So unless there is some other way to prove that P rejects all strings except itself, this problem is undecidable.

I dunno - is there? I was going to say, suppose P accepts P but also accepts when its input is a TM that accepts its input (or something equally gnarly.) That would definately make it undecidable. But we know P is total, so it can't contain a TM simulator.

But still, just because we know that P always halts doesn't mean we can know everything that it rejects on (as far as I'm aware...) So I'm leaning toward "undecidable" until I think more about this. --Chris Pressey 02:52, 13 November 2007 (UTC)

It seems to me that what you're doing is using an oracle for the halting problem, and observing correctly that, with such an oracle, the quine-recognition problem is decidable whereas the narcissus-recognition problem is undecidable. I don't think it's surprising that the two problems have different "degrees of unsolvability". --r.e.s. (Talk) 18:49, 13 November 2007 (UTC)

I'm not thinking in terms of using an oracle, I'm just stipulating that someone has already given me a proof that their program P halts. (Think of it as a pair (P, p), where p is a proof that P is total, if you like.) Even if I were phrasing it in terms of oracles, I'm using the same oracle when looking at both programs, so it doesn't make it any less surprising to me that they have different degrees of unsolvability.

At any rate, I did recall something that might help establish the undecidability part. The narcissist could be written as a recursive descent parser; basically, a context-free grammar plus a little "interpreter" for it. This can be shown to always halt (because it depends on consuming its input, which is finite.) But the problem of whether a CFG recognizes all possible strings is undecidable. It might be possible to extend that property slightly somehow, and say that the problem of whether a CFG rejects all strings except a distinguished string is undecidable. But, I haven't worked it out, and there are many decidable properties of CFG's too, so I'm not yet convinced. --Chris Pressey 20:58, 13 November 2007 (UTC)

IIRC the intersection of a CFG language with a regular/FSA language (such as the language of all strings except a given one) is a CFG language, whose grammar can be explicitly calculated, and then the language may be tested for emptiness. So no. --Ørjan 21:43, 13 November 2007 (UTC)

Maybe Ørjan's argument (which I'm unfamiliar with) settles the issue, but one thing that would add to the "surprise factor" is that you would have come up with very nice illustration of Muchnik's theorem. The situation can be described as follows for the two cases ...

quine: φ_n(.) = n

narcissus: \forall m, φ_n(m) = δ_n,m,

... where δ_n,m is Kronecker's delta (1 if n==m, else 0), and the φ's form an acceptable programming system modified by removing all functions that aren't total. It's well-known that no system of always-halting programs can be universal; however, it was proved by Muchnik that there's a Turing degree strictly between 0 (the degree of any recursive set) and 0' (the degree of the Halting set). It would've been neat if an example were your set

{n: \forall m, φ_n(m) = δ_n,m},

since the only ones I've heard of are said to involve a kind of "universality in disguise". I'll be interested in what you manage to discover. --r.e.s. (Talk) 22:47, 13 November 2007 (UTC)

The first narcissist

Perhaps the very first (published) narcissist program ever can be found here: http://bf-hacks.org/hacks/narc.b :) As I mentioned on that other talk page, I completely rewrote it today -- now it's pretty fast and fits in 1827 brainfuck instructions. --Keymaker 14:59, 13 November 2007 (UTC)

Pretty cool! It's only natural that the first one had to be in Brainfuck, I suppose... :) --Chris Pressey 21:05, 13 November 2007 (UTC)

(That link is dead; the program has moved to 73b.org.) —ehird 17:46, 10 March 2012 (UTC), who has an aversion to editing other people's comments

Yes, thanks. This is the annoying thing with website re-namings. --Keymaker 18:07, 10 March 2012 (UTC)

FlogScript

I wrote a narcissist program in FlogScript:

#{#\C|\D.Sx=
}.Sx=

Can you make it shorter? I wonder if there is also one in GolfScript as well. --Zzo38 02:18, 27 April 2008 (UTC)

Very cool, even if I don't understand it. FlogScript seems to be quite dense (don't know any right word), in the sense (or so it seems) one can do programs with low amount of characters. An Underload interpreter in 80 characters (not counting whitespace) -- that is impressive! I'd really like to try out this language, I hope someone explained how it works. --Keymaker 09:58, 27 April 2008 (UTC)

Read Talk:FlogScript to see the answer. --Zzo38 18:54, 2 May 2008 (UTC)