Random

Ne obstaja. Zakaj ne obstaja?

Če je izračunljivo, potem je izračunljivo v Turingovem smislu. Se pravi obstaja konfiguracija Turingove mašine, ki to izračuna. To formulo namreč.

Če pa taka mašina je - potem formula ni ... neizračunljiva?

Kaj pa če namontiraš random na radioaktivni razpad?

Potem je pa takole: NE MOREŠ vnaprej predvideti, kakšno število se ti bo pojavilo iz te TransTuringove mašine. NITI z drugo tako TransTuringovo mašino.

KER ... ne moreš narediti kopije TranTuringove mašine. Ker ko jo scaniraš - jo spreminjaš. Kvantna mehanika - kaj češ.

So bili pa ljudje, ki niso (hoteli) razumeti Bellovega teorema, da skritih parametrov v kvantni fiziki ni. Einstein, Bohm na stara leta, Fredkin, Wolfram ... pa še kdo ... in so govorili, da "Bog ne kocka". Da je pod vsako TransTuringovo mašino pa skrita ena Turingova.

Čudo božje ... zgleda da bi utegnili imeti prav.



Torej, potem ni možnosti za true random - prav nobene!

Double_J

Nikakor ni pravoverno, fizikalno politično korektno ipd. reči, da je spodaj pod kvantnim nivojem vse deterministično.

95% fizikov se s tem ne strinja. Bodo začeli takoj operirati s tem, da ne zastopiš Bellovega teorema, ki naj bi dokazoval "nemožnost skritih parametrov, ki bi determinizirali kvantno mehaniko".

Torej, če se greš z njimi ... dobro imet kakšno krepko gorjačo v rokah.

Tole.

Tudi tole bi jih utegnilo nekoliko umiriti:



Pa še tole.

Samo moraš znati dobro mahat s tem!

larpo

Mozart je navaden smrtnik, ki je nekaj več resursov namenil muziki.

Vsi smo navadni smrtniki. Če smo nesmrtni, je to sekundarna reč.

Jest recimo razumem tiste linke zato, ker se mi zdi vredno investirati nekaj (precej) truda v to.

Če jih ti ne, jih samo zato ne, ker prezgodaj odmahneš z roko. Ko (če) se boš skoncentriral nanje, boš težko krotil svoje presenečenje, kako niso tako zelo OUT kot si zmeraj mislil.

Je pa res, da toliko virov kot jih zahtevajo, je pripravljeno alocirati le malo ljudi. Ker alokacija tu, pomeni dealokacijo (virov) drugje.

Je pa res tudi to - da kdor jih ne alocira, tja, naj bo raje tiho, ko je debata o teh rečeh.

Nevertheless, bom povedal v čem je štos.

Einstein (ki NI bil tak nice guy kot ga ponavadi slikajo) je spet enkrat imel prav. (Četudi je imel narobe večkrat, kot se to običajno prizna.) Ampak tokrat je kaže imel prav, ko se je (z maloštevilnimi soborci) zoperstavil kakšni stoterici top fizikov na svetu. Ki so bili tudi povprečno kakšnih 20 let mlajši. No zoperstavil se jim je, ko so trdili, da obstaja popolni random. To je bilo sila tvegano podjetje, saj je najprej von Neumann s svojo avtoriteto zatrdil, da Einstein niti teoretično ne more imeti prav. Potem je to isto zatrdil Bell, s svojim (miselnim) eksperimentom.

Potem je to zatrdil še Bohm, ki je napisal knjigo, ki naj bi pojasnila spor široki publiki.

Takoj, ko je knjigo končal, je Bohma začel glodati črv dvoma ... v letu dni je spremenil svoj kurz za 180 stopinj. 1952, tri leta preden je Einstein umrl, mu je dal prav. "Bog NE kocka". Toda njegovo delo je ostalo "skrito" preko 30 let. Ko ga je odkril 1986 Bell (!) - in ugotovil, da je njegov miselni eksperiment propadel že leta 1952. To je tudi jasno in glasno povedal. Večina pa se je še zmeraj sklicevala nanj.

Nadaljnih 15 let kasneje, so se Einsteinovci pregrupirali. Wolfram - čeprav (še) ne uživa dosti podpore - pa tudi mnogo drugih, je sklenilo obnoviti determinizem.

Zdaj nam ostane samo še čiščenje terena. "Hunt down and kill" every ortodox indeterminist.

Quite a story - kaj mislite?

Zanimivo !

Nekako mi je jasno, da absolutnega randoma ne moramo doseči. Ampak me čisto tako za "splošno izobrazbo" zanima katera zadeva se najbolj temu približa? Seveda je "temu približa" malo smotano vprašanje, ker je tukaj problem samo v zapletenosti "formule" ki to izračuna. Ampak tisti fiziki/matematiki, ki trdijo da obstaja random, na kaj se sklicujejo?

joco

>Ampak tisti fiziki/matematiki, ki trdijo da obstaja random, na kaj se sklicujejo?

Sklicujejo se na "dejstvo", da je kvantna mehanika končna teorija. Da ni nobene, ki bi jo lahko pojasnila - oziroma razložila.

Ko Alice in Bob ugibata, kateri random izbrani bit ima drugi, bi jima eventualna globja teorija lahko pomagala. Toda potem - se jim zdi - bi morali eksperimenti, ki so jim BILI PRIČE - bi ti eksperimenti morali imeti 16% drugačne izide.

Če mene vprašaš je to zato, ker niso dobro definirali začetnih pogojev, pa mislijo, da so jih.

Človek, ki si je ta (trenutno prevladujoči) argument izmislil (Bell), zdaj misli isto, kot (novi) deterministi.

Von Neumann, ki ga je inspiriral v njegovih zmotnih letih - je NEKAJ POMUTIL - big way!

To je pač tako, kot v Sveti Katoliški Cerkvi ali Komunistični partiji Sovjetske Zveze. (Po)iščejo se krivoverci, heretiki - in odstranijo.

S to razliko, da v fiziki ne ubijejo nikogar. Pa četudi (simbolično) ga, še vedno lahko pride nazaj in obračuna s svojimi "morilci". No ... in prav zdaj poteka začetek velike čistke, ki utegne pomesti dosedanjo "udobno večino".

Power strugle - kaj češ.

OK, ostanimo še malo pri kvantni fiziki. Ta njihova "teorija" o randomu... ali ima kaj veze s časom? V tem smislu, da kje je elektron (npr) vsakih 0.00024 sekunde? In če ne, kako "naj bi potem računali random"?

Še ein frage, kdo so že deterministi (si malo slabo zapomnim imena in potem vse pomešam... )

Pha! Statistika je zadnje na kar bi se opiral. Tam je še 1 + 1 le v povprečju dva...

Ja sej to tudi trdim. Tisti, ki je enačbo nardil točno ve kako deluje.
Random je random zgolj če ne veš kako zadeva točno deluje.
Tudi s kvantno mehaniko je tako.

Albert Einsten - God does not play dice with the universe.

Stephen Hawking - God not only plays with dice, he sometimes throws them where they can't be seen.

Komu verjamete?

cyer pa TESKAn

A tisti linki, ki sem jih dal, vama niso nič nucali?

Hardware za "true" random.

Sposojanje randoma iz analognih izvirov, je relativno česta praksa. Navsezadnje se za SEED pseudorandoma dostikrat uporablja ura, timer. To je pravzaprav nujno, če hočemo, da deterministični program teče "vsakič drugače". Pasjansa bi se postavila vedno enako, če bi ne bila vezana na čas postavitve (v kombinaciji s časom od klika miške).

Ura, temperatura, celo prostor na disku, ali pa čas pinga enga sajta - so zasilo dobre reči, za SEED randoma.

BTW: A je kdo gledu "Beautiful Mind ?"

Komentarji, na tole?

A Random Walk in Arithmetic

New Scientist 125, No. 1709 (24 March 1990), pp. 44-46

Gregory Chaitin

God not only plays dice in physics but also in pure mathematics. Mathematical truth is sometimes nothing more than a perfect coin toss.



THE NOTION of randomness obsesses physicists today. To what extent can we predict the future? Does it depend on our own limitations? Or is it in principle impossible to predict the future? The question of predictability has a long history in physics. In the early 19th century, the classical deterministic laws of Isaac Newton led Pierre Simon de Laplace to believe that the future of the Universe could be determined forever.

Then quantum mechanics came along. This is the theory that is fundamental to our understanding of the nature of matter. It describes very small objects, such as electrons and other fundamental particles. One of the controversial features of quantum mechanics was that it introduced probability and randomness at a fundamental level to physics. This greatly upset the great physicist Albert Einstein, who said that God did not play dice.

Then surprisingly, the modern study of nonlinear dynamics showed us that even the classical physics of Newton had randomness and unpredictability at its core. The theory of chaos, as the series of articles in New Scientist last year described, has revealed how the notion of randomness and unpredictability is beginning to look like a unifying principle.

It seems that the same principle even extends to mathematics. I can show that there are theorems connected with number theory that cannot be proved because when we ask the appropriate questions, we obtain results that are equivalent to the random toss of a coin.

My results would have shocked many 19th-century mathematicians, who believed that mathematical truths could always be proved. For example, in 1900, the mathematician, David Hilbert, gave a famous lecture in which he proposed a list of 23 problems as a challenge to the new century. His sixth problem had to do with establishing the fundamental universal truths, or axioms, of physics. One of the points in this question concerned probability theory. To Hilbert, probability was simply a practical tool that came from physics; it helped to describe the real world when there was only a limited amount of information available.

Another question he discussed was his tenth problem, which was connected with solving so-called ``diophantine'' equations, named after the Greek mathematician Diophantus. These are algebraic equations involving only whole numbers, or integers. Hilbert asked: ``Is there a way of deciding whether or not an algebraic equation has a solution in whole numbers?''

Little did Hilbert imagine that these two questions are subtly related. This was because Hilbert had assumed something that was so basic to his thinking that he did not even formulate it as a question in his talk. That was the idea that every mathematical problem has a solution. We may not be bright enough or we may not have worked long enough on the problem but, in principle, it should be possible to solve it---or so Hilbert thought. For him, it was a black or white situation.

It seems now that Hilbert was on shaky ground. In fact, there is a connection between Hilbert's sixth question dealing with probability theory and his tenth problem of solving algebraic equations in whole numbers that leads to a surprising and rather chilling result. That is: randomness lurks at the heart of that most traditional branch of pure mathematics, number theory.

Clear, simple mathematical questions do not always have clear answers. In elementary number theory, questions involving diophantine equations can give answers that are completely random and look grey, rather than black or white. The answer is random because the only way to prove it is to postulate each answer as an additional independent axiom. Einstein would be horrified to discover that not only does God play dice in quantum and classical physics but also in pure mathematics.

Where does this surprising conclusion come from? We have to go back to Hilbert. He said that when you set up a formal system of axioms there should be a mechanical procedure to decide whether a mathematical proof is correct or not, and the axioms should be consistent and complete. If the system of axioms is consistent, it means that you cannot prove both a result and its contrary. If the system is complete, then you can also prove any assertion to be true or false. It follows that a mechanical procedure would ensure that all mathematical assertions can be decided mechanically.

There is a colourful way to explain how this mechanical procedure works: the so-called ``British Museum algorithm.'' What you do---it cannot be done in practice because it would take forever---is to use the axiom system, set in the formal language of mathematics, to run through all possible proofs, in order of their size and lexicographic order. You check which proofs are correct---which ones follow the rules and are accepted as valid. In principle, if the set of axioms is consistent and complete, you can decide whether any theorem is true or false. Such a procedure means that a mathematician no longer needs ingenuity or inspiration to prove theorems. Mathematics becomes mechanical.

Of course, mathematics is not like that. Kurt Gödel, the Austrian logician, and Alan Turing, the father of the computer, showed that it is impossible to obtain both a consistent and complete axiomatic theory of mathematics and a mechanical procedure for deciding whether an arbitrary mathematical assertion is true or false, or is provable or not.

Gödel was the first to devise the ingenious proof, couched in number theory, of what is called the incompleteness theorem (see ``The incompleteness of arithmetic,'' New Scientist, 5 November 1987). But I think that the Turing version of the theorem is more fundamental and easier to understand. Turing used the language of the computer---the instructions, or program, that a computer needs to work out problems. He showed that there is no mechanical procedure for deciding whether an arbitrary program will ever finish its computation and halt.

To show that the so-called halting problem can never be solved, we set the program running on a Turing machine, which is a mathematical idealisation of a digital computer with no time limit. (The program must be self-contained with all its data wrapped up inside the program.) Then we simply ask: ``Will the program go on forever, or at some point will it say `I'm finished' and halt?''

Turing showed that there is no set of instructions that you can give the computer, no algorithm, that will decide if a program will ever halt. Gödel's incompleteness theorem follows immediately because if there is no mechanical procedure for deciding the halting problem, then there is no complete set of underlying axioms either. If there were, they would provide a mechanical procedure for running through all possible proofs to show whether programs halt---although it would take a long time, of course.

To obtain my result about randomness in mathematics, I simply take Turing's result and just change the wording. What I get is a sort of a mathematical pun. Although the halting problem is unsolvable, we can look at the probability of whether a randomly chosen program will halt. We start with a thought experiment using a general purpose computer that, given enough time, can do the work of any computer---the universal Turing machine.

Instead of asking whether or not a specific program halts, we look at the ensemble of all possible computer programs. We assign to each computer program a probability that it will be chosen. Each bit of information in the random program is chosen by tossing a coin, an independent toss for each bit, so that a program containing so many bits of information, say, N bits, will have a probability of 2?N. We can now ask what is the total probability that those programs will halt. This halting probability, call it ?, wraps up Turing's question of whether a program halts into one number between 0 and 1. If the program never halts, ? is 0; if it always halts, ? is 1.

In the same way that computers express numbers in binary notation, we can describe ? in terms of a string of 1s and 0s. Can we determine whether the Nth bit in the string is a 0 or a 1? In other words, can we compute ?? Not at all. In fact, I can show that the sequence of 0s and 1s is random using what is called algorithmic information theory. This theory ascribes a degree of order in a set of information or data according to whether there is an algorithm that will compress the data into a briefer form.

For example, a regular string of 1s and 0s describing some data such as 0101010101 ... which continues for 1000 digits can be encapsulated in a shorter instruction ``repeat 01 500 times.'' A completely random string of digits cannot be reduced to a shorter program at all. It is said to be algorithmically incompressible.

My analysis shows that the halting probability is algorithmically random. It cannot be compressed into a shorter program. To get N bits of the number out of a computer, you need to put in a program at least N bits long. Each of the N bits of ? is an irreducible independent mathematical fact, as random as tossing a coin. For example, there are as many 0s in ? as 1s. And knowing all the even bits does not help us to know any of the odd bits.

My result that the halting probability is random corresponds to Turing's assertion that the halting problem is undecidable. It has turned out to provide a good way to give an example of randomness in number theory, the bedrock of mathematics. The key was a dramatic development about five years ago. James Jones of the University of Calgary in Canada and Yuri Matijasevic of the Steklov Institute of Mathematics in Leningrad discovered a theorem proved by Edouard Lucas in France a century ago. The theorem provides a particularly natural way to translate a universal Turing machine into a universal diophantine equation that is equivalent to a general purpose computer.

I thought it would be fun to write it down. So with the help of a large computer I wrote down a universal-Turing-machine equation. It had 17 000 variables and went on for 200 pages....(DJ upam da se treseš )

The equation is of a type that is referred to as ``exponential diophantine.'' All the variables and constants in it are non-negative integers, 0, 1, 2, 3, 4, 5, and so on. It is called ``exponential'' because it contains numbers raised to an integer power. In normal diophantine equations the power has to be a constant. In this equation, the power can be a variable. So in addition to having X3, it also contains XY.

To convert the assertion that the halting probability ? is random into an assertion about the randomness of solutions in arithmetic, I need only to make a few minor changes in this 200-page universal-Turing-machine diophantine equation. The result, my equation exhibiting randomness, is also 200 pages long. The equation has a single parameter, the variable N. For any particular value of this parameter, I ask the question: ``Does my equation have a finite or infinite number of whole-number solutions?'' Answering this question turns out to be equivalent to calculating the halting probability. The answer ``encodes'' in arithmetical language whether the Nth bit of ? is a 0 or a 1. If the Nth bit of ? is a 0, then my equation for that particular value of N has a finite number of solutions. If the Nth bit of the halting probability ? is a 1, then this equation for that value of the parameter N has an infinite number of solutions. Just as the Nth bit of ? is random---an independent, irreducible fact like tossing a coin---so is deciding whether the number of solutions of my equation is finite or infinite. We can never know.

To find out whether the number of solutions is finite or infinite in particular cases, say, for k values of the parameter N, we would have to postulate the k answers as k additional independent axioms. We would have to put in k bits of information into our system of axioms, so we would be no further forward. This is another way of saying that the k bits of information are irreducible mathematical facts.

I have found an extreme form of randomness, of irreducibility, in pure mathematics---in a part of elementary number theory associated with the name of Diophantus and which goes back 2000 years to classical Greek mathematics. Hilbert believed that mathematical truth was black or white, that something was either true or false. I think that my work makes things look grey, and that mathematicians are joining the company of their theoretical physics colleagues. I do not think that this is necessarily bad. We have seen that in classical and quantum physics, randomness and unpredictability are fundamental. I believe that these concepts are also found at the very heart of pure mathematics.


Gregory Chaitin is a member of the theoretical physics group at the Thomas J. Watson Research Center in Yorktown Heights, New York, which is part of IBM's research division.

Further Reading G. J. Chaitin, Information, Randomness & Incompleteness, Second Edition, World Scientific, Singapore, 1990; G. J. Chaitin, Algorithmic Information Theory, third printing, Cambridge University Press, Cambridge, 1990.

Ko dopustiš neskončnost - magari samo v teoriji - imaš štalo. Trdim. Najprej Goedel. Dokazal je tole:

Za vsak sistem, dovolj bogat, da vsebuje aritmetiko znotraj števno neskončne množice naravnih števil, imaš VEDNO premalo aksiomov, da bi dokazal/ovrgel vsak teorem. ALI pa imaš protisloven sistem.

Če bi uspeli samo rahlo zaostriti njegov izrek, da je vsak tak sistem kar protisloven - nič samo inkompleten - bi bilo glavobolov konec.

Začuda pa ... neke vrste neskončnost bi celo preživela! Taka, ki nima definirane aritmetike znotraj sebe. Če bi jo pobralo potem kaj drugega - ne vem.

Bom pa rekel tudi, da tale mož uporablja rahlo pretežke besede za svoje sicer zelo zanimive konstrukcije. Namreč, če bi jest imel neskončnost, sproduciram tudi perpetuum mobile prve stopnje, to tak, ki daje energijo kar v materijalnih paketih. Zmenil bi se s tistim famoznim Cantorjevim receptorjem, naj mi da televizor iz sobe 1 njegovega neskončnega hotela. Potem naj premakne iz 2 v 1 tisti TV, v 2 naj ga vzame iz 3 - itd. Vse sobe bodo imele TV, jest pa cel TV nove mase. Hočem reči - dopustiš neskončnost, pa pošejkaš tudi zakon o ohranitvi mase.

Mislim, da se je Thomas obreknil ob tole

``Does my equation have a finite or infinite number of whole-number solutions?''

Če ni neskončnosti, potem tudi ni neskončno rešitev, temveč samo zelo (zelo, zelo ...) veliko, ampak končno. Torej je tudi število dodatnih aksiomov končno. Iz tega sledi, da je sistem opisljiv, torej lahko predvidimo rezultat za dani vhodni parameter, kar se nekako ne sklada z zahtevami popolnoma naključne funkcije.

OwcA - true.

Thomas - Si pomislil tako. Če neskončno obstaja, potem je tudi neskončno vesloje(a) in neskončno mase iz katere lahko izdelamo nov TV, da bo tudi zadnja neskončna soba imela svojega. Tako kot ti.

Just a splinter in my mind

Nedavno so neki znanstveniki delali eno telovadbo, kako bi predrli dogodkovni horizont črne luknje. Opazovalec bi s tvorom strange matter (tujske snovi po naše???) naredil nekakšno luknjo v horizont in šel naprej proti fizikalni singularnosti. Vsi računi se bili okay, razen da so pozabili na to, da bi črna luknja davno prej izparela in prenehala obstajati kot črna luknja, kot bi se oni asimptotsko približali horizontu dovolj, da bi lahko začeli vrtat. Postulirali so neskončno obstojnost črne luknje, kar je napaka. No, takih vaj za moj okus delajo rahlo preveč. Kar od nekod vzamejo eno neskončnost, ki sploh nima osnove. Čeprav je desetletja (ali leta) nazaj še izgledalo, da jo ima. Take vaje so tako nesmiselne, kot računanje šahovske poteze z vkalkuliranjem figure trgovec. Ki da zna skakati kot konj in napredovati kot kmet. Take figure ni, te kalkulacije ibržne.

se pravi, da lahko punci rečeš, da je antikvarkistična?

Na tle maš tale bluz!

Tole je pa obračun z njim.

Ob tej debati mi je v glavo stopu en citat:
Ah, but a man’s reach should exceed his grasp, or what’s a heaven for? (Robert Browning)

[tole spada že bolj v oddelek "Sedem umetnost", če ne misliš argumentirati -- m.]

odie - sploh nimam teh problemov. Ima jih kvečjemu avtor članka. Za katerega (članek) pa pravim, da s postuliranjem neskončnosti lahko prideš tudi do čudnih fizikalnih sklepov. Lahko pridobivaš maso iz nič, če imaš dobre veze s Cantorjevim receptorjem. Tudi en tak članek se da napisati. Samo da evidentno nima večjega pomena.