Hi!

test

testing

ping

pinging

@user21820 Pinging myself.

Heh

@lyxal Heheh

@lyxal truly excellent

@lyxal: I guess you already knew about this.

indeed I did

I've done my fair share of same-message and future replies

I once made a recurisve bookmark too

and a two room recursive bookmark

Lol you must be bored.

@user21820 tell me about it

The things I do late at night

@lyxal Have you written a program that outputs the SHA256 hash of its own source code?

no, but I imagine it'd be easy

just an extension of the usual quine

Just an extension?

Well..

I don't know how easy it is for other people..

here's a whole bunch of quines that could be extended

Where I'm from (code golf SE), quines are a dime a dozen

Plain quines (in common languages) are certainly far easier for me; since I don't have to think to write them.

It would be interesting if you have a uniform way of thinking about quines that automatically solves the question I posed.

@user21820 I have now

s='s={};from hashlib import sha256;print(print(sha256(s.format(repr(s)).encode("utf-8")).hexdigest()))';from hashlib import sha256;print(sha256(s.format(repr(s)).encode("utf-8")).hexdigest())

ato.pxeger.com/…

nevermind I left an extra print

s='s={};from hashlib import sha256;print(sha256(s.format(repr(s)).encode("utf-8")).hexdigest())';from hashlib import sha256;print(sha256(s.format(repr(s)).encode("utf-8")).hexdigest())

ato.pxeger.com/…

Well yea. It's just somehow initially more confusing than a regular quine, if you've never seen how such things are done before.

@lyxal: Since that's too easy for you... Let F = ( x , y ↦ ( t ↦ SHA1(x+"$"+y+"$"+t) ) ) and G = ( x , y ↦ ( t ↦ SHA256(x+"$"+y+"$"+t) ) ). Write programs P,Q such that P ≡ F(P,Q) and Q ≡ G(P,Q), where "≡" means "has the same input/output behaviour".

And, uh, no cheating by using the finite output space for SHA hash-functions, in case you happen to think of that. To prevent that loophole we can let F = ( x , y ↦ ( t ↦ t+SHA1(x+"$"+y+"$"+t) ) ) and G = ( x , y ↦ ( t ↦ t+SHA256(x+"$"+y+"$"+t) ) ) instead.

I wouldn't have though of that loophole lol

and that's an exponentially large increase in difficulty

you've gone from the easy end of the spectrum to what is basically impossible to me

@lyxal Really? Strangely enough, there is a mathematical tool that solves standard quines and this one easily, but not the program that prints its own hash...

Do you know about fixed-point combinators?

no

not very much

I've heard about them and have a vague idea of them

but other than that, I don't know how they work

@lyxal It's easy to understand how they work. I can explain the Y combinator to you in one message. Let Y = ( f ↦ ( x ↦ f( t ↦ x(x)(t) ) ) ( x ↦ f( t ↦ x(x)(t) ) ) ). Take any f. Let d = ( x ↦ f( t ↦ x(x)(t) ) ). Then Y(f) = d(d) = f( t ↦ d(d)(t) ). If f is total and does not distinguish behaviourally equivalent inputs, then d is total and d(d) is defined, so f( t ↦ d(d)(t) ) = f(d(d)) and hence Y(f) = f(Y(f)).

Whoops this isn't the version of the Y combinator that is strong enough for our purposes here. Here is the strong version, and it's even simpler to prove: Y = ( f ↦ ( x ↦ ( t ↦ f(x(x))(t) ) ) ( x ↦ ( t ↦ f(x(x))(t) ) ) ). Take any total function f. Let d = ( x ↦ ( t ↦ f(x(x))(t) ) ). Then Y(f) = d(d) = ( t ↦ f(d(d))(t) ) ≡ f(d(d)) = f(Y(f)).

Note the ( t ↦ f(d(d))(t) ) ≡ f(d(d)) in the middle; they are (in general) different programs but they have the same input/output behaviour.

So with the strong version, we can find a program fixed-point of any total function f. In particular, the standard quine is essentially a program f such that U(f) = f, where U is a universal program (e.g. "eval"). And the above puzzle has total functions F,G and asks for P,Q such that P ≡ F(P,Q) and Q ≡ G(P,Q), and one possible solution is to find P,Q such that Q = Y( x ↦ G(P,x) ), in which case P ≡ F( P , Y( x ↦ G(P,x) ) ), which can be solved by using Y.

@lyxal: Let me know if you need further clarification!

That's more than enough

Thanks!

You're welcome!