Seed

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

The Mersenne Twister has a period of 2¹⁹⁹³⁷ - 1. Although that means that it is not possible to generate every possible Befunge program, it has been proven that Seed is capable of generating interpreters for Turing-complete languages, and thus is ℒ-hard (ℒ-hardness can be thought of as being a form of Turing-completeness). The following program due to Kamila Szewczyk evaluates the SKI combinator calculus known to be Turing-complete:

112 15005947709794001551745957934844387741963949195277224222942941175436326514584950738591687605839219554765312673139412565708303623220949435523970322376797353146959745711905510018709836078812043106050834210308953675588904375331147958460963516014023707270232815615580191475313492822637836797632954281710946191499605228074932238550384395938117947060215994891322895044239528628512342238908241756883576002309136458318426853695392342134155539648665540277527361486373315204318620925711966035942972301024071758707541614676997726343666069365960926312389921620411476834005712809293274727572041778318193400305675046336765396855687333907497840274069746276373367369703580554409090562378751245676511475863473197371503596617476237367564859524783860932491719480838743775854752937582631478472858805293525550579186499439467601324049079649702705638149237726903715713198300458483396210318594205002535699020033101313998794049241761482893215545820063264328229881143576843458089686528082309939218920676760397200190753211539050612871378253300234981486827195149285993539318712648895148239989077967469145906695695725639268359301194662154392742578020810701834214158736314590623136502888397978749532810617946493901929092720143858186563905545327303571180219726465764878181781793186557115346627825930278330900621009385247050349799814637325838873386273620292889508639528760077557546022550893317195975075676364661558122052118325128379943533068090012220829021399689156629396236283055797200153622175538248583908589003663439918426202812570956934037616313978141038436250235826227599001867803787753289942830662970049826887648134355967676874394598303565162564098091962321618997451086001894320616183844450949745111961097935961422054551097993708497261609312619851867552774875820025258452120004909524068566821412865560838149303210060349938961761533503092020673002416898086436041943447125182745611224019177109739446600864677559430466121929945756146084077508406141217714924746215384101090025498044684775465393706427360635410805944030744216263012281416728398396416831795019051695841375796012411932982781478577883259595757903277557013560339885004421095676988158159396051716905851695868846217163033650855582743560777135998979147462531018626808123024651044752899172971002767697839239729810707234489951369936874749971224648800779627289820691653942304035510887312581099887291489063786961615815819042632926041887143023442493367191018860931124256737065291117513395597390330436919578761534024220110023138771538795599121937519406552355650683399790256516607065531496732816853693448215404786400970519966206258869445999493937332453168572772112997760870010241144983948646532970556412494478470874278789858188343190563017173944011190771623840595351509754982449024750394701519531006485472627145366830956667859501091417380696397464590991791308983349002274205858210760481683412352685066760822807899782234565255719233842430215301267239587428773746177871165689901600646208417243654576703937071967370788826253003884731359674397195313538272303293175867053889097207394492875065268350307339622671904542995950940807603665603392360313488803906413379430184051083670651885004729854473727892899327473728338289015477022005098264171173287148216655347470405522687318205669926969047603404427022940081372422043277056357622857655043121570602934088962243851150034231358205417695570313960867608351649616601597171103712920006771227684820533564475176054040787432340472274329195572428023594055583381411302879259043579364074516131781566192239762614111449269891788954603213847889168431350014116352332568495719218713235740892206829549462198325993188837102069283539752183758065423840683800603399859637684399037099221818564860203439420354868316030912624198686770619813926501773589831388435439912756367101921385867304769841318242527202174699712749989890549100618766195763093033777895223312002305430160001275541120625668816562872370554533240740711308545492566622447387847129184675258840061167986941835187326795163219815464893135818120045226688158342762111189020715287040929632731150621861797218443116943858771703314057252808040194719272221568604757655663698552989990229004273536247930781680140083595248339872510398208349681626516323634002414520180187717671833484137244164128541147709523893558998899056288656978386170358563298472726263463417577850405538930616250768204180320433714120300698104642831290348733321737432889366924916049752215841193779080800636674778497915959708337417182273764342346866774775653756058911256185185873508680869141984524483214089280934429062520714358784586525050484207441645220993262882342756100509032546437508737632994769953343557031259340876734256731175957719696115684088124816754110816835876004771979087627144264947341007701385546122301660045006701955256463852124008422794869017906021119668922855196994038408121927354830095485511684485897883093363153061118792730884544102569938337293922496429629026756031491789824151232745788879429878141955008264934544729922641571626500646801646006325177424332041649880615834179528840475135442387961477263271755349703111900050322015750046110520113769061873773224255260567367037977307039933923712455102299122383393934719598954896540671632062855631877929121978543395229931810235373538276109853789473509980161486544938872377251787271170167749722788024574615673100600339991716767083485020637569393181718479956878303006973117799848008281819831255077962986793387572680394422233339861138992427628320726864707782719207666267011154525035418875867304015403972370212699575463083434809323275089626152829749877006988525385406485549790996313807504116069326092250060019527246837345192885824159103450484754359747938657719239950929657439192593009675109091074171048468653400294437717256292360536782184532950229108298749236074423546534432582236295463728400904674225389451924335046169486189781521045046285871978796304537708669530610470217951827243335780340661190275411840673425107286839355369264896654238856744240956275

It is probable that Seed may be Turing-complete in a more traditional sense, too; there are infinitely many possible Seed programs, because nothing prevents the creation of a program that's larger than the Mersenne Twister's period (and repeats itself as a consequence). All that would be required, therefore, would be a seed that generates a program whose prefix looks at the length the program as a whole, and interprets the resulting number as a program in some Turing-complete language, executing it; programs could then be compiled into Seed via hardcoding the seed itself, and specifying what program to execute via varying the length. It is not currently known whether any such seeds exist, but it seems likely.

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