John Tromp does it for Binary Lambda Calculus here: http://homepages.cwi.nl/~tromp/cl/cl.html On Sat, Nov 14, 2009 at 6:00 AM, victor miller <victorsmiller@gmail.com> wrote:
Greg Chaitin does this in his book "Algorithmic Information Theory" http://www.umcs.maine.edu/~chaitin/cup.pdf using a version of pure LISP.
Victor
On Sat, Nov 14, 2009 at 8:23 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I would like to nominate Goedel as the world champion of obfuscated code, with Matiyasevich (of Hilbert's Tenth Problem fame) as the runner-up. I think that we can safely retire both their player numbers.
BTW, has anyone actually gone through all the gory details of implementing Goedel's programming style?
There was a good Scientific American article on Hilbert's Tenth Problem that gave actual numbers for real encodings.
At 08:48 PM 11/13/2009, rwg@sdf.lonestar.org wrote:
I entered the obfuscated C contest one year with a program that computed a prime sieve in an incredibly slow and non-intuitive manner. I don't think anyone ever figured out what it did ---- it was so slow and ugly that no one would look at it.
Hilarie
____________________________________________Ah, an obbortunity to refustigate with this Mathematica malpractice:
OddPrimeQ[n_]:= Block[{$RecursionLimit=Infinity},n+1==Odd4[(n-1)/2,0,4]]
Odd4[n_,t_,k_]:=If[k==0,KroneckerDelta[0,n], If[t>n,0,Odd4[n-t,0,k-1]+Odd4[n,1/2+t+Sqrt[2*t+1/4],k]]]
Absolutely useless hint:
OddPrimeQ[n_]:= Block[{$RecursionLimit=Infinity},n^3+1==Odd4[n-1,0,8]]
gets the same answers, only more slowly.
The only Funster to come close to explaining this was Joshua Zucker, who stopped short of totally cooking it, but correctly indicated the final steps. (Marc LeBrun is disqualified--he helped misbeget it.) --rwg For a modicum of speed: Odd4[n_,t_,k_]:=Odd4[n,t,k]= If[k==0,KroneckerDelta[0,n], If[t>n,0,Odd4[n-t,0,k-1]+Odd4[n,1/2+t+Sqrt[2*t+1/4],k]]]
I don't know whether
OddPrimeQ[n_]:=Block[{$RecursionLimit=Infinity}, (Odd4[(n-1)/2,0,4]-1)^3==Odd4[n-1,0,8]-1]
can give a false positive. It's too slow to test beyond a few thousand. But I see how, with Macsyma, to test its conjecture out to a few million.
DAZ> it was a *positive* "No".
As opposed to a positive, definite "No".
DDyer>I've had waxy paper ... burst into flames while the tamale was still cold.
Isn't "cold tamale" an oxymoron?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com