Du kan prova k\u00f6ra den h\u00e4rifr\u00e5n<\/a>. Vad h\u00e4nder?<\/p>\n Ett program som skriver ut sin egen k\u00e4llkod utan att fuska kallas f\u00f6r en ’quine’. (Som ’fusk’ r\u00e4knas direkt uppl\u00e4sning av programfilen och annat liknande.) Exemplet ovan best\u00e5r av tre delar:<\/p>\n Du kanske t\u00e4nker att quiner \u00e4r unika f\u00f6r Python-spr\u00e5ket, men i sj\u00e4lva verket kan man bevisa f\u00f6ljande sats:<\/p>\n F\u00f6r alla vettiga<\/a> programmeringsspr\u00e5k\u00a0L existerar det \u00e5tminstone ett program P\u2208 L som skriver ut inneh\u00e5llet av P.<\/em><\/p>\n Beviset kan l\u00e4sas h\u00e4r<\/a> f\u00f6r dem som \u00e4r intresserade. I ett n\u00f6tskal listas alla giltiga program Pi<\/sub> upp, vartefter det bevisas att f\u00f6r varje ber\u00e4kningsbar funktion h<\/em> kan man hitta en fixpunkt k<\/em> s\u00e5 att\u00a0Pk<\/sub> och\u00a0Ph(k)<\/sub> \u00e4r identiska. Genom att v\u00e4lja funktionen h<\/em>\u00a0s\u00e5 att Ph(t)<\/sub> skriver ut inneh\u00e5llet av Pt<\/sub> kan man hitta k<\/em> s\u00e5 att programmet Pk<\/sub> skriver ut inneh\u00e5llet av sig sj\u00e4lv.<\/p>\n Utifr\u00e5n detta presenterar jag Waffes ouroborosprogram<\/a> teorem (WOooP teoremet):<\/p>\n Givet vettiga programmeringsspr\u00e5k L1<\/sub>,\u00a0L2<\/sub>, … Ln<\/sub>\u00a0 existerar det ett en serie av program P1<\/sub>\u2208 L1<\/sub>, P2<\/sub> \u2208 L2<\/sub>, … Pn<\/sub>\u2208\u00a0Ln<\/sub> d\u00e4r Pn<\/sub> skriver ut P1<\/sub>, och Pi<\/sub> skriver ut Pi+1<\/sub>.<\/em><\/p>\n Programmen P1<\/sub>, P2<\/sub>, … Pn<\/sub> kallas d\u00e5 f\u00f6r ouroboros<\/a>program, namngett efter den mytologiska ormen som \u00e4ter sin egen svans. B\u00f6rjandes fr\u00e5n Pi<\/sub> f\u00e5r man efter minst n k\u00f6rningar tillbaka det ursprungliga programmet Pi<\/sub>. En quine kan d\u00e5 t\u00e4nkas vara ett ouroborosprogram p\u00e5 bara ett spr\u00e5k.<\/p>\n F\u00f6r att bevisa WOooP r\u00e4cker det med att definiera LC<\/sub> som spr\u00e5kens\u00a0L1<\/sub>, L2<\/sub>, … Ln<\/sub> sammans\u00e4ttning. Man kan sedan anv\u00e4nda f\u00f6rsta satsen f\u00f6r att bevisa att det m\u00e5ste finnas en quine f\u00f6r LC<\/sub>, vilket \u00e4r ouroborosprogrammet vi s\u00f6ker efter.<\/p>\n Som ett test p\u00e5 mitt teorem skrev jag ett hackigt ouroborosprogram fr\u00e5n Python\u00a0till Clojure till R.\u00a0Ta g\u00e4rna och testa f\u00f6r er sj\u00e4lva! Koden finns i min git h\u00e4r: code.py<\/a>.<\/p>\n Alla tre spr\u00e5ken har online terminaler<\/a>, s\u00e5 inget beh\u00f6ver installeras f\u00f6r att testa koden.<\/p>\n P.S. H\u00e4r \u00e4r ett lite l\u00e4ngre\u00a0ouroborosprogram p\u00e5 128 spr\u00e5k<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":" Betrakta Python-koden nedan. s = ’s = %r\\nprint(s%%s) #Hello’ print(s%s) #Hello Du kan prova k\u00f6ra den h\u00e4rifr\u00e5n. Vad h\u00e4nder? Ett program som skriver ut sin egen k\u00e4llkod utan att fuska kallas f\u00f6r en ’quine’. (Som ’fusk’ r\u00e4knas direkt uppl\u00e4sning av programfilen och annat liknande.) Exemplet ovan best\u00e5r av tre delar: Kod som data. Str\u00e4ngen\u00a0’s = … Forts\u00e4tt l\u00e4sa PyClojuR: En kod ouroboros<\/span> \n
![\"\"](\"http:\/\/spektrum.fi\/spektraklet\/wp-content\/uploads\/2018\/10\/cropped-ouroboros512.png\")
<\/a><\/p>\n