Seed
From Esolang
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-98 is Turing-complete, Seed can be Turing-complete.
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 it was proven that Seed is Turing-complete[1].
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.
Adder, taken from CodeGolf by User:Palaiologos:
4 141745954
Hello, world (Actually just prints "h"):
4 80814037
True hello world (Created by PPCG user feersum for this answer):
20 854872453003476740699221564322673731945828554947586276010721089172712854441839676581917455319274850944955030258951339804246125714958815519550291630078076933441706558540342671975808828643360922071900333028778314875248417953197990571991784126564752005357199892690656368640420204822142316716413192024742766282266114842280731756458212469988291309261528542889299297601723286769284159107438930448971911102280330101196758384815655479640836157495863547199726234352265518586460633795171196315255736880028338460236768181141732764911402112878175632130129852788301009582463631290071329795384336617491655825493435803011947670180368458659271192428341035912236946048939139042310380278430049252171822721598175984923434205610723412240162418996808671543770639111617709604242882388664919702606792443015941265168129550718541372361144081848761690730764968771245566074501485020726368378675085908872608679630368472956274468410052703615106090238423979678950131481176272880569100533049143775921798055136871254424261001442543122666701145111965968366507060931708140304772342855064834334129143038575569044150428480231956133612367393837580345180691911525531699573096952433882387811884727975431823620782822755161559988205401134640722220804177812794328129589949692446031008866917615922944976151073653201316255518389496411696741029209242119521978920200314572718584995265523235225587228975886710511855501710470163649632761488899317729943053884132314641377747687975638119132094777769497069556255954031537245957811105217875011509899497752696062748928963281605780942517262774976217663461063680912331030221981433051827519906741285738915397005702326447635845195923640649166530310494885569783989508000344280715868581532826832242144647203531393142251025361866506821695860883605004105862208004440476654027574832078603305884731766236740069411566854496824754558761536201352147934963241039597221404341132342297870517293237489233057335406510464277610336142382379135365550299895416613763920950687921780736585299310706573253951966294045814905727514141733220565108490291792987304210662448111170752411153136765318541264632854767660676223663544921028492602135525959428999005153729028491208277493747933069008199074925710651071766675870081314909460661981433426167330215548196538791617762566403934129026219366764038390123622134753742930729751695349588862441999672547791630729398908283091638866715502470152431589429837867944760012419885615525232399584379209285060418518373512154801760060312646951597932345591416241634668119867158079946680321131213357200382937049485606706114467095019612014749723443159443363662563254359712162432143334612180576945072905749883870150120687696027984317320305291407322779803583395375616762530641605634303022155218169343410634115050596030685041633824154135240376022159918501703555881290333205131375705406831260759974112248490451605422031345264183102048614606636275942039438138959188478277971377232005036301145411215067576576667743288951344423152531417111852584846747428443123174595987315325304540564683047858415059703724263652136185848573853965992798725654430360647040362341567082462847275277303225817689141675391972818943419663764371222973269129542760661385278009266471167618553065823580448848795731295589715602705860758954890415040763604082216728159486423396295188510311881004469017351709060492844398219491990895826924575575549615118821417543037296628825303328056839433114519945243963946989899508355224823109677424196639930153649890175062456649384605721510239142861693109687536600667811037619175927995599388547421689316110236566026931360164495251160997857372500940728057700473763884480342708897319990346726967220426504612260565552531158509215849649565188655100774748485416791517853427613458459889062942881409801879085054494129489535044719193283409051007851153504224002807392992520076910314763705776345053922387355156981872691537772657428096384535960466923475731297217863371650154415835785630016335858514130863258775100537612371430357576913148500310344278511588325852376442503898849856566716198848377379400158332792027967216204970114516984638014129252882482309132898416484525230488700253065644547798869056136044415413099076332059572505138116227535024546891015836838323022822272664771489129085797354578016574544759934333471793
Shorter "Hello World" made by User:Palaiologos for this PPCG challenge:
20 77698190481213510983405846204529755428212736563278528088055816123655499433757607718113585773285686740433752335768949721107461077652705328567448384490378909463204984642622585570301449419608763821501335954761638946551568252142160714228369356054944595121742743720935369219143086698092657062614382519069928478344861416117079283276656675368390764675728501797178208908097054412833019383889935034413095990596139618411133857423995278221670378808372393943846302426674985203826030563290800228881174929701934609803807325868775242909948272754141956168876233403760199007405891058308908050926690654387065882097924294620229833663324754801060691573338185912369627367088050915813931912943122729210762147280440619571047157836177316082899933374851699282897590433145623725705072835054748369992455883804733164985993447304652512229557984322495162682327137071900307763332392727562988633724175094951314863886096190608268953115914497741446723188169519334729165647294618083444761551231012944903572063441813639201051793052623561949314826491616145873848990439549320951496534538450810083853945092224500179417650727351532486362656533602860500906935826231374501097567347929533018944533000919137863885267937690665655625569011036163950983389810112758403211861147501289650757555111271813737813381172074709337306647481507917983021055643749698971365256395367215437223669891280521155247529741719633106765965869860677198632388808752014013939448563313855130972968670015202479226496876067874099463222366536167126653600056389712632892652810365218798697007191747287017174284819764736012653205048166550645507761123345279502597627995423826537299795220169894222867163817508592362092945387317777666016102146798532337718546431888424995701016828542559577710937459975677354300708252448630110787487122698124054544454425586794841157136743408274159313823745226919626156949004386804874236325506583268311452185182143521552429596087556634158778951670223004413763782647825362665491934988477225698133609360969370513836064317152213804169538880632390908441210809806024082600637872813704781431414342781727628446451808751293046212690472851527294326981763969926510021099532791692362104324026231160941956411410511639925420026544463125250979130259151326444714248961523031316570018708849878676230362246913063109584502143502908906243190007062857721367402065760878808920961082444422470813023453274563914735545463757909757689866565064353853099958949763412521666109346825939993377745919874506439752272141853783745051726268592621080457687000431023453539135927140364910898906534604541224314820195082362228787083990333757268808864746297304451768935814651205074884015268982492445996542040655715230139673520569765431617018824427859214902954216246257690105154030408059145566852643855789351907818461502260430297487602982850090037405732117988720732457199005151517240766953718440639691354185802798689950155164379549518496065038927905828230066053603755553745353618846804435103593395141938947781375633374976924393453162350331593801284839409264892975739791751842620029351535320807733966984270102067017902086335370470815153908942490581427972998999752666174807935897314584088695849094389002316139005810918748032068307783088481430339303809949409414892479892121893571274086727250767713365523021125610242269894861374297866741571608166536165735922984579027986499758294460652554897534526492251140681138244025665400003029337114012766773010641359450599171473565675885966777145500248501370644599274741842644014722083732709145488157998306684831419559774212264003518406013032514468522158218837161285401631773099549510145156007147884565387852623860047153609138110997222297132678660783411624002400927435687937355446057878202312894093195453248164648271580944753933355967626542678764854079218206499479071658357103085513937246462858404881973219571392564909528645166637501279457604649906515968389831094896970731573714836150178126997674563415266672131632765794599548356902607125568792417432226125654028873443580337866760487651905138461301986816386866811155111486155341154153322710638921116465132825486519667178335471102213200521032618562169530188826434060179505699797068436325168526618824444305122475837890944742004331675952611756641739756206337285946
Infinite cat:
2 20093
Do nothing and exit:
1 186
Do nothing and exit (multi-line):
3 599084
