» »

Ustavljivost linearno omejenih avtomatov

Ustavljivost linearno omejenih avtomatov

«
1
2

OwcA ::

Otroška radovednost - gonilo napredka.
  • spremenilo: OwcA ()

CaqKa ::

>>> Eni vsaj ne "skrivajo" svojih napak pred celim belim svetom kot to rado počne neko podjetje in so ob tem hvali, kako varno kodo producira...
>>> flejm on...

mah.. a sem čist slučajno očital karkoli?
omenil sem da ima Linux kernel 1000 bugov in da se mi to zdi veliko. sicer nisem programer, tako da naj en programer pove ali je to veliko ali ne.
ne pa igrat ožaljenega opensourcarja..

>>> Ni 100% staticnih preverjalnikov, ze zaradi tega ker "100% staticno preverjanje" ni definiran pojem. Torej lahko pozabis na to, da bi nasel kar vse buge, ki bi jih lahko. V vsak tak preverjalnik gre veliko dela in vecinoma iscejo nek zelo specificen razred bugov.
>>> kdor pozna teoretične osnove račualništva ve, da ni mogoče niti ugotoviti ali se program ustavi na vseh vhodih, kaj šele da bi se ugotovilo ali deluje pravilno (poenostavljeno povedano).

ah ok.. zgleda so me eni narobe razumeli.
ja vem da je tako orodje težko skup spravit. še več. sem mnenja da se tako orodje da naredit in to celo tako ki ti bo vse buge odkrilo, vprašanje je samo v času da se tako orodje sproducira in v hitrosti računalnika ki bo to preverjal.
nadalje mi je popolnoma jasno da tak program najde le zelo površinske buge. celo omenjam da ta kritičnih tak program ne najde, ker še verjetno njegov razvoj ni tako daleč.
očitno pa ni nihče opazil med vrsticami da predlagam da se tak program naredi vsem na voljo, tako da ga bodo lahko uporabljali. a se ne sliši butasto 'skripta [od tretje osebe, ki je analizirala naš sw [da bi nas morebiti očrnila]] nam je našla buge'

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

ja vem da je tako orodje težko skup spravit. še več. sem mnenja da se tako orodje da naredit in to celo tako ki ti bo vse buge odkrilo, vprašanje je samo v času da se tako orodje sproducira in v hitrosti računalnika ki bo to preverjal

Turing se v grobu obrača...

Zgodovina sprememb…

  • premaknilo od: OwcA ()

CaqKa ::

a so ga živega pokopali?
no. kakšen EA bi kar pomagal pri tem. naj thomas pove kaj več. on je specialist za take zadeve :)

>>> Edina korist od nje je to, da so ali bodo teh 1000 bugov popravili in potem boš vedel, da ima 1000 bugov manj.

heh onih 50 kritičnih pa bo še vedno ostalo :) dokler se skripte ne izboljšajo :)

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

Jaz sicer malo drugace gledam na to zadevo, niti nima turing toliko veze tukaj. Bistvo problema je v tem, kaj je "pravilno delujec softver", torej tocna matematicna definicija pravilnosti. Namrec, kolikor vem, noben program preko nekaj deset tisoc vrstic v celi zgodovini clovestva nima zares tocne definicije kaj sploh dela.

Je pa res, da naceloma v nobenem programu noces imeti null pointer crasha, kar je tocno to kar coverity isce...
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

Kot kaže, ne veš ravno dobro, kdo je bil Turing oziroma kaj je ugotovil, zato pa pišeš takšne, hm, bom vljudno rekel - zmote.:)

Dobro si zapomni tole: Ne obstaja program, ki bi kot vhod prejel opis poljubnega drugega programa (njegovo izvorno kodo) in bi ugotovil, ali se ta vhodni program ustavi pri vseh vhodih ali ne. Enostavno ne obstaja. Pa ne, da ga še nihče napisal, sploh ga ni možno narediti - ker ne obstaja. Kakorkoli napišeš svoj program, vedno se bo prej ali slej pojavil primerek vhodnega programa, pri katerem se bo tvoj program zaciklal.

Ker (v splošnem) nikoli ne boš mogel ugotoviti, ali se morda vhodni program zacikla, posledično tudi ne boš mogel ugotoviti vseh njegovih bugov. Pri nekaterih vhodih se bo namreč tudi tvoj program zaciklal. EA ne bo nič našel, ker tak program ne obstaja. 1000x hitrejši računalnik ti ne bo nič pomagal, saj boš z njim dosegel le to, da se ti bo neskončna zanka v tvojem programu izvajal 1000x hitreje - v neskončnost.>:D

Še enkrat razmisli, ali bi se lotil pisanja programa, ki najde vse buge kateregakoli programa, ki mu ga daš na vhod.;)

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

niti nima turing toliko veze tukaj

Pa še kako ima vezo. "Zaradi njega" ne moreš napisati programa, ki bi našel vse buge v (poljubnem) vhodnem programu. Beri zgornji post.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

CaqKa ::

>>> ali se ta vhodni program ustavi pri vseh vhodih ali ne

kaj bi naj pomenilo 'ustavi'?

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

Ja da se zmeraj (pri vsakem vhodu) izvede v končnem času, kaj pa drugega.:) Da se ne zacikla v neskočnčo zanko. V večini primerov dejstvo, da se nek program izvaja v neskončnost (dokler ga na silo ne ubiješ), pomeni bug. Npr. od programa za računanje produkta dveh matrik upravičeno pričakujemo, da se bo prej ali slej ustavil in vrnil rezultat (čeprav bo morda pri velikih matrikah zelo dolgo računal, ampak prej ali slej naj bi prišel do konca).

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

> Pa še kako ima vezo. "Zaradi njega" ne moreš napisati programa, ki bi našel vse buge v (poljubnem) vhodnem programu. Beri zgornji post.

Mi je cisto jasno kaj govoris :). Za zacetek se sploh vprasat ne znamo ali je softver "pravilno delujoc". Turingove zadeve postanejo relevantne sele ko imas konkretno vprasanje - da/ne. Torej, najprej moramo za vsak konkreten program definirat pojem "bug". Je pa res, da zelo hitro prides do turinga:

> kaj bi naj pomenilo 'ustavi'?

Halting problem - Wikipedia, the free encyclopedia, hec je v tem, da je vecina zanimivih vprasanj v splosnem enako tezkih kot vprasanje "ali se program ustavi", recimo "ali se ta progam sesuje". Coverity pa pocne nekaj drugega, isce konkretne primere, kjer pa se da z veliko gotovostjo reci ali se program sesuje ali ne.
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

CaqKa ::

no jaz sem še vedno mnenja da tak program obstaja (da ga je možno naredit). Navsezadnje so programi digitalni in sprejmejo končno število vhodov. samo vprašanje singularnosti.
s pomočjo kakega bodočega AIja bo to kar fino delalo ;)
sicer to jaz samo na urinu čutim pa nekih konkretnih dokazov za to nimam... ;)

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

> no jaz sem še vedno mnenja da tak program obstaja (da ga je možno naredit). Navsezadnje so programi digitalni in sprejmejo končno število vhodov.

Ja, turingov stroj je matematicen konstrukt, ki predpostavi neskoncen pomnilnik. Zdaj, ce pa vzames en obicajen program, ki pokuri 10 mb rama, porabis 83886080 bitov za notranje stanje. Kar pomeni, da je ta program lahko regularen avtomat z 2 na 83886080 stanji. Zato se uposteva turingove stroje kot uporabno teorijo :D
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

OwcA ::

no jaz sem še vedno mnenja da tak program obstaja (da ga je možno naredit). Navsezadnje so programi digitalni in sprejmejo končno število vhodov. samo vprašanje singularnosti.

Končnost/fizikalnost (vesolja) ti tu ne pomaga kaj dosti, edino kar pridobiš je, da veš da se bo stvar ustavila, ko bo zmanjkalo energije, kar pa ni ravno presunljivo.
Otroška radovednost - gonilo napredka.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

no jaz sem še vedno mnenja da tak program obstaja (da ga je možno naredit). Navsezadnje so programi digitalni in sprejmejo končno število vhodov

Ni res, možnih vhodov je neskončno mnogo, marsikateri program jih tudi sprejme neskončno (to se pravi, da se ustavi pri kateremkoli končnem vhodu). In ravno dejstvo, da so programi digitalni, je v tem primeru njihova slabost - to namreč pomeni, da jih je samo števno neskončno, medtem ko je vseh možnih problemov še več kot toliko. Iz tega avtomatično sledi, da za nekatere probleme enostavno ni programa, ki bi tovrsten problem rešil. Je to razumljivo, CaqKa?

No, če smo čisto natančni, je res, da imajo dejanski računalniki samo končno število stanj. Če program pride v stanje, v katerem je že bil (tj. vse vrednosti v pomnilniku so v nekem trenutku izvajanje enake kot že nekoč prej, tudi npr. vrednost programskega števca v procesorju), potem, ker zadeva deluje deterministično, je jasno, da bo čez nekaj časa program še tretjič prišel v isto stanje (pa potem še četrtič pa petič in tako naprej v nedogled...). Če bi shranjeval vsa pretekla stanja in bi vsako novo stanje primerjal z vsemi dosedanjimi, potem bi na ta način lahko odkril morebiten cikel in bi s tem ugotovil, da se je program ujel v neskončno zanko. Žal je za praktične primere tak postopek obupno počasen, poleg tega pa je zelo hitro možnih stanj toliko, da celotno vesolje nima dovolj pomnilniške kapacitete, da bi lahko shranil vsa => v praksi torej neuporabno, torej lahko kar vzameš, da ne moreš v splošnem ugotoviti, ali se je nek poljuben program zaciklal ali ne.

Sicer si pa celo sam rekel, da nisi programer, torej prepusti to debato strokovnjakom.;) Pa za začetek si obvezno preberi tisti Wiki link, tam piše točno to, kar tu želimo povedati.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Jeti, da ne bi o tem ta imaš lahko neskočno zanko, kjer se ti en counter stalno povečuje. Poj ti pa tisto kar si ti napisal nič ne pomaga :D No če ne drugega enkrat prideš do največjega števila(v računalniku seveda) in poj vse skup crkne :D

EDIT: Sicer je pa asistent pri TOR enkrat reku, da če kdo pogrunta tak program naj ga pride pokazat. Mu v življenu ne bo treba več skrbet za denar :D
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

Jeti, da ne bi o tem ta imaš lahko neskočno zanko, kjer se ti en counter stalno povečuje. Poj ti pa tisto kar si ti napisal nič ne pomaga

Seveda ti pomaga (teoretično). Tudi counter je samo neka vrednost v pomnilniku, ki jo shraniš takrat, ko shranjuješ stanje in potem primerjaš z dosedanjimi stanji.:) Ampak kot že rečeno, je to v praksi neuporabno, ker je možnih stanj preveč.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

...namreč računalnik je linearno omejen avtomat in ne TS, zato tvojega counterja ne moreš povečevati v neskončnost, saj imaš končno mnogo pomnilnika. Prej ali slej se ti biti counterja prevrtijo (in ti ugotoviš cikel), ali pa v tem robnem primeru pride do napake - program se sesuje, torej je spet končal svoje delovanje v končnem času (pa čeprav na nepravilen način, končal se je kljub temu).

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Hehe, tvoj program bi potem reševal probleme za katere še ne poznamo rešitve :D Wiki Samo utegnil bi precej časa trajat.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

Lahko ker nehaš lepiti režeče se smileye ker je iz tvojega pisanja razvidno, da razumem TOR malo bolje od tebe.;)

Še enkrat: Računalnik NI Turingov stroj, ampak linearno omejen avtomat. Ima namreč končno mnogo pomnilnika, kolikokrat ti bom moral še napisati? Za linearno omejene avtomate pa se (teoretično) da ugotoviti, kdaj se zaciklajo. V praksi se seveda ne da, ker imajo preveč možnih stanj.
In ko smo že pri tvojem linku: teoretično bi se dalo napisati nadzorni program, ki bi simuliral tisti program za iskanje lihih perfektnih števil z Wiki linka in tak program bi lahko v končnem času ugotovil, ali se simulirani program kdaj ustavi ali ne. Če bi našel liho perfektno število, bi se ustavil, če pa ga dovolj dolgo ne bi našel, bi števec "n" prej ali slej prišel do zgornje meje in bi imeli dve možnosti:
a) To bi pomenilo napako. SImulirani program bi se sesul, nadzorni program bi javil "program se ustavi, čeprav z napako"
b) To ne bi bila napaka, biti števca "n" bi se enostavno prevrteli naokoli. Nadzorni program bi ugotovil, da je simulirani program v istem stanju, kot je nekoč že bil, torej je prišlo do cikla. Simulirani program bi nato ubil in javil "program se ne ustavi".

Problem ustavljivosti velja za Turingove stroje (neskončno pomnilnika) in ne za linearno omejene avtomate (končno mnogo pomnilnika). Jasno?

Če meni ne verjameš, pa na vajah Slivnika vprašaj.>:D

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

In mimogrede, "jaz" sploh ne bi pisal programa za iskanje lihih perfektnih števil, kot mi skušaš podatkniti, ampak nadzorni program, ki bi ugotavljal, ali se omenjeni program za iskanje LPF ustavi ali ne (pri izvajanju na nekem konkretnem računalniku s končno mnogo pomnilnika, ne na TS).
Z dovolj velikim (končnim) pomnilnikom za ta nadzorni program bi odgovor dobili v končnem času.

Če misliš, da to ni res, TOR-a ne razumeš tako dobro, kot si domišljaš.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Možno, da TOR bolj obvladaš, saj ga že kar nekaj časa obiskuješ(vsaj če si ti tisti Jeti katerega imam trenutno v glavi) :D

Kaj pa če ne bi imel števca v tistem programu za iskaneje perfektenge lihega števil, ampak while(true) in znotraj zanke na random generiram število, za katerega probavam če je perfektno. Pa ne se mi obesit na random, lahko ga generiram na takle način. Če perfektno število obstaja se bo program ustavil in tvoj nadzorni program bo pravilno ugotovil. Kaj pa v nasprotenem primeru?

Ali pa kaj če napišem program, ki na začetku pogleda koliko pomnilnika je na voljo in ga začne vsega zasedati. Tik preden pa nima čisto nič na voljo pa se zacikla. Ko boš ti šel s svojim nadzornim programom gledat kaj se dogaja, boš tudi sam zasegel vedno več pomnilnika(zato, da boš iskal, če se katere vrednosti ponavljajo) in potem bo moj program crknil, ker ne bo imel na voljo toliko, kot si je želel zasečti. Torej se vsa zadeva obesi zaradi tvojega programa. Sicer se ne bi.

Verjemem, da se da napisat kar dober nadzorni program. Vendar pa za vse programe ne bi deloval. Sicer pa izvoli, napiši tak program. Slivnik bo ploskal z ušesi, če mu ga prineseš. Ravno letos se mi zdi so hoteli imeti seminarsko, kjer bi pisali program, ki za kar največ programov zna povedati ali se zaciklajo ali ne.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

Kaj pa če ne bi imel števca v tistem programu za iskaneje perfektenge lihega števil, ampak while(true) in znotraj zanke na random generiram število, za katerega probavam če je perfektno. Pa ne se mi obesit na random, lahko ga generiram na takle način.

Pa ravno v randomu je hec. Turingov stroj namreč že po sami definiciji deluje popolnoma deterministično. Vhod (začetna vsebina traku) je znan, bralno-pisalna glava je na začetku nad prvo celico traku, s čimer je določen prvi videni simbol, začetno stanje je določeno, funkcija prehodov med stanji je tudi nedvoumno definirana, iz vsega tega pa sledi, da je prvi korak izvajanja (in tudi vsi ostali) 100% predvidljiv.
Turingov stroj tako ne more generirati popolnoma naključnih števil, temveč samo psevdonaključna. Psevdonaključni generator pa ima končno dolgo periodo in bo torej prej ali slej začel generirati spet isto zaporedje psevdonaključnih števil, kar pa bi nadzorni program pri simuliranju seveda ugotovil.

Ali pa kaj če napišem program, ki na začetku pogleda koliko pomnilnika je na voljo in ga začne vsega zasedati. Tik preden pa nima čisto nič na voljo pa se zacikla. Ko boš ti šel s svojim nadzornim programom gledat kaj se dogaja, boš tudi sam zasegel vedno več pomnilnika(zato, da boš iskal, če se katere vrednosti ponavljajo) in potem bo moj program crknil, ker ne bo imel na voljo toliko, kot si je želel zasečti. Torej se vsa zadeva obesi zaradi tvojega programa. Sicer se ne bi.

Nadzorni program ne bi nič odžiral pomnilnika vhodnemu programu, saj bi ga le simuliral, opažena stanja pa bi si zapisoval v svoj pomnilnik. Vhodni program ne bi prav ničesar vedel o tem, da se v resnici ne izvaja na dejanskem računalniku, ampak je samo simuliran. Skratka pomislek o odžiranju pomnilnika je čisto odveč.

Verjemem, da se da napisat kar dober nadzorni program. Vendar pa za vse programe ne bi deloval.

No pa utemelji, zakaj po tvojem naj ne bi deloval za vse programe. Vedno znova pozabljaš, da imamo na voljo končno mnogo pomnilnika, se pravi da se programi dejansko izvajajo na linearno omejenem avtomatu in ne na Turingovem stroju.

Sicer pa izvoli, napiši tak program.

Žal v celotnem vesolju ni dovolj pomnilnika, da bi lahko tak program shranil vsa videna stanja, zato se tega seveda ne bom lotil.:) Teoretično bi ustavljivost poljubnega vhodnega programa, ki bi se izvajal na LOA, lahko ugotovili v končnem času in s pomočjo končno velikega pomnilnika, za praktično uporabo pa imamo časa in prostora žal premalo.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

Ena opomba pri vsem skupaj, da ne bo nesporazumov: govora je seveda o tistih programih, ki na začetku dobijo nek vhod, potem pa računajo svoje in berejo/pišejo samo po danem pomnilniku, ne berejo pa več novih podatkov z zunanjih virov, na podlagi katerih bi se odločali, kako se bodo izvajali naprej. Turingovi stroji (in njihova podmnožica linearno omejeni avtomati) namreč po definiciji ne predvidevajo branja zunanjih podatkov po začetku izvajanja.
Če bi hoteli ugotavljati ustavljivost tudi takšnih programov, ki komunicirajo z "zunanjim svetom", bi morali beležiti tudi stanja teh zunanjih entitet (npr. disk ali pa drug računalnik, ki našemu računalniku pošilja svoje podatke preko mreže). No, v tem primeru bi seveda lahko rekli, da je ves ta sistem en sam velik linearno omejen avtomat in bi kot "stanje" shranjevali celotno globalno stanje takega sistema.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Pa ravno v randomu je hec. Turingov stroj namreč že po sami definiciji deluje popolnoma deterministično. Vhod (začetna vsebina traku) je znan, bralno-pisalna glava je na začetku nad prvo celico traku, s čimer je določen prvi videni simbol, začetno stanje je določeno, funkcija prehodov med stanji je tudi nedvoumno definirana, iz vsega tega pa sledi, da je prvi korak izvajanja (in tudi vsi ostali) 100% predvidljiv.


Potemtakem trdiš, da je računalnik, ki vsebuje random presega TS (lahko imaš custom računalnik, ki vsebuje enoto, ki se ukvarja z razpadom radioaktivnih jeder)? Če ga ne potem lahko random kar lepo uporabljam, ker sta ekvivalentna. Če ga pa, potem pa morda lahko s takim računalnikom rešimo kak problem, ki ga TS ne more. Kar je pa nakako v protislovju s trditvijo, da TS izračuna vse kar se izračunat da. Se pravi sva ali odkrila toplo vodo, ali pa ne smeš čez random nič rečt :D

Kaj pa če za za naključna števila vzamemo kar podzaporedja števila pi(pa naprimer vsakič za eno mesto večje podzaporednje), ki se dokazano ne začne ponavljati(pi je tudi zelo deterministično določen)? To se ne bo začelo ponavljati.

Pa ne vem zakaj zdaj to na TS prenašaš, saj si sam rekel, da tam tak program za TS ne obstaja. Govoriva o računalnikih.

Nadzorni program ne bi nič odžiral pomnilnika vhodnemu programu, saj bi ga le simuliral, opažena stanja pa bi si zapisoval v svoj pomnilnik. Vhodni program ne bi prav ničesar vedel o tem, da se v resnici ne izvaja na dejanskem računalniku, ampak je samo simuliran. Skratka pomislek o odžiranju pomnilnika je čisto odveč.


Prav lahko napišem tudi program, ki najprej ugotovi, ali ga nekdo nadzira ali ne.

No pa utemelji, zakaj po tvojem naj ne bi deloval za vse programe. Vedno znova pozabljaš, da imamo na voljo končno mnogo pomnilnika, se pravi da se programi dejansko izvajajo na linearno omejenem avtomatu in ne na Turingovem stroju.


Kot si že sam ugotovil, ti bo zmanjkalo pomnilnika, če ne bo še kak drug problem.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

JerKoJ ::

Cofko pejt se ti se mal TOR ucit, ti ne bo skodval :D
Prav lahko napišem tudi program, ki najprej ugotovi, ali ga nekdo nadzira ali ne.

No pa daj - en simple progi, ki ti potem, ko ga pozenes izpise :
- laufam se na fizicnem cpuju
- laufam se v vmware
- nekdo me simulira s svincnikom na papirju

Kot si že sam ugotovil, ti bo zmanjkalo pomnilnika, če ne bo še kak drug problem.


No ja - se da narest, da je treba zlo mal pomnilnika. Nadzorni program sprejme na vhod program in ga pozene (simulira) na zacetku v zacetnem okolju (okolje 0). Po izvedbi vsake instrukcije v vhodnem programu dobimo novo okolje (1,2,...). Po izvedbi n-te instrukcije dobimo okolje n in ga shranimo. Potem zopet startamo program od zacetka v okolju 0 in ponovi vse istrukcije do (n-1) - cim je prvi od okolij (0,1,...,n-1) enak okolju (n) se program cikla - drugace se ne - nalozis okolje n in pozenes instrukcijo n+1 ter postopek preverjanja ponovis. Memorije rabis za 2 okolja in le se ene par bajtov vec, je pa casovno zadeva zelo potratna.

Kaj pa če za za naključna števila vzamemo kar podzaporedja števila pi(pa naprimer vsakič za eno mesto večje podzaporednje), ki se dokazano ne začne ponavljati(pi je tudi zelo deterministično določen)? To se ne bo začelo ponavljati.


Psevdo random ne pomeni, da gre nujno za perodicna zaporedja stevil. Deterministično pomeni le, da se da iz prejsnjih izhodov generatorja ugotoviti nesljednji izhod generatorja. Ker so nekatere funkcije "zelo" komplicirane govorimo o psevdo randomu. Sej tut zaporedje a(n)=a(n-1)+1 ne da periodicnega zaporedja, ni pa ravno dober random. Dober pseudo random mora prestat se kar nekaj zahtevnih statisticnih testov. V praksi se najbolje pac izkazejo peridocna zaoredja (z zelo velikimi periodami). Med branjem tega odstavka si lahko ze ugotovil, da decimalke stevila Pi pac niso random, res pa je da niso periodicne.

Potemtakem trdiš, da je računalnik, ki vsebuje random presega TS (lahko imaš custom računalnik, ki vsebuje enoto, ki se ukvarja z razpadom radioaktivnih jeder)? Če ga ne potem lahko random kar lepo uporabljam, ker sta ekvivalentna. Če ga pa, potem pa morda lahko s takim računalnikom rešimo kak problem, ki ga TS ne more. Kar je pa nakako v protislovju s trditvijo, da TS izračuna vse kar se izračunat da. Se pravi sva ali odkrila toplo vodo, ali pa ne smeš čez random nič rečt :D


Glede razlike v uporabi true randoma in psevdo randoma si preberi poglavje 9. v dodatni snovi za tor2 na Vilfanovi domaci strani ( link). Povzetek - nedeterministicni TS je ekvivalenten TS edino eden lahko NP probleme izracuna v P casu - drugi pa (verjetno) ne. Seveda nedeterministicnega TS ne znamo sestavt zato uporabljamo TS z random odlocitvijo. S tem lahko nekatere probleme z veliko verjetnostjo pravilno resimo v P casu (primer je iskanje prastevil). Razlika med true random odlocitvami in prevdorandom so lahko le v porabljenem casu pa se te so se vedno v P, tako da vpliva prakticno ni.

Sicer je pa tole zelo zelo OFF-TOPIC in bi lahko kaksen mod naredil fork v lozo :D .

Zgodovina sprememb…

  • premaknilo od: OwcA ()

CaqKa ::

>>> Potemtakem trdiš, da je računalnik, ki vsebuje random presega TS (lahko imaš custom računalnik, ki vsebuje enoto, ki se ukvarja z razpadom radioaktivnih jeder)? Če ga ne potem lahko random kar lepo uporabljam, ker sta ekvivalentna. Če ga pa, potem pa morda lahko s takim računalnikom rešimo kak problem, ki ga TS ne more. Kar je pa nakako v protislovju s trditvijo, da TS izračuna vse kar se izračunat da. Se pravi sva ali odkrila toplo vodo, ali pa ne smeš čez random nič rečt


hehe nice one.
a toti novi računalniki na qubite pa to bodo turingovi stroji?

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

Potemtakem trdiš, da je računalnik, ki vsebuje random presega TS (lahko imaš custom računalnik, ki vsebuje enoto, ki se ukvarja z razpadom radioaktivnih jeder)? Če ga ne potem lahko random kar lepo uporabljam, ker sta ekvivalentna. Če ga pa, potem pa morda lahko s takim računalnikom rešimo kak problem, ki ga TS ne more. Kar je pa nakako v protislovju s trditvijo, da TS izračuna vse kar se izračunat da. Se pravi sva ali odkrila toplo vodo, ali pa ne smeš čez random nič rečt

hehe nice one.

No, no, nikar se prehitro ne veseli, CaqKa. Tudi ti pojdi še malo TOR študirati. ;) Cofko Cof je dejansko izumil toplo vodo. Z radioaktivnim dodatkom je sestavil nekakšen kvantni Turingov stroj (če zanemarimo končno količino pomnilnika, seveda). Kvantni Turingov stroj pa dejansko je močnejši od navadnega Turingovega stroja, saj lahko generira prava naključna števila, ki jih klasičen Turingov stroj ne more. Ker pa se pogovarjamo o klasičnih Turingovih strojih (oziroma o linearno omejenih avtomatih), uporaba pravega random generatorja (npr. radioaktivnega) ni dovoljena. Če pa rečemo, da radioaktivna snov ni del računalnika, pa to pomeni, da računalnik dejansko ne generira naključnih števil ampak jih bere z zunanjega vira, ampak to se ne sklada z definicijo TS (oz. LOA), kjer je ves vhod zapisan na traku še pred začetkom izvajanja.
Ostane torej še "random" generator, ki za generiranje naključnih števil uporablja decimalke števila PI (le-te so, po dosedanjih testih, res random). Zakaj "random" v narekovajih? Ker to pač ni pravi random generator, žal mi je, fanta.>:D Če hočeš generirati naključna števila s pomočjo števila PI, moraš znati računati njegove decimalke. Obstajajo različni iterativni postopki za to, dejstvo pa je, pa da koncu izračunaš decimalke PI tako, da koeficiente, ki si jih izračunaval med iteracijami, vstaviš v neko formulo in izračunaš rezultat. Več iteracij računanja koeficientov, kot algoritem naredi, več decimalk števila PI je pravilno izračunanih, ko koeficiente vstavimo v formulo. Ker pa imamo pri računalniku končno mnogo pomnilnika in lahko koeficiente predstavimo le s končno mnogo biti, je jasno, da je možnih kombinacij koeficientov le končno mnogo. Zaradi tega lahko pri danem pomnilniku izračunamo le končno mnogo decimalk števila PI in na podlagi tega le končno mnogo naključnih števil. Po dovolj vztrajnem klicu funkcije te predlagane funkcije rand() bo novih "naključnih števil" zmanjkalo in nadzorni program bo ugotovil ciklanje ter s tem tudi neustavljivost programa za iskanje lihih perfektnih števil (oziroma ustavljivost, če bo program prej našel kakšno tako število).


Tiste trditve, da se da napisati program, ki bi vedel, ali ga nekdo opazuje, pa raje ne bom komentiral, ker nisem tako zloben.>:D Je že JerKoJ razložil, kako je s tem.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Ovo kle maš program, ki ti napiše, če uporablaš vmware:
Link
Na papirju pa ne velja, ker more bit program.

No ja - se da narest, da je treba zlo mal pomnilnika. Nadzorni program sprejme na vhod program in ga pozene (simulira) na zacetku v zacetnem okolju (okolje 0). Po izvedbi vsake instrukcije v vhodnem programu dobimo novo okolje (1,2,...). Po izvedbi n-te instrukcije dobimo okolje n in ga shranimo. Potem zopet startamo program od zacetka v okolju 0 in ponovi vse istrukcije do (n-1) - cim je prvi od okolij (0,1,...,n-1) enak okolju (n) se program cikla - drugace se ne - nalozis okolje n in pozenes instrukcijo n+1 ter postopek preverjanja ponovis. Memorije rabis za 2 okolja in le se ene par bajtov vec, je pa casovno zadeva zelo potratna.



Že ti dve stanji tako veliki, da ti zmanjka spomina. Npr. da računam pi. Ne bom nikoli končal, vedar pa nikoli ne bom v dveh istih stanjih pa vse tiste decimalke pi-ja ti slej ko prej pojejo pomnilnik.

Psevdo random ne pomeni, da gre nujno za perodicna zaporedja stevil. Deterministično pomeni le, da se da iz prejsnjih izhodov generatorja ugotoviti nesljednji izhod generatorja. Ker so nekatere funkcije "zelo" komplicirane govorimo o psevdo randomu. Sej tut zaporedje a(n)=a(n-1)+1 ne da periodicnega zaporedja, ni pa ravno dober random. Dober pseudo random mora prestat se kar nekaj zahtevnih statisticnih testov. V praksi se najbolje pac izkazejo peridocna zaoredja (z zelo velikimi periodami). Med branjem tega odstavka si lahko ze ugotovil, da decimalke stevila Pi pac niso random, res pa je da niso periodicne.

:
Vem kaj pomeni pseudo random in kaj deterministično. Vidim, da sem malo nejasno tole napisal:
Kaj pa če za za naključna števila vzamemo kar podzaporedja števila pi(pa naprimer vsakič za eno mesto večje podzaporednje), ki se dokazano ne začne ponavljati(pi je tudi zelo deterministično določen)? To se ne bo začelo ponavljati.


Mislil sem: Kaj pa če namesto naključnih števil ....

Glede razlike v uporabi true randoma in psevdo randoma si preberi poglavje 9. v dodatni snovi za tor2 na Vilfanovi domaci strani (link). Povzetek - nedeterministicni TS je ekvivalenten TS edino eden lahko NP probleme izracuna v P casu - drugi pa (verjetno) ne. Seveda nedeterministicnega TS ne znamo sestavt zato uporabljamo TS z random odlocitvijo. S tem lahko nekatere probleme z veliko verjetnostjo pravilno resimo v P casu (primer je iskanje prastevil). Razlika med true random odlocitvami in prevdorandom so lahko le v porabljenem casu pa se te so se vedno v P, tako da vpliva prakticno ni.


To je bil tudi moj point, pač sem hotel jetiju povedat naj se ne vtika v moj random. Ker sta tako ali tako enakovredna.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

JerKoJ ::

Ovo kle maš program, ki ti napiše, če uporablaš vmware: Link
Na papirju pa ne velja, ker more bit program.


Ti sploh ves kaj je to program? Zdej pa ze mal buce valis - bos reku, da v mislih ga pa lahko izvajas al ti programas
kr tko "random" pa vids kaj ven pride? Prvi sahovski program sploh nikol ni racunalnika vidu, pa se ga je dal igrat - zanimivo ne?

Si sploh pogledu na katerem principu deluje tvoj omenjeni progi?
Kaj za vsak simulator na tem svetu bos napisal 10+ vrstic ASM kode? To, da se da vmware detektirat
je samo zarad tega ker obstaja komunikacijski mehanizen.

Both Virtual PC and VMWare allow you to install "add-in"s to accelerate emulation, allow drag-n-drop from your real desktop to your virtual desktop, and allow file sharing between your real machine and the virtual machine. In order to accomplish this task, a communication mechanism between the virtual machine software and the virtual machine itself must exist. This sort of interfacing is called a "backdoor interfacing", since, using a special/undocumented mechanism, certain commands can be carried and interpreted in a different manner (by the virtual machine software) unlike having them interpreted by the real machine.


Naprej:

Že ti dve stanji tako veliki, da ti zmanjka spomina. Npr. da računam pi. Ne bom nikoli končal, vedar pa nikoli ne bom v dveh istih stanjih pa vse tiste decimalke pi-ja ti slej ko prej pojejo pomnilnik.


Ja pa sej simuliras realni racunalnik. Ce bi program poganju na 256MB pomnilnika bi ti cez neki casa vrgel ven out of memory, za omenjeni simulator rabis pa 512MB za stanji in tudi tuki bi prislo do napake out of memory (v simuliranem programu). Zopet smo pri tistmu, da realni racunalnik ni TS ampak LOA. In simulacijo programa na LOA lahko naredis na LOA z 2x vec pomnilnika.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

> Na papirju pa ne velja, ker more bit program.

:D

Kaka pa je tvoja definicija pojma "program"
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

Kaj pa ce ti jaz povem, da mam doma program od fotra, shranjem na temule: Punch card - Wikipedia, the free encyclopedia (sicer ni cisto papir, je bolj kartonasta zadeva)

:D :D :D
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Kaj pa ce ti jaz povem, da mam doma program od fotra, shranjem na temule: Punch card - Wikipedia, the free encyclopedia (sicer ni cisto papir, je bolj kartonasta zadeva)


Super jaz nimam problema s tem kje je shranjen, problem je tem, da je on hotel na papirju sam s svinčnikom preverjat rezultate. Če pogledaš lahko imaš program z lahkoto na papirju in ga skeniraš in potem poženeš.

a pa sej simuliras realni racunalnik. Ce bi program poganju na 256MB pomnilnika bi ti cez neki casa vrgel ven out of memory, za omenjeni simulator rabis pa 512MB za stanji in tudi tuki bi prislo do napake out of memory (v simuliranem programu). Zopet smo pri tistmu, da realni racunalnik ni TS ampak LOA. In simulacijo programa na LOA lahko naredis na LOA z 2x vec pomnilnika.


In spet pridemo do tega, da lahko napišemo program, ki porabi več 1/2 pomnilnika, ki ga imaš ti na voljo. Pa se lahko zacikla šele po tem ko ga toliko porabi.

Si sploh pogledu na katerem principu deluje tvoj omenjeni progi?

Kaj za vsak simulator na tem svetu bos napisal 10+ vrstic ASM kode? To, da se da vmware detektirat

je samo zarad tega ker obstaja komunikacijski mehanizen.


Prosil si me za tak program in si ga dobil. Nisem jaz kriv, da obstaja tak mehanizem. Sicer pa nisem jaz tisti, ki piše simulator, tako da assemblerja ne bom pisal.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

JerKoJ ::

Cofko ali lahko v alinejah napises kaj ti zagovarjas prosim?
Jest pravim da:
1) se da napisat program za LOA, ki na vhodu sprejme program in ugotovi, ali se podani program konca (magar z napako) ali pa se zacikla (je pa neprakticen) ne da bi se sam zaciklu.
2) se ne da napisat programa za TS, ki bi naredil isto
3) se ne da napisat programa (za LOA ali TS), ki bi ugotovil v kaksnem okolju se izvaja.

1) Sem ze opisal algoritem zgoraj. Algoritem potrebuje 2x vec rama kot ga simuliramo ter neprakticno veliko casa (ampak ne neskoncno). Program lahko ugotovi, da se vhodni program cikla. Lahko ugotovi, da se konca z napako (zmanjka memorije, ...), lahko seveda ugotovi tudi da se program konca normalno. Pri primeru uporabe true random - pomeni, da se v okolju nekje pojavijo random biti - ker je pomnilnik koncen je razlicnih random stevil lahko le koncno mnogo (n) in najkasneje po n+1 koraku bo nadzorni program ugotovil cikel (ce predpostavimo, da so vsi ostali biti okolja vedno nespremenjani). Nihce ne trdi, da tak program dela prav, trdim le da tak program obstaja - ustavi se pri vsakem moznem vhodu in se nikoli ne zacikla sam (je rekurzivni !).
2) Zopet glej ze omenjeni wiki link. Vazno je, da tak program (rekurzivni) ne obstaja, ki bi pri vsakem vhodu odgovoril DA ali NE. Ce mu podamo ravno pravi program se stvar zacikla in odgovora ne dobimo. Ceprav imam obcutek, da to celo nekako zastopis (ima pa CaqKa mal problemov).
3) Tvoje poznavanje v tej tocki je porazno. Na papirju torej ne moremo poganjati programa - ti zna pa vsak otrok izpisat (ne da bi stvar zagnal na racunalniku) izhod programa: int i=5; System.out.println(i); al ti morem se kaksen bolj banalen primer navest. Vse skupaj velja ce je simulacija pravilna. Ce simulacija ni pravilna - kot to velja za vmware in virtual pc - potem obstaja za vsak simulator posebaj nekaj ukazov iz katerih se da sklepat na katerem okolju se nahajas. Nikakor pa to ne velja v splosnem al pa rect, da se ne da napisat pravilnega simulatorja ce ne uporabis vsaj miljon tranzistorjev na osnovi silicija.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

CaqKa ::

No, no, nikar se prehitro ne veseli, CaqKa. Tudi ti pojdi še malo TOR študirati.

ja samo ti boš najprej povedal kaj je TOR, pa tudi ostali boste nehali kratice uporabljat dokler jih ne razložite..
LOA???
tor poznam edino od mathaiia ko un anomizer tool vsakič znova forsira..

jaz pravim da se z dovolj vlkim databejsom da naredit program (ali neko stvar), ki ti bo za dano input kodo povedala, kje so bugi. (pri predpostavki da so v bazi zapisane vse oblike bugov, ki bi se morebiti pojavile v tem programu, torej zadeva nebi odkrivala še nikoli videnih bugov)

kaj je zdaj turingov stroj ali pa ne mi je čist vseeno, govorim o napravah, ki sedaj ali pa v prihodnosti delajo računanje ali razmišljanje namesto nas. v singularnosti bomo znali naredit tako zadevo. če nebomo, potem še nebomo v singularnosti.

glede simulatorjev/emulatorjev (če se ne motim je ena minimalna razlika med njima), če je prav izveden, potem program ki na njem teče, pod nobenim pogojem ne sme in ne more ugotovit na kaki platformi teče.. pa četudi je to papir. sicer ni simulator prav izveden. to da ima vmware en dodaten fičr s katerim se to ugotovi, ne šteje. pc je pc, če ga hočeš emulirat, ga emuliraj popolno.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Matevžk ::

Objavljenih je bilo precej linkov na wikipedio. Sicer ti vzame nekaj dni (vsak dan po nekaj uric) časa, da zadeve vsaj približno preštudiraš, ampak tako je ... ne moreš se vtikati v debato o stvari, ki je sploh ne poznaš, kaj šele razumeš.
TOR je predmet na Fakulteti za računalništvo in informatiko - Teoretične osnove računalništva.
LOA je linearno omejen avtomat, ki je bil s celo besedo že vsaj enkrat omenjen v tej temi.
lp, Matevžk

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

TOR - teoretične osnove računalništva(predment na Fakulteti za računalništvo in informatiko.
LOA - linearno omejen avtomat.

Jest pravim da:
1) se ne da napisat program za LOA, ki na vhodu sprejme program in ugotovi, ali se podani program pr nekem vhodu konca (magar z napako) ali pa se zacikla
2) se ne da napisat programa za TS, ki bi naredil isto
3) program (za LOA ali TS), ki bi ugotovil v kaksnem okolju se izvaja.

1) Če si samo tole pogledaš boš to videl.

Nihce ne trdi, da tak program dela prav, trdim le da tak program obstaja - ustavi se pri vsakem moznem vhodu in se nikoli ne zacikla sam (je rekurzivni !).

Pa tudi kaj mi koristi program, ki ne dela prav?

2. O tej točki nimamo kaj govort, se vsi strinjamo.

3. Ne vem kaj bi rekel o tej točki. Mogoče obstaja, mogoče pa ne. Pa tudi ni toliko važno za to debato, še posebej če pogledaš točko 1.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

JerKoJ ::

Eto na copy/paste iz linka, ki si ga sam nazadnje podal:

There is another caveat. The undecidability of the halting problem relies on the fact that algorithms are assumed to have potentially infinite storage: at any one time they can only store finitely many things, but they can always store more and they never run out of memory. However, computers that actually exist are not equivalent to a Turing machine but instead to a linear bounded automaton, as their memory and external storage of a machine is limited. In this case, the halting problem for programs running on that machine can be solved with a very simple general algorithm (albeit one that is so inefficient that it could never be useful in practice). It involves running the program and trying to find a cycle over the states of the machine's memory.


Glede pravilnosti v tega programa v prejsnjem postu: mislil sem na to kako handlamo true random generator - ce se prej pojavi ista cifra v zaporedju opisani program zazna cikel in rece, da se vneseni program ne ustavi. Torej ce imam progi:
while (true) {
 int i=rand();
 if (i==10) break;
}

lahko "moj" program rece - ima neskoncen cikel ali pa se uspesno konca - odvisno od tega ali prej pride do ponovitve iste stevilke iz generatorja ali pa se prej pojavi 10. Seveda lahko rand funkcijo simuliramo tako da vraca zaporedoma 0,1,....n stevilke in potem hitro lahko ugotivimo, da obstaja izhod iz zanke ali pa ne.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Seveda lahko rand funkcijo simuliramo tako da vraca zaporedoma 0,1,....n stevilke in potem hitro lahko ugitivimo, da obstaja izhod iz zanke ali pa ne.


Kaj pa:
while(true)
{
i = rand();
if(i==1) return 0
else loop forever
}

Zaradi tvoje simulirane funkcije program napačno deluje.

Glede pomnilnika pa takole, poglej si dokaz. Ko kličemo halt(t,t) se lahko zgodi:
1. Halt ugotovi, da se t zacikla
2. Halt ugotovi, da se t ustavi
V obeh teh primerih pridemo v protislovje, kot je opisano že na podanem linku. Zdaj pa imamo zaradi omejenosti pomnilnika še eno možnost.
3. Programu t zmanjka pomnilnika in se zaradi tega ustavi

Pa poglejmo:
halt(t,t) ti v tem primeru reče true, torej program se ustavi. Vendar pa zaradi pogoja if halt(s, s) == false izvedemo loop forever, kar pomeni, da se zaciklamo. Pa smo spet v protislovju.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

> Super jaz nimam problema s tem kje je shranjen, problem je tem, da je on hotel na papirju sam s svinčnikom preverjat rezultate.

Aha, ti torej zagovarjas, da clovek > TS...?

No jaz trdim, da to ni nujno res, en indikator: clovek do sedaj se ni skonstruiral modela racunanja, ki bi univerzalno resil problem ustavljanja.
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

> Pa poglejmo: halt(t,t) ti v tem primeru reče true, torej program se ustavi. Vendar pa zaradi pogoja if halt(s, s) == false izvedemo loop forever, kar pomeni, da se zaciklamo. Pa smo spet v protislovju.

Najprej pogledamo, kaj program naredi za vsak mozen output random generatorja (output je koncen!). Potem bi lahko sestavili tabelo vnaprej. In pozenes program, pogledas kaj je random generator izpljunil, in pogledas v tabeli resitev. Ali se motim?
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Random generatorja v programu trouble sploh ni. Tista koda koda tam, je kar cel program.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Človek je vsaj enakovreden TS, če je pa še kaj več pa lahko podebatiraš npr. v temi Protokol. Pa še enih par podobni tem je.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

> Random generatorja v programu trouble sploh ni. Tista koda koda tam, je kar cel program.

Aha ja, tabela je itak brezveze. Tvoje vprasanje glede pravega random generatorja je odvisno od tega, kak random generator vzames. Ce vzames recimo takega fizikalnega, potem moras s TS-jem simulirat celotno vesolje (ce se da, potem ni pravih fizikalnih rg-jev).

Me pa se vedno zanima, kaj te tako moti s programom na papirju?
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Kot sem že napisal me nič ne moti, če imaš program na papirju. Moti me pa, če se spravi človek preverjat s svinčnikom na papir ali se program ustavi ali ne. Ker ni čist jasno ali je človek morda sposoben česa več od TS.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

Aha, ok. To pomeni da mogoce znas izvest zadevo, ne znas pa napisat na list papirja vnaprej pravila, po katerih bos zadevo izvedel. :D
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

Cofko Cof ::

Aha, ok. To pomeni da mogoce znas izvest zadevo, ne znas pa napisat na list papirja vnaprej pravila, po katerih bos zadevo izvedel. :D


Ja nekaj takega. Saj če pogledaš to na primeru inteligence. Prepričan sem, da sem sposoben vsaj kančka inteligentnega razmišljanja :D , vendar pa niti približno ne znam, kot praviš ti, zapisati pravil, po katerih bi se moral računalnik ravnat, da bi bil inteligenten.
Ars longa,vita brevis.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

JerKoJ ::

Cofko, torej ti se vedno trdis, da se problema ustavljivosti LOA programa ne da narediti z LOA programom. Je dokaz iz strani je lep in sploh preprost ampak velja za TS. Na tej isti strani pise kar dvakrat da problem ustavljivosti ni neresljiv ce omejimo pomnilnik (takoj nad dokazom in se poglavje nizje - "Common pitfalls"). Malo razmisli, kako se mora program troble simulirat pa ti bo kmal jasno, da zmanjka memorije.

Zopet glede pravilnosti opisanega testerja ustavljivosti. Originalni problem je da ne ne obstaja program, ki bi za podani program in njegov vhod ugotovil ali se ustavi (halt(p,i)) za TS. Torej moramo upostevati se vhod v program. Tvoje zvijanje ven z rand funkcijo se lahko cisto brez problema simulira, da se rand jemlje kot vhod. Torej pri nekaterih vhodih se bo tvoj program ustavil (tocno pri vhodu 1) pri vseh ostalih pa se bo zaciklu in simulator bo to sposoben zaznat in napisat - program se za vhod X zacikla.

Zgodovina sprememb…

  • premaknilo od: OwcA ()

64202 ::

true rand je itak razsiritev...
I am NaN, I am a free man!

Zgodovina sprememb…

  • premaknilo od: OwcA ()

jeti51 ::

Cofko, torej ti se vedno trdis, da se problema ustavljivosti LOA programa ne da narediti z LOA programom.

Ravno danes smo po vajah asistenta vprašali, kaj in kako, prišli smo tudi na LOA, pri katerih se dejansko da ugotoviti, ali se program na njih zacikla (mora pa biti LOA determinističen), no, po vsem skupaj mi je pa Cofko potem na hitro omenil, kaj točno ga pri celi stvari še vedno bega. Sem potem malo razmislil in veste, v čem je hec? Program, ki bi ugotovil, ali se nek program na nekem LOA zacikla, je sicer možno napisati, problem pa je, da ga v nekaterih primerih (pri nekaterih vhodih) enostavno ne moreš pognati - ker imaš na voljo premalo pomnilnika, s katerim bi izvedel simulacijo!:))
(oziroma ti pomnilnika zmanjka nekje na sredi, kar pa je isto)

V bistvu je potem vse skupaj stvar semantike, ali bomo rekli, da je to krivda programa (skratka da ne deluje) ali ne. Drži pa, da si na koncu v vsakem primeru ti, kot končni uporabnik programa, pri nekaterih vhodih prikrajšan za odgovor. Pa še tako ali tako bi tudi predolgo trajalo vse skupaj.:)

Po mojem je ravno tole bila srž problema in da kaj dosti niti ni več za povedati...

P.S.: Tisto prej o kvantnem Turingovem stroju... vzemite za vsak slučaj malo z rezervo. Kot je asistent razložil, si trenutno tu stroka še zdaleč ni enotna. Pa še edu link, če koga zanima kaj o tem.

Zgodovina sprememb…

  • spremenil: jeti51 ()
«
1
2


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

IBM predstavil prvi čip, zasnovan po zgledu človeških možganov (strani: 1 2 )

Oddelek: Novice / Znanost in tehnologija
9613212 (9599) Thomas
»

Thomasov problem (strani: 1 2 3 )

Oddelek: Znanost in tehnologija
1318150 (3967) Pixy222
»

Kurzweil in kako narediti možgane (strani: 1 2 3 4 )

Oddelek: Znanost in tehnologija
16818904 (16838) Thomas
»

Turing train terminal

Oddelek: Novice / --Nerazporejeno--
473337 (2536) 64202
»

simulacija procesorja

Oddelek: Programiranje
12923 (722) Zvonko

Več podobnih tem