Kiszámíthatóságelméletileg a Turing-gép memóriacelláit milyen adattípusokkal indexelhetjük?

Amit belinkeltél videót az természetesen nem explicit megvalósítás, hanem explicit szemléltetése.

Amit belinkeltél wiki oldalt, részlet :

"State space

In a sense, most functions are uncomputable: there are {\displaystyle \aleph _{0}}\aleph _{0} computable functions, but there are an uncountable number ({\displaystyle 2^{\aleph _{0}}}2^{\aleph _{0}}) of possible Super-Turing functions.[3]"

Írom magyarul.

Bizonyos értelemben a legtöbb függvény kiszámíthatatlan. Kiszámíthatlan alatt azt szokták érteni ami nem számítható ki Turing géppel. Megszámlálhatóan végtelen (alef-0) kiszámítható függvény van , kontinuum végtelen sok (2^aleph-0) féle szuper-Turing géppel számítható függvény létezik.

State space azaz állapottér. Turing gép állapottere megszámlálhatóan végtelen. Egyszerűség kedvéért tekintsünk olyan Turing gépet melynek memória cellái 0 vagy 1 értéket vehetnek fel. Tudjuk hogy a Turing gép mindig véges sok memóriacellát használ fel, de ezen belül tetszőlegesen sok memóriacellát használhat fel. A Turing gép memóriájának az összes lehetséges állapotát megindexelhetjük a természetes számokkal, méghozzá bijektív leképezéssel. 1-hez rendeljük az aktuálisan nulla darab memóriacellát használó Turing gépet. 2-höz rendeljük az aktuálisan az egy darab nulla értékű memóriacellát használó Turing-gépet. 3-hoz rendeljük az aktuálisan az egy darab egy értékű memóriacellát használó Turing-gépet ... és így tovább. Vagyis a leképezés 1 --> [], 2 --> [0], 3 --> [1], amit nem írtam le hosszasan 4 --> [0,0] ... stb. Vegyük észre hogy tulajdonképpen a sorszám bináris képe a hozzá tartozó memóriacellák állapota, csak éppen a kezdeti egyest hagytuk le, tekinthetjük úgy is hogy mindig 1-essel kezdődik így kár kiírni. Ezzel beláttuk hogy megszámlálhatóan végtelen sok állapota lehet. Viszont ha megengedjük hogy ténylegesen végtelen sok memóriacella is lehet, akkor annak már megszámlálhatatlanul sok féle állapota lehet. Mint tudjuk hogy n bitnek 2^n állapota lehet, ha alef-0 bit van annak 2^(alef-1) azaz kontinuum sok állapota van. Röviden : a memóriacelláit akkor is indexelhetjük a természetes számokkal, ha a szalag hossza és tartalma aktuális végtelen.

Egyik elvi konstrukció a Zeno-gép amely egy ATM (accelerated Turing machine azaz gyorsított Turing gép). Az n-dik lépést 2^-n-iken időegység alatt hajtja végre, így véges idő alatt végtelen sok lépést hajt végre. Mint tudjuk 1/2 + 1/4 + 1/(2^n) + ... végtelen összeg pont 1. Precízebben mondva az a sorozat melynek első tagja s(1) = 2^-1 , n-ik tagja n>1 esetében s(n) = s(n-1) + 2^-n, sorozat határétéke 1. Vagyis ha a Zeno gép első műveletet 1/2 sec alatt, másidik műveletet 1/4 ... stb hajtha végre akkor 1 másodperc alatt végtelen sok műveletet hajt végre.

Másik ilyen elvi gép a CTC-ben létező gép (closed timelike curve = zárt időszerű görbe) azaz időhurokban van.

[link]

Stb.

Egyébként ezek már pusztán matematikailag is ellentmondásosak. A Zeno gép az általam írt 1 másodperc alatt végtelen sok számítást végreható változatában ha írok egy algortimust amely egy bool változót negál minden lépésnél, kezdetnek legyen igaz az értéke, majd hamis, majd megint igaz ... az értéke igaz vagy hamis lesz 1 másodperc múlva? Olyan mintha azt kérdezném hogy páros vagy páratlan a megszámlálhatóan végtelen --> ellentmodás.

Továbbá Pl :

Idealizált analóg számítógép tud hiperszámítást végezni, ha a fizika megengedi ténylegesen a valós változókat, nem csak a Turing géppel kiszámítható és nem csak a véges pontosságú aritmetikán ábrázolható és ezek valamilyen módon „kihasználhatók” hasznos (nem véletlenszerű) számításokhoz. Ez meglehetősen bizarr fizikatörvényeket igényelhet (például mérhető fizikai állandót orakuláris értékkel, például Chaitin állandóját), és megkövetelné a valós értékű fizikai érték abszolút pontosságú mérésének képességét,az e fajta precíziós mérés a fizikai ismereteink szerint elméletileg is kivitelezhetetlen.

... stb.

A turing gépnek nincsenek memóriacellái. Ha lennének, akkor sem adattípussal lenne indexelve, hanem halmazokkal. (Az állapotai például azzal vannak.)

Ha meg akarsz tudni valamit, kérdezd meg. Ha valami konkrétat akarsz megtudni, tedd fel a kérdést pontosan, de úgy, hogy értelme is legyen.

Ha általánosság érdekel, akkor tedd fel a kérdést általánosan (pl: kérdezd meg azt, ami érdekel).

Egyébként meg ne trollkodj.