Page namespace (page_namespace) | 0 |
Page title (without namespace) (page_title) | 'Seed' |
Full page title (page_prefixedtitle) | 'Seed' |
Old content model (old_content_model) | 'wikitext' |
New content model (new_content_model) | 'wikitext' |
Old page wikitext, before the edit (old_wikitext) | 'Seed is a language based on random seeds. Actually, programs only contain two instructions: length and random seed, separated by a space. To execute a Seed program, the seed is fed into a [http://en.wikipedia.org/wiki/Mersenne_twister Mersenne Twister random number generator], and the randomness obtained is converted into a string of ''length'' bytes, which will be executed by a Befunge-98 interpreter (or compiler).
The random characters generated are ASCII values 32 to 126 plus line feed (ASCII 10). An example Seed program might look like this:
780 983247832
This will generate a [[Befunge]] program 780 characters long that looks like this:
<nowiki>
q
Z?T7yQ
;RyHIw*#{8).'}iN*P{u>z#ok<w\\?!KPrVO7U;b> B
f:rDj':T3'O~J(>BLLxj(>{5n) oM/?nwC{c(OT>Fv?=)tW*`6oL8yCI:D_%4d}:ubmL"6v'(o4^5zi{E3F+vDHk"*}a&nu=S*syIgT>MQ9_vyi'b&i^_xT"WP-"lk=#/r)8%:rG,I?'DTz<)|J]0|^LDakzrx]Gjy=^.0$R<y9#Sl,_K5y@\~z+jSlARiA6D#:gVlmb^>[MQea
(etc)
</nowiki>
==Computational class==
Since standard Befunge is considered to be a finite state machine, it is, strictly speaking, not Turing-complete; thus, Seed cannot be Turing-complete either. However, the actual computational class of Befunge is currently unknown.
The Mersenne Twister has a period of 2<sup>19937</sup> - 1. That means that it is not possible to generate every possible Befunge program, which means it may not be Turing-complete, but if at least one Seed generated a program that could for example interpret a bounded version of Brainfuck, then it would mean that it certainly is. If somebody figures it out, please add it here.
==Running programs==
Here is the Python 3.0 script that converts seed programs to Befunge. A Befunge interpreter could be put in the same script, but I decided to Keep It Simple:
import random
program="780 983247832" ##Place program here
program=program.split()
length=int(program[0])
random.seed(int(program[1]))
chars="".join(map(chr,range(32,127)))+'\n'
prog="".join([chars[int(random.random()*96)] for i in range(length)])
print("Your program:\n----------------------------------------\n", prog, "\n----------------------------------------\n")
This script was tested in two different computers to make sure it produces the same results. Other implementations MUST do so.
==Writing programs==
Writing programs in Seed is easy (once you have the befunge program required), but requires enormous processing power: a Befunge program n bytes long has 96^n possibilities. Here is a script that brute-forces a seed program. It could be rewritten in C or optimized in some way, but it'd still not be useful beyond 6 characters.
<pre>import random,time
endprog='"hi",' #Place program here
triespersec=100000 #approximate number of tries per second (to calculate time needed)
seed=0 #Starting seed. Modify if running multiple in parallel
chars=''.join(map(chr,range(32,127)))+'\n'
length=len(endprog)
p=96**length
seconds=p/triespersec
prog,n='',0
print("Program length is {0} characters.\n95^{0}={1} possibilities.".format(length,p))
if seconds > 86400:
print("Estimated time: {0} days, {1} hours".format(int(seconds/86400),int(seconds%86400/3600)))
elif seconds > 3600:
print("Estimated time:{0} hours {1} minutes".format(int(seconds/3600),int(seconds%3600/60)))
elif seconds > 60:
print("Estimated time:{0} minutes {1} seconds".format(int(seconds/60),int(seconds%60)))
else:
print("Estimated time:{0} seconds".format(seconds))
print("Brute-forcing seed...")
seconds=time.clock()
while prog != endprog:
n+=1
random.seed(seed)
prog = ''
for t in range(1,length+1):
prog += chars[int(random.random()*96)]
if endprog[:t] != prog:
seed += 1
break
seconds=time.clock()-seconds
print('Found seed for "{0}"!\nSeed program:\n{1} {2}'.format(prog,length,seed))
print("Time elapsed: {0} seconds. Tries per second:{1}".format(seconds,int(n/seconds)))</pre>
==Examples==
These examples were found with the above script.
Hello, world (Actually just prints "h"):
4 80814037
True hello world (Created by PPCG user [https://codegolf.stackexchange.com/users/30688/feersum feersum] for [http://codegolf.stackexchange.com/a/97842/53745 this answer]):
20 854872453003476740699221564322673731945828554947586276010721089172712854441839676581917455319274850944955030258951339804246125714958815519550291630078076933441706558540342671975808828643360922071900333028778314875248417953197990571991784126564752005357199892690656368640420204822142316716413192024742766282266114842280731756458212469988291309261528542889299297601723286769284159107438930448971911102280330101196758384815655479640836157495863547199726234352265518586460633795171196315255736880028338460236768181141732764911402112878175632130129852788301009582463631290071329795384336617491655825493435803011947670180368458659271192428341035912236946048939139042310380278430049252171822721598175984923434205610723412240162418996808671543770639111617709604242882388664919702606792443015941265168129550718541372361144081848761690730764968771245566074501485020726368378675085908872608679630368472956274468410052703615106090238423979678950131481176272880569100533049143775921798055136871254424261001442543122666701145111965968366507060931708140304772342855064834334129143038575569044150428480231956133612367393837580345180691911525531699573096952433882387811884727975431823620782822755161559988205401134640722220804177812794328129589949692446031008866917615922944976151073653201316255518389496411696741029209242119521978920200314572718584995265523235225587228975886710511855501710470163649632761488899317729943053884132314641377747687975638119132094777769497069556255954031537245957811105217875011509899497752696062748928963281605780942517262774976217663461063680912331030221981433051827519906741285738915397005702326447635845195923640649166530310494885569783989508000344280715868581532826832242144647203531393142251025361866506821695860883605004105862208004440476654027574832078603305884731766236740069411566854496824754558761536201352147934963241039597221404341132342297870517293237489233057335406510464277610336142382379135365550299895416613763920950687921780736585299310706573253951966294045814905727514141733220565108490291792987304210662448111170752411153136765318541264632854767660676223663544921028492602135525959428999005153729028491208277493747933069008199074925710651071766675870081314909460661981433426167330215548196538791617762566403934129026219366764038390123622134753742930729751695349588862441999672547791630729398908283091638866715502470152431589429837867944760012419885615525232399584379209285060418518373512154801760060312646951597932345591416241634668119867158079946680321131213357200382937049485606706114467095019612014749723443159443363662563254359712162432143334612180576945072905749883870150120687696027984317320305291407322779803583395375616762530641605634303022155218169343410634115050596030685041633824154135240376022159918501703555881290333205131375705406831260759974112248490451605422031345264183102048614606636275942039438138959188478277971377232005036301145411215067576576667743288951344423152531417111852584846747428443123174595987315325304540564683047858415059703724263652136185848573853965992798725654430360647040362341567082462847275277303225817689141675391972818943419663764371222973269129542760661385278009266471167618553065823580448848795731295589715602705860758954890415040763604082216728159486423396295188510311881004469017351709060492844398219491990895826924575575549615118821417543037296628825303328056839433114519945243963946989899508355224823109677424196639930153649890175062456649384605721510239142861693109687536600667811037619175927995599388547421689316110236566026931360164495251160997857372500940728057700473763884480342708897319990346726967220426504612260565552531158509215849649565188655100774748485416791517853427613458459889062942881409801879085054494129489535044719193283409051007851153504224002807392992520076910314763705776345053922387355156981872691537772657428096384535960466923475731297217863371650154415835785630016335858514130863258775100537612371430357576913148500310344278511588325852376442503898849856566716198848377379400158332792027967216204970114516984638014129252882482309132898416484525230488700253065644547798869056136044415413099076332059572505138116227535024546891015836838323022822272664771489129085797354578016574544759934333471793
Infinite cat:
2 20093
Do nothing and exit:
1 186
Do nothing and exit (multi-line):
3 599084
[[Category:Unknown computational class]]
[[Category:Zero-dimensional]]
[[Category:Languages]]' |
New page wikitext, after the edit (new_wikitext) | 'Seed is a language based on random seeds. Actually, programs only contain two instructions: length and random seed, separated by a space. To execute a Seed program, the seed is fed into a [http://en.wikipedia.org/wiki/Mersenne_twister Mersenne Twister random number generator], and the randomness obtained is converted into a string of ''length'' bytes, which will be executed by a Befunge-98 interpreter (or compiler).
The random characters generated are ASCII values 32 to 126 plus line feed (ASCII 10). An example Seed program might look like this:
780 983247832
This will generate a [[Befunge]] program 780 characters long that looks like this:
<nowiki>
q
Z?T7yQ
;RyHIw*#{8).'}iN*P{u>z#ok<w\\?!KPrVO7U;b> B
f:rDj':T3'O~J(>BLLxj(>{5n) oM/?nwC{c(OT>Fv?=)tW*`6oL8yCI:D_%4d}:ubmL"6v'(o4^5zi{E3F+vDHk"*}a&nu=S*syIgT>MQ9_vyi'b&i^_xT"WP-"lk=#/r)8%:rG,I?'DTz<)|J]0|^LDakzrx]Gjy=^.0$R<y9#Sl,_K5y@\~z+jSlARiA6D#:gVlmb^>[MQea
(etc)
</nowiki>
==Computational class==
Since standard Befunge-98 is Turing-complete, Seed '''can''' be Turing-complete.
The Mersenne Twister has a period of 2<sup>19937</sup> - 1. That means that it is not possible to generate every possible Befunge program, which means it may not be Turing-complete, but it was proven that Seed is Turing-complete<ref>https://krzysztofszewczyk.github.io/MerseneTuringCompletness/SeedProof.pdf</ref>.
==Running programs==
Here is the Python 3.0 script that converts seed programs to Befunge. A Befunge interpreter could be put in the same script, but I decided to Keep It Simple:
import random
program="780 983247832" ##Place program here
program=program.split()
length=int(program[0])
random.seed(int(program[1]))
chars="".join(map(chr,range(32,127)))+'\n'
prog="".join([chars[int(random.random()*96)] for i in range(length)])
print("Your program:\n----------------------------------------\n", prog, "\n----------------------------------------\n")
This script was tested in two different computers to make sure it produces the same results. Other implementations MUST do so.
==Writing programs==
Writing programs in Seed is easy (once you have the befunge program required), but requires enormous processing power: a Befunge program n bytes long has 96^n possibilities. Here is a script that brute-forces a seed program. It could be rewritten in C or optimized in some way, but it'd still not be useful beyond 6 characters.
<pre>import random,time
endprog='"hi",' #Place program here
triespersec=100000 #approximate number of tries per second (to calculate time needed)
seed=0 #Starting seed. Modify if running multiple in parallel
chars=''.join(map(chr,range(32,127)))+'\n'
length=len(endprog)
p=96**length
seconds=p/triespersec
prog,n='',0
print("Program length is {0} characters.\n95^{0}={1} possibilities.".format(length,p))
if seconds > 86400:
print("Estimated time: {0} days, {1} hours".format(int(seconds/86400),int(seconds%86400/3600)))
elif seconds > 3600:
print("Estimated time:{0} hours {1} minutes".format(int(seconds/3600),int(seconds%3600/60)))
elif seconds > 60:
print("Estimated time:{0} minutes {1} seconds".format(int(seconds/60),int(seconds%60)))
else:
print("Estimated time:{0} seconds".format(seconds))
print("Brute-forcing seed...")
seconds=time.clock()
while prog != endprog:
n+=1
random.seed(seed)
prog = ''
for t in range(1,length+1):
prog += chars[int(random.random()*96)]
if endprog[:t] != prog:
seed += 1
break
seconds=time.clock()-seconds
print('Found seed for "{0}"!\nSeed program:\n{1} {2}'.format(prog,length,seed))
print("Time elapsed: {0} seconds. Tries per second:{1}".format(seconds,int(n/seconds)))</pre>
==Examples==
These examples were found with the above script.
Hello, world (Actually just prints "h"):
4 80814037
True hello world (Created by PPCG user [https://codegolf.stackexchange.com/users/30688/feersum feersum] for [http://codegolf.stackexchange.com/a/97842/53745 this answer]):
20 854872453003476740699221564322673731945828554947586276010721089172712854441839676581917455319274850944955030258951339804246125714958815519550291630078076933441706558540342671975808828643360922071900333028778314875248417953197990571991784126564752005357199892690656368640420204822142316716413192024742766282266114842280731756458212469988291309261528542889299297601723286769284159107438930448971911102280330101196758384815655479640836157495863547199726234352265518586460633795171196315255736880028338460236768181141732764911402112878175632130129852788301009582463631290071329795384336617491655825493435803011947670180368458659271192428341035912236946048939139042310380278430049252171822721598175984923434205610723412240162418996808671543770639111617709604242882388664919702606792443015941265168129550718541372361144081848761690730764968771245566074501485020726368378675085908872608679630368472956274468410052703615106090238423979678950131481176272880569100533049143775921798055136871254424261001442543122666701145111965968366507060931708140304772342855064834334129143038575569044150428480231956133612367393837580345180691911525531699573096952433882387811884727975431823620782822755161559988205401134640722220804177812794328129589949692446031008866917615922944976151073653201316255518389496411696741029209242119521978920200314572718584995265523235225587228975886710511855501710470163649632761488899317729943053884132314641377747687975638119132094777769497069556255954031537245957811105217875011509899497752696062748928963281605780942517262774976217663461063680912331030221981433051827519906741285738915397005702326447635845195923640649166530310494885569783989508000344280715868581532826832242144647203531393142251025361866506821695860883605004105862208004440476654027574832078603305884731766236740069411566854496824754558761536201352147934963241039597221404341132342297870517293237489233057335406510464277610336142382379135365550299895416613763920950687921780736585299310706573253951966294045814905727514141733220565108490291792987304210662448111170752411153136765318541264632854767660676223663544921028492602135525959428999005153729028491208277493747933069008199074925710651071766675870081314909460661981433426167330215548196538791617762566403934129026219366764038390123622134753742930729751695349588862441999672547791630729398908283091638866715502470152431589429837867944760012419885615525232399584379209285060418518373512154801760060312646951597932345591416241634668119867158079946680321131213357200382937049485606706114467095019612014749723443159443363662563254359712162432143334612180576945072905749883870150120687696027984317320305291407322779803583395375616762530641605634303022155218169343410634115050596030685041633824154135240376022159918501703555881290333205131375705406831260759974112248490451605422031345264183102048614606636275942039438138959188478277971377232005036301145411215067576576667743288951344423152531417111852584846747428443123174595987315325304540564683047858415059703724263652136185848573853965992798725654430360647040362341567082462847275277303225817689141675391972818943419663764371222973269129542760661385278009266471167618553065823580448848795731295589715602705860758954890415040763604082216728159486423396295188510311881004469017351709060492844398219491990895826924575575549615118821417543037296628825303328056839433114519945243963946989899508355224823109677424196639930153649890175062456649384605721510239142861693109687536600667811037619175927995599388547421689316110236566026931360164495251160997857372500940728057700473763884480342708897319990346726967220426504612260565552531158509215849649565188655100774748485416791517853427613458459889062942881409801879085054494129489535044719193283409051007851153504224002807392992520076910314763705776345053922387355156981872691537772657428096384535960466923475731297217863371650154415835785630016335858514130863258775100537612371430357576913148500310344278511588325852376442503898849856566716198848377379400158332792027967216204970114516984638014129252882482309132898416484525230488700253065644547798869056136044415413099076332059572505138116227535024546891015836838323022822272664771489129085797354578016574544759934333471793
Infinite cat:
2 20093
Do nothing and exit:
1 186
Do nothing and exit (multi-line):
3 599084
[[Category:Unknown computational class]]
[[Category:Zero-dimensional]]
[[Category:Languages]]' |
Unified diff of changes made by edit (edit_diff) | '@@ -13,7 +13,7 @@
==Computational class==
-Since standard Befunge is considered to be a finite state machine, it is, strictly speaking, not Turing-complete; thus, Seed cannot be Turing-complete either. However, the actual computational class of Befunge is currently unknown.
+Since standard Befunge-98 is Turing-complete, Seed '''can''' be Turing-complete.
-The Mersenne Twister has a period of 2<sup>19937</sup> - 1. That means that it is not possible to generate every possible Befunge program, which means it may not be Turing-complete, but if at least one Seed generated a program that could for example interpret a bounded version of Brainfuck, then it would mean that it certainly is. If somebody figures it out, please add it here.
+The Mersenne Twister has a period of 2<sup>19937</sup> - 1. That means that it is not possible to generate every possible Befunge program, which means it may not be Turing-complete, but it was proven that Seed is Turing-complete<ref>https://krzysztofszewczyk.github.io/MerseneTuringCompletness/SeedProof.pdf</ref>.
==Running programs==
' |