Eldönthető-e polinomidőben, hogy ez a Q* -> N algoritmus megáll-e?

Abból indulnék ki, hogy (tízes számrendszerben) annak a valószínűsége, hogy egy számjegy 0, 1/10, szóval a valószínűség igencsak konvergál a 0-hoz.

Persze mondható olyan irracionális szám, ami nem tartalmaz 0-t, ilyen az 1,12112111211112..., ahol két kettes között egyre több 1-es található, és erről bebizonyítható, hogy irracionális.

Első körben arra van szükségünk, hogy az adott számról tudjuk, milyen „sűrűn” helyezkednek el benne a nullák. Persze ez sem garancia semmire, mert lehet olyan irracionális számot mondani, ami tele van 0-val, mégsem fog soha megállni, például 1,20300500001600000..., vagyis ha a lépett számjegy n, akkor utána (n-1) darab nullát teszünk, és ez a módszer variálható úgy, hogy irracionális számunk legyen.

Általánosságban azt mondanám, hogy polinomidő alatt nem lehet megmondani, hogy a program lefut-e.

A másik kérdésnél mit értesz konvertálás alatt?

Mi az a polinomidő ebben az esetben? Értelmetlen!!!

A végrehajtási idő a számok hosszának (ami végtelen!!!) polinomja???

Vagy a számoknak, amiből gyököt vonunk? Itt meg SEMMILYEN összefüggés nincs.

Értelmetlen.

Nem jó a példád mert π = 3.141592653589793238462643383279502884...

Ezért a te f függvényed esetében f(π) = 15926535897932384626433832795 .

kezdjük ott, hogy nem világos az sem hogy veszed azokat az irracionális számokat a pí és a prímes eseteken kívül. Ha abból indulsz ki, hogy bármelyik irracionális számot elő lehet állítani valamilye algoritmussal akkor tévedésből indulsz ki.

Az algoritmusok halmazának számossága megszámlálhatóan végtelen azaz alef-0, az irracionláis számok halmazának számossága kontinuum azaz alef-1. Az alef-1 magasabb rendű végtelen mint az alef-0.

A többszörös, nagyobb végtelenek között fogalmakkal óvatosan kell bánni, ezért számosságot írtam mert így precíz a matemamtika nyelvén. Bármely a matematikában szokásos értelemben létező számot mint mennyiséget tekintve azt felülmúló mértékben "kisebb" azon irracionális számok halmaza melyre létezik egyáltalán algoritmus mely előállítaná. Természetesen itt megengedőbb vagyok az algoritmusfogalom tekintetében, azt is elemnek tekintem ami az algortimus produktuma ami végtelen futási idejű lenne, mint pl a π mint szám előállítása végtelen futási idejű. Nem is maga az kész kiszámított eredményt veszem figyelembe, hanem elemként veszem maga az algoritmus létezését amibe tart mint határérték a π közelítésében maga a π-t. Ilyen értelemben van egy csomó szám melyre nincs algoritmus sem, csupán a létező algoritmusok számossága és az irracionális számok számosságából adódóan.

Tulajdonképpen egy-egy sorozat képezhető bármely irracionális szám számjegyeiből ahol a sorozat tagjai ezen számjegyek.

Az algoritmikus információelmélet foglalkozik többek között kiszámíthatóan generált objektumok információi közötti kapcsolattal. Ez esetben maga a számjegyek mint generált sorozat. A π-ből a gyök(2)-ből stb. előállíttott sorozat tömöríthető maga az algoritmussal. Ha az irracionális szám számjegyei sztochasztikusan generáltak akkor nincs rá algoritmus mely előállítaná. Bár ez elméleti matematika/informatika, mivel gyakorlatban véges hosszú sorozatokat tud tárolni egy gép. Így egy számítógépen egy véletlenszerűen generált sorozatra nincs rövidebb leírás mint önmaga, azaz nem tömöríthető. Az hogy akkor honnan veszünk sztochasztikusan generált sorozatot gyakorlatilag, a kvantummechanika tartalmazza axióma szinten hogy létezik objektív véletlen, de ez már egy más terület. Gyakorlatilag mindig véges hosszú egy ilyen mérési sorozat.

Továbbá nem ugyanaz hogy definiálok egy számot és nem ugyanaz ha algoritmust is adok a kiszámítására.

Például van a busy beaver magyarul elfoglalt hód. Ami az elméleti informatikában egy játék melynek célja, egy adott méretű befejező program megtalálása, ami a lehető legtöbb kimenetet produkálja. Mivel könnyen lehet végtelen ciklust csinálni, így örökké futó programot írni, ezért ezen programok ki vannak zárva a versenyből. A részletekbe nem belemenve megemlítem, hogy mindössze csak 5 állapotú

gép esetében már nem ismert melyik program a hódbajnok. jelöljük Σ(n)-el az n állapotú gép hódbajnok amennyi kimenetet produkált. Ekkor ez a Σ(n) függvény létező függvény, de matemaitai értelemben is kiszámíthatatlan és aszimptotikusan gyorsabban nő bármely kiszámítható függvénynél.

Ide vonatkozó irracionális számok tekintetében pedig példának mondom algoritmikus információelmélet számítástechnikai részterültén lévő Chaitin's konstansokat vagy máshogy mondva Chaitin-Ω-ákat vagy még máshogy mondva megállási valószínűségeket. Bizonyított, hogy az értékük nem számítható ki.

Kiszámítható esetben pedig attól függ hogy mit tudunk az algortitmusról, illetve tudjuk e addig számolni amíg 0 nem lesz. Ott se biztos hogy tudjuk bizonyítani minden esetben hogy lesz e 0.

"a prímek négyzetgyökeinek halmazán (garantáltan irracionális számok) mekkora a kimenetek várható hossza a konvertálás után? "

Sejtésem szerint 7-nél nagyobb prím esetében mindig rövidebb lesz a hossz mint maga a prím értéke.

"Mi az összefüggés azon számok között, melyeknél nem áll meg az algoritmus?"

Így prímek négyezgyökei esetben nincs mit erről beszélni, ha jó a sejtésem.

"Akik nem értenék a problémát, azoknak leírom"

Ott valami félrement.

A pi esetében a 0-át nem vetted bele, én így azt nem vettem bele. Az más kérdés hogy rossz az a példád amit már írtam.

A 0-át nem veszem bele a képzett listába, első 15 prímszám:

prim(1) = 2 -> 1.4142135623730950488016887242096980785697 -> [4, 1, 4, 2, 1, 3, 5, 6, 2, 3, 7, 3] 12 hossz

prim(2) = 3 -> 1.7320508075688772935274463415058723669428 -> [7, 3, 2] 3 hossz

prim(3) = 5 -> 2.2360679774997896964091736687312762354406 -> [3, 6] 2 hossz

prim(4) = 7 -> 2.6457513110645905905016157536392604257103 -> [4, 5, 7, 5, 1, 3, 1, 1] 8 hossz

prim(5) = 11 -> 3.3166247903553998491149327366706866839271 -> [6, 6, 2, 4, 7, 9] 6 hossz

prim(6) = 13 -> 3.6055512754639892931192212674704959462513 -> [5, 5, 5, 1, 2, 7, 5, 4, 6, 3, 9, 8, 9, 2, 9, 3, 1, 1, 9, 2, 2, 1, 2, 6, 7, 4, 7] 27 hossz

prim(7) = 17 -> 4.1231056256176605498214098559740770251472 -> [1] 1 hossz

prim(8) = 19 -> 4.3588989435406735522369819838596156591370 -> [8, 9, 8, 9, 4, 3, 5, 4] 8 hossz

prim(9) = 23 -> 4.7958315233127195415974380641626939199967 -> [8, 3, 1, 5, 2, 3, 3, 1, 2, 7, 1, 9, 5, 4, 1, 5, 9, 7, 4, 3, 8] 21 hossz

prim(10) = 29 -> 5.3851648071345040312507104915403295562951 -> [6, 4, 8] 3 hossz

prim(11) = 31 -> 5.5677643628300219221194712989185495204764 -> [6, 4, 3, 6, 2, 8, 3] 7 hossz

prim(12) = 37 -> 6.0827625302982196889996842452020670620850 -> [2, 5, 3] 3 hossz

prim(13) = 41 -> 6.4031242374328486864882176746218132645204 -> [4, 2, 3, 7, 4, 3, 2, 8, 4, 8, 6, 8, 6, 4, 8, 8, 2, 1, 7, 6, 7, 4, 6, 2, 1, 8, 1, 3, 2, 6, 4, 5, 2] 33 hossz

prim(14) = 43 -> 6.5574385243020006523441099976360016279270 -> [8, 5, 2, 4, 3] 5 hossz

prim(15) = 47 -> 6.8556546004010441249358714490848489604606 -> [4, 6] 2 hossz

"nem feltétlenül kell a prímes megszorítás, csak így a négyzetszámok triviálisan nem okoznak végtelen ciklust"

A négyzetszámok négyzetgyökei egész számok, így a tizedespont után mindig csupa 0-ák lesznek, 0-ánál definíció szerint megáll az algoritmus, nem értem miért okoznának végtelen ciklust.

"És a 31 prím gyöke 5.567764... (a végződő 0 számjegyet is beleszámítva) egy 38 hosszú számot ad eredményül."

Ott valamit eltoltál, mert 7 hosszú lista lesz a végződő 0-át nem beleszámítva. A 13-nál benéztem ott hosszabb, javítom a sejtésemet 7 helyett 13 feletti prímre. Maga a trend igaznak lászik.

"A pít még egyszer kiszámoltam, és [1, 5, 3, 9, 2, 4, 3, 9, 7, 3, 1, 0]-t adott eredményül a programom."

Akkor rossz a programod például a listába a 3.-ik szám helyén 9-nek kéne lennie. Nulla pedig csak később van.

Az én programom jól számolta, de ha nem hiszel nekem :

[link]

[link]

[link]

"Egyébként a foglalt hód probléma nagyon érdekesnek hangzik. Tudsz hozzá linket dobni?"

[link]

"A Chaitin konstansról annyit, hogy matematikailag valóban nem kiszámítható, de (szerintem) egy amolyan Monte-Carlo módszerrel (ld. Monte-Carlo integrálás) megközelíthető."

A Chaitin Ω első N bitjének ismeretében kiszámítható a leállítási probléma minden N méretig terjedő programra . Legyen N méretű az a p program , amelyre a leállítási feladatot meg kell oldani . A program lefut mindaddig, amíg meg nem áll addig amíg elegendő valószínűséggel járul hozzá az első N bithez . Ha a p program ekkor még nem állt meg, akkor soha nem is fog, mivel a leállási valószínűséghez való hozzájárulása az első N bitet érintené. Mivel a leállási probléma általában nem oldható meg ezért a Chaitin konstans első néhány bitjét kivéve nem számítható.

Minden leállási valószínűség normális, transzcendens és valós szám. Minden leállási valószínűség Martin-Löf véletlenszerű , vagyis nincs olyan algoritmus, amely megbízhatóan kitalálná a számjegyeit (kiévéve esetleg az első néhány számjegyét). Minden kiszámítható függvény eleme a kiszámíthatóan felsorolható függvények halmazának, ami viszont nem számítható halmaz. Ezen halmaz elemei kiszámításának nehézsége egyenértékű a leállási problémával.

Találtam egy prímszámot, amelynek négyzetgyöke 1200 ciklus alatt jut el a nullához!

Nem próbálgatással, hanem célirányos számítással találtam. De hogyan?

Szabad a gazda? :D

Úgy értendő, hogy majdnem 1200* léptetjük előre a mutatót, (az aktuális számjegy értékével,) mire nullához érkezünk.

A prímszám pedig: next_prime((10^1000-10)/81) =

1234567901234567901234567901...6790123456790123456790123462947 (999 számjegyű prímszám), ennek négyzetgyöke pedig:

111111... (995 db 1-es) ...111111388170555555... 989 db 5-ös ...555555210...

(Az 500. 1-es után van a tizedespont.)

17:53

Ja ok, így írjon az ember nem szólnak hogy rosszul értettem.

Csak legelső jegynél léptettem annyival mint maga a legelső számjegy.