Stevilo se ne konča(PI)

[Maedhros]

Kot je že Roman dejal, so vsa realna števila limite konvergentnih zaporedij. Zato je vsako tako zaporedje možno jemati kot algoritem. Iz tega vidika kvečjemu tvoje izjave ne držijo.

Če bi to držalo, potem je Turingov dokaz in nasploh delo matematikov, ki se ukvarjajo s teorijo izračunljivosti in so iznašli več sto formalizacij koncepta algoritma, za katere pa vse velja kar sem omenil, napačno. Možno je, samo potem te čaka Turingova nagrada.

Sedaj mi je jasno, kaj misliš s tem, da realno število ni izračunljivo. Pač v smislu definicije iz omenjenega Turingovega članka (The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means).

Ja... lahko pa pogledaš kar na wikipedijo, kjer piše preprosto:
Although the set of real numbers is uncountable, the set of computable numbers is countable and thus most real numbers are not computable.

Omenil pa si, da je število \(\pi\) izračunljivo v smislu omenjene definicije (da obstaja končen zapis). To pa ne drži. Tudi tega števila (ker je iracionalno) ni možno zapisati bodisi s končnim številom decimalnih mest bodisi s številom decimalnih mest, ki se periodično ponavlja, in torej ni izračunljivo s končnim številom korakov.

Mogoče ga je zapisati kot končen algoritem (v smislu končnega formalnega zapisa Turingovega stroja, npr.) in s tem algoritmom lahko v končnem številu korakov izračunamo njegovo poljubno decimalko, kar je dovolj, da ga lahko proglasimo za izračunljivo število. Tudi wiki se v tem strinja z mano (kar je v tem primeru dovolj):
The computable numbers include many of the specific real numbers which appear in practice, including all algebraic numbers, as well as e, \(\pi\), and many other transcendental numbers.

[kren]

Tisto da so vsa realna stevila limite zaporedij bo ze drzalo, vendar so limite realnih zaporedij o katerih (ce se prav spomnem dokaza) spet ne vemo kaj dosti.

[Roman]

Kren, samo primer:
\(e = \lim_{n\to\infty} \left(1+\frac{1}{n}\right)^n\)
Vsi členi zaporedja so racionalni.

[Roman]

Če bi to držalo, potem je Turingov dokaz in nasploh delo matematikov, ki se ukvarjajo s teorijo izračunljivosti in so iznašli več sto formalizacij koncepta algoritma, za katere pa vse velja kar sem omenil, napačno. Možno je, samo potem te čaka Turingova nagrada.

Kaj si želel povedati? Saj s povedanim nisi zavrnil Shrinkove ali moje trditve.

[shrink]

Kot je že Roman dejal, so vsa realna števila limite konvergentnih zaporedij. Zato je vsako tako zaporedje možno jemati kot algoritem. Iz tega vidika kvečjemu tvoje izjave ne držijo.

Če bi to držalo, potem je Turingov dokaz in nasploh delo matematikov, ki se ukvarjajo s teorijo izračunljivosti in so iznašli več sto formalizacij koncepta algoritma, za katere pa vse velja kar sem omenil, napačno. Možno je, samo potem te čaka Turingova nagrada.

Kot sem že poudaril, je predvsem odvisno od tega, kako so pojmi definirani. Če definiramo izračunljivost v Turingovem smislu in jemljemo algoritem kot Turingov stroj, potem drži, kar si napisal. Ker pa v svojem začetnem postu nisi pojmov dovolj dobro definiral, lahko povsem upravičeno na zadevo gledam drugače. Osebno je zame algoritem vsak "opis postopka pri reševanju nekega problema, podan v obliki niza navodil", zato sploh ni nujno, da gre za računski stroj ali kaj podobnega, temveč lahko tudi za nek predpis oz. navodilo (kar zaporedje je), ki vodi do rešitve.

Zato so tvoje sarkastične opazke popolnoma odveč.

Sedaj mi je jasno, kaj misliš s tem, da realno število ni izračunljivo. Pač v smislu definicije iz omenjenega Turingovega članka (The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means).

Ja... lahko pa pogledaš kar na wikipedijo, kjer piše preprosto:
Although the set of real numbers is uncountable, the set of computable numbers is countable and thus most real numbers are not computable.

Heh, menim, da sem matematično dovolj podkovan, da se ne ustrašim niti članka izpod Turingovega peresa. Vseeno hvala za namig.

Omenil pa si, da je število \(\pi\) izračunljivo v smislu omenjene definicije (da obstaja končen zapis). To pa ne drži. Tudi tega števila (ker je iracionalno) ni možno zapisati bodisi s končnim številom decimalnih mest bodisi s številom decimalnih mest, ki se periodično ponavlja, in torej ni izračunljivo s končnim številom korakov.

Mogoče ga je zapisati kot končen algoritem (v smislu končnega formalnega zapisa Turingovega stroja, npr.) in s tem algoritmom lahko v končnem številu korakov izračunamo njegovo poljubno decimalko, kar je dovolj, da ga lahko proglasimo za izračunljivo število. Tudi wiki se v tem strinja z mano (kar je v tem primeru dovolj):
The computable numbers include many of the specific real numbers which appear in practice, including all algebraic numbers, as well as e, \(\pi\), and many other transcendental numbers.

To je spet v povezavi z omenjeno definicijo izračunljivosti in z algoritmi, ki so tako definirani. V teoriji števil pa pojem izračunljivosti sploh ni potreben. Tam je zgolj govora o limitah in njihovem obstoju oz. vrstah in njihovi konvergenci.

Skratka: Ni ustrezno reči (kakor si sam dejal v enem od prvih postov), da poznamo končen zapis za število \(\pi\); poznamo zgolj končen zapis za njegov približek. Za izračun njegove natančne vrednosti bi potrebovali neskončno št. korakov, kar z računskim strojem ni izvedljivo. Matematika pa se temu elegantno ogne s pojmom limite ali konvergence. In zgolj to sva z Romanom želela poudariti. Izračunljivost je v tem smislu zelo relativen pojem, predvsem pa stvar definicije.

[Maedhros]

Sakrastičen? Mislim da se z Romanom ne zavedata prav dobro, kako zelo radikalne so vajine trditve.

V začetku 20. stoletja so matematiki razmišljali o mejah (mehanske) izračunljivosti. Iskali so nek okvir, v katerem bi lahko zapisovali natančna navodila, postopke za izračun česarkoli že ... algoritme pač. Turing je sestavil slavni Turingov stroj, Alonzo Church lambda račun (LR), nek drug matematik pa je predlagal tezo, ki je od tedaj poimenovana z njunima imenoma: "vse kar je izračunljivo, je mogoče izračunati na Turingovem stroju".

Zakaj ravno na TSju in ne recimo LRju? V bistvu je vseeno, ker sta si po moči ekvivalentna - kar je mogoče izračunati s TSjem, je namreč mogoče tudi v LRju.

Od tistih časov vse do danes matematiki iščejo nek model računanja, ki bi bil močnejši od TSja, v katerem bi bila npr. vsa realna števila izračunljiva. Brez uspeha. Predlaganih je bilo že več 100 različnih modelov, od zelo kompleksnih do silno preprostih, vendar se je vedno izkazalo, da so ekvivalentni ali šibkejši od TSja. S tem Church-Turingova teza seveda ni dokazana, vendar je zaradi toliko neuspelih poskusov splošno sprejeta kot veljavna.

Če menita, da bosta v 5 minutah rešila problem, ki so mu ljudje posvetili celotne kariere, potem... no ja, verjetnost za kaj takega je pač infinitizemalno majhna.

Kar se pa tiče omenjenih limit zaporedij, jih je mogoče zapisati za začetek kot psevdokodo, s katero bi konstruirali vedno natančnejše približke nekega realnega števila, ta pa je seveda prevedljiva v navodila, za delovanje TSja... in tako velja pač, da zaradi števnosti takih algoritmov večina realnih števil ostaja neizračunljiva.

shrink, na koncu si omenil še, da je št. PI izračunljivo samo glede na določeno (Turingovo) definicijo pojma izračunljivosti. Pozabljaš pa, da zaradi Church-Turingove teze to velja splošno, za kakršnokoli poznano definicijo.

Na PI bi drugače lahko pogledali še na nek drug način. Ker poznamo končen algoritem za njegovo generiranje lahko rečemo, da je njegova kompleksnost Kolmogorova (količina algoritmične informacije) končna - kar bi nekdo, ki bi ga poznal le v decimalnem zapisu (recimo prvih 1000 decimalk) težko sklepal...

[Roman]

Res ne vem, v čem je problem oziroma nesporazum. In kaj bi bilo radikalnega v najinih trditvah.

Če je definicija izračunljivega števila ta, da jih je mogoče izračunati na izbrano natančnost s končnim algoritmom (se pravi v končno mnogo korakih nekega seznama posameznih operacij), potem je jasno, da lahko izračunamo samo nekaj decimalnih mest tega števila, nikakor pa ne vseh. In to sploh ni odvisno od metode ali orodja.

Na PI bi drugače lahko pogledali še na nek drug način. Ker poznamo končen algoritem za njegovo generiranje

Jaz ne poznam nobenega takega algoritma. Generiramo lahko samo približek, nikakor pa ne celega števila pi.

[Maedhros]

Res ne vem, v čem je problem oziroma nesporazum. In kaj bi bilo radikalnega v najinih trditvah.

shrink meni, da obstaja nek algoritem, s katerim bi bilo mogoče izračunati *vsa* realna števila, kar pa ostro nasprotuje rezultatom teorije izračunljivosti. Če bi to držalo, bi obrnilo na glavo celotno podpodročje matematike/znanosti - se ti to ne zdi radikalno?

Če je definicija izračunljivega števila ta, da jih je mogoče izračunati na izbrano natančnost s končnim algoritmom (se pravi v končno mnogo korakih nekega seznama posameznih operacij), potem je jasno, da lahko izračunamo samo nekaj decimalnih mest tega števila, nikakor pa ne vseh.

Hmm.., izračunamo jih lahko *poljubno* mnogo; drugače rečeno, racionalno število, ki ga izračunavamo, je lahko poljubno blizu željenemu realnemu številu. S tem se približamo izračunu celotnega števila kolikor je sploh mogoče.

Zgoraj si napisal enačaj med limito zaporedja in število e, samo nisem prepričan, da je bilo to glede na tvoje razmišljanje sploh pravilno. Pri limiti gre namreč za zelo podobno idejo kot pri izračunljivosti števil, ker je definirana z epsilon okolico, ki določa *poljubno* majhno razliko med realnim številom e in njegovim približkom z naraščanjem n-ja...

Jaz ne poznam nobenega takega algoritma. Generiramo lahko samo približek, nikakor pa ne celega števila pi.

Najbolj preprost algoritem bi bil recimo tale:

Koda: Izberi vse

// najprej inicializiramo nekaj spremenljivk:
imenovalec = 1, PI = 4, epsilon = 100, i = 1...

// nato v zanki izračunavamo vrsto 4 - 4/3 + 4/5 - 4/7 +... 
dokler ( epsilon > željena_natančnost ) ponavljaj
{
	stariPI <- PI
	imenovalec <- imenovalec + 2
	PI <- PI + (-1)^i * 4/imenovalec
	epsilon <- |PI - stariPI|
	i <- i + 1; 	        
}
izpiši( PI ) 

Približek je lahko poljubno dober, tako kot je pri limiti člen zaporedja pri velikem n poljubno blizu določenemu realnemu številu.

[Roman]

shrink meni, da obstaja nek algoritem, s katerim bi bilo mogoče izračunati *vsa* realna števila

Tega nisem zasledil. Si lahko bolj natančen?

racionalno število, ki ga izračunavamo, je lahko poljubno blizu željenemu realnemu številu.

Ne, če je to poljubno nič.

S tem se približamo izračunu celotnega števila kolikor je sploh mogoče.

Ni, s "kolikor je sploh mogoče" v matematiki ne boš daleč prišel.

Zgoraj si napisal enačaj med limito zaporedja in število e, samo nisem prepričan, da je bilo to glede na tvoje razmišljanje sploh pravilno. Pri limiti gre namreč za zelo podobno idejo kot pri izračunljivosti števil, ker je definirana z epsilon okolico, ki določa *poljubno* majhno razliko med realnim številom e in njegovim približkom z naraščanjem n-ja...

To ni res. Z epsilonom in delto preizkušamo konvergentnost zaporedja. Limita je isto kot stekališče, ni približek, ampak je dejansko neskončno-ti člen zaporedja. Velja enačaj. Podobnost z izračunljivostjo je samo v mejah epsilon/delta.

Najbolj preprost algoritem bi bil recimo tale...

Približek ne more biti poljubno dober, ampak je za izbrano natančnost možno izračunati približek s končno mnogo iteracijami. Treba je razlikovati med "dovolj dober" (sem spada izračunljivost) in realnim številom samim.

[Aniviller]

Koda: Izberi vse

// najprej inicializiramo nekaj spremenljivk:
imenovalec = 1, PI = 4, epsilon = 100, i = 1...

// nato v zanki izračunavamo vrsto 4 - 4/3 + 4/5 - 4/7 +... 
dokler ( epsilon > željena_natančnost ) ponavljaj
{
	stariPI <- PI
	imenovalec <- imenovalec + 2
	PI <- PI + (-1)^i * 4/imenovalec
	epsilon <- |PI - stariPI|
	i <- i + 1; 	        
}
izpiši( PI ) 

Približek je lahko poljubno dober, tako kot je pri limiti člen zaporedja pri velikem n poljubno blizu določenemu realnemu številu.

Joj, a nisi mogel najti kaksne bolj konvergentne variante. Tale vrsta "skoraj" divergira

[Maedhros]

Hehe, imaš prav. Samo je pa ena izmed najbolj preprostih in čisto dovolj dobra za moj namen.

[Maedhros]

shrink meni, da obstaja nek algoritem, s katerim bi bilo mogoče izračunati *vsa* realna števila

Tega nisem zasledil. Si lahko bolj natančen?

Lahko:

Za vsako iracionalno število obstaja "algoritem za njegovo generiranje"

Z epsilonom in delto preizkušamo konvergentnost zaporedja. Limita je isto kot stekališče, ni približek, ampak je dejansko neskončno-ti člen zaporedja. Velja enačaj. Podobnost z izračunljivostjo je samo v mejah epsilon/delta.

V definiciji limite ni nobene neskončnosti, samo epsiloni... Kolikor vem, matematiki radi rečejo, da se določeni števili razlikujeta za poljubno malo (poljubno majhen epsilon) in s tem mislijo, da sta si enaki. Tako sta npr. 0.9999... in 1.0 enaki. Omenjanje neskončnosti ni potrebno.

Približek ne more biti poljubno dober, ampak je za izbrano natančnost možno izračunati približek s končno mnogo iteracijami. Treba je razlikovati med "dovolj dober" (sem spada izračunljivost) in realnim številom samim.

Glej... neko število je izračunljivo, če obstaja nek algoritem s katerim v končnem številu korakov izračunamo njegovo n-to decimalko, kjer je n poljubno velik. Za število PI to velja (kar je pokazal svoje čase že Turing) zato je to pač izračunljivo. Saj to menda je jasno, no...

Še z drugega zornega kota:
"For example, the KC [Kolmogorov complexity] of pi is quite small as is the KC of a fractal."
http://www.cs.unm.edu/~saia/infotheory.html

In ker KC ni nič drugega kot dolžina programa za generiranje nekega niza (v tem primeru števila PI), lahko zaključim, da je tak program pač končen.

Drugače so to standardni zaključki informacijske znanosti in osnov računalništva, ki so splošno sprejeti...

[Roman]

Lahko:

Za vsako iracionalno število obstaja "algoritem za njegovo generiranje"

Že, že, ampak pod "generiranje" je bil mišljen izračun približka.

V definiciji limite ni nobene neskončnosti, samo epsiloni...

Narobe. Limita je vedno limita zaporedja, zaporedje pa je definirano kot neskončna množica števil v predpisanem vrstnem redu. Definicija limite zaporedja pa je, da je to število s posebno lastnostjo, da za vsako, še tako majhno število epsilon obstaja dovolj pozen člen zaporedja, da se vsi njegovi naslednji členi (neskončno jih je) od limite razlikujejo za manj kot epsilon.

Kolikor vem, matematiki radi rečejo, da se določeni števili razlikujeta za poljubno malo (poljubno majhen epsilon) in s tem mislijo, da sta si enaki.

Tudi to ni res. Epsilon je vedno različen od nič. Tvoja trditev se sliši nekako takole, da sta diferenciala dx in dy v resnici enaka nič, ampak v tem primeru bi bilo odvajanje funkcij nemogoče.

Omenjanje neskončnosti ni potrebno.

Pač.

Glej... neko število je izračunljivo, če obstaja nek algoritem s katerim v končnem številu korakov izračunamo njegovo n-to decimalko, kjer je n poljubno velik.

Ne vem, zakaj ponavljaš definicijo? Sem jo jaz narobe zapisal? Toda z izračunljivostjo pridemo le do približkov.

Saj to menda je jasno, no...

Upam, da res.

In ker KC ni nič drugega kot dolžina programa za generiranje nekega niza (v tem primeru števila PI), lahko zaključim, da je tak program pač končen.

Da, ampak rezultat je (samo) približek.

Drugače so to standardni zaključki informacijske znanosti in osnov računalništva, ki so splošno sprejeti...

Prav, ampak nauči se razlikovati med računalništvom in matematiko. V računalništvu ni realnih števil, tip "real" v Pascalu ni realno število v matematičnem smislu.

[Maedhros]

Lahko:

Za vsako iracionalno število obstaja "algoritem za njegovo generiranje"

Že, že, ampak pod "generiranje" je bil mišljen izračun približka.

In to je v nasprotju z deli Turinga in horde matematikov, ki so mu sledili.

Prav, ampak nauči se razlikovati med računalništvom in matematiko. V računalništvu ni realnih števil, tip "real" v Pascalu ni realno število v matematičnem smislu.

Poleg tega da so to osnove računalništva, so tudi osnove matematike. Goedel in Turing sta tesno prepletena (izračunljivost in dokazljivost sta dve plati iste medalje).

Kar se pa tiče neskončnosti sem bil očitno preveč izpostavljen trditvam oblike "neskončnost je magija", kar je pred časom trdil sam K.F.Gauss. Še vedno mislim, da je omenjanje neskončnosti povsem nepotrebno in dobro vem, da se del matematikov s tem strinja - imenujejo se intuicionisti, če se ne motim.

Drugače mi pa zmanjkuje časa, da bi se poglabljal tule v podrobnosti (fax pač jemlje čas). Mogoče kdaj drugič. Zaenkrat pa ostajam pri svojih trditvah, da:
a) večina realnih števil je neizračunljiva
b) PI, e, koren(2) in podobna števila *so* izračunljiva, torej zapisljiva s končnim algoritmom

Poleg tega pa seveda trdno stojim za Church-Turingovo tezo, ki postavlja zgornjo shrinkovo trditev v nič kaj zavidljiv položaj.

Mimogrede, na naslednjem linku je kar zanimiv pogovor o teh zadevah:
http://www.nrich.maths.org/askedNRICH/edited/1172.html

[kren]

Roman sej najbrz je nesporazum samo v definicijah, izracunljivo stevilo ni isto kokr da bi reku da obstaja zaporedje ki tja konvergira. za izracunljivost mora obstajat se koncen algoritem ki bi nam to stevilo generiral, to pa je strozji pogoj.

Maedhros, sam zakaj tocno vecina realnih stevil ni izracunljiva? ne vidim zakaj za poljubno realno stevilo naj ne bi bilo mozno najti koncnega algoritma ki bi ga generiral. no sej tudi razloga v prid temu ne vidim, sam tko.. kako so tisti ljudje to argumentiral?