Seed

From Esolang
Jump to: navigation, search

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 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:

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)
 

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 219937 - 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.

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)))

Examples

These examples were found with the above script.

Hello, world (Actually just prints "h"):

4 80814037

True hello world (Created by PPCG user feersum for this answer):

20 854872453003476740699221564322673731945828554947586276010721089172712854441839676581917455319274850944955030258951339804246125714958815519550291630078076933441706558540342671975808828643360922071900333028778314875248417953197990571991784126564752005357199892690656368640420204822142316716413192024742766282266114842280731756458212469988291309261528542889299297601723286769284159107438930448971911102280330101196758384815655479640836157495863547199726234352265518586460633795171196315255736880028338460236768181141732764911402112878175632130129852788301009582463631290071329795384336617491655825493435803011947670180368458659271192428341035912236946048939139042310380278430049252171822721598175984923434205610723412240162418996808671543770639111617709604242882388664919702606792443015941265168129550718541372361144081848761690730764968771245566074501485020726368378675085908872608679630368472956274468410052703615106090238423979678950131481176272880569100533049143775921798055136871254424261001442543122666701145111965968366507060931708140304772342855064834334129143038575569044150428480231956133612367393837580345180691911525531699573096952433882387811884727975431823620782822755161559988205401134640722220804177812794328129589949692446031008866917615922944976151073653201316255518389496411696741029209242119521978920200314572718584995265523235225587228975886710511855501710470163649632761488899317729943053884132314641377747687975638119132094777769497069556255954031537245957811105217875011509899497752696062748928963281605780942517262774976217663461063680912331030221981433051827519906741285738915397005702326447635845195923640649166530310494885569783989508000344280715868581532826832242144647203531393142251025361866506821695860883605004105862208004440476654027574832078603305884731766236740069411566854496824754558761536201352147934963241039597221404341132342297870517293237489233057335406510464277610336142382379135365550299895416613763920950687921780736585299310706573253951966294045814905727514141733220565108490291792987304210662448111170752411153136765318541264632854767660676223663544921028492602135525959428999005153729028491208277493747933069008199074925710651071766675870081314909460661981433426167330215548196538791617762566403934129026219366764038390123622134753742930729751695349588862441999672547791630729398908283091638866715502470152431589429837867944760012419885615525232399584379209285060418518373512154801760060312646951597932345591416241634668119867158079946680321131213357200382937049485606706114467095019612014749723443159443363662563254359712162432143334612180576945072905749883870150120687696027984317320305291407322779803583395375616762530641605634303022155218169343410634115050596030685041633824154135240376022159918501703555881290333205131375705406831260759974112248490451605422031345264183102048614606636275942039438138959188478277971377232005036301145411215067576576667743288951344423152531417111852584846747428443123174595987315325304540564683047858415059703724263652136185848573853965992798725654430360647040362341567082462847275277303225817689141675391972818943419663764371222973269129542760661385278009266471167618553065823580448848795731295589715602705860758954890415040763604082216728159486423396295188510311881004469017351709060492844398219491990895826924575575549615118821417543037296628825303328056839433114519945243963946989899508355224823109677424196639930153649890175062456649384605721510239142861693109687536600667811037619175927995599388547421689316110236566026931360164495251160997857372500940728057700473763884480342708897319990346726967220426504612260565552531158509215849649565188655100774748485416791517853427613458459889062942881409801879085054494129489535044719193283409051007851153504224002807392992520076910314763705776345053922387355156981872691537772657428096384535960466923475731297217863371650154415835785630016335858514130863258775100537612371430357576913148500310344278511588325852376442503898849856566716198848377379400158332792027967216204970114516984638014129252882482309132898416484525230488700253065644547798869056136044415413099076332059572505138116227535024546891015836838323022822272664771489129085797354578016574544759934333471793

Infinite cat:

2 20093

Do nothing and exit:

1 186

Do nothing and exit (multi-line):

3 599084