Legalább hány függvény/operátor/metódus lenne szükséges, hogy az összes többit definiálhassuk velük?

Hát… Szerintem kontinuum-sok legalább kell, de nem vagyok benne biztos, hogy az elég is.

Legalábbis, ha jól értem a kérdést…

A kérdés teljes mértékben értelmetlen.

"függvény/operátor/metódus....."

"....hány olyan alapfüggvény létezik, amivel az összes többit leírhatnánk a logaritmuson keresztül a szögfüggvényeken át egészen az integrálásig"

Szemmel láthatólag nem vagy tisztában az elemi matematikával. Ez a kérdés olyan, mintha azt kérdeznéd hogy hányfajta villanykörtéből lehetne felépíteni az összes világító reklámtáblát, mókust és még a négyzetesen integrálható magú operátorokat is.

Első megközelítésben 8 operátorral (avagy metódussal), de nevezzük egyszerűen csak műveletnek.

Ennek egy számítógépes implementációja a Brainfuck Turing teljes programozási nyelv. Lást: [link]

Turing gép:

„A Turing-gép fogalmát Alan Turing angol matematikus dolgozta ki 1936-ban megjelent cikkében a matematikai számítási eljárások, algoritmusok precíz leírására, tágabb értelemben pedig mindenfajta „gépies” problémamegoldó folyamat, például az akkoriban még nem létező számítógépek működésének modellezésére. Erre az időszakra, a második világháború környékére tehető az ilyesfajta, a számítási eljárásokat azok különféle modelljein keresztül vizsgáló kutatások fellendülése, melyek végül a valódi számítógépek építésébe torkollottak (Turing maga is részt vett egy valódi gép, a Colossus megépítésében).

A Turing-gép úgynevezett absztrakt automata: a valóságos digitális számítógépek nagyon leegyszerűsített modellje (részletesebben ld. következő fejezet). További jelentőségét az ún. Church–Turing-tézis adja, amely szerint a Turing-gép egy univerzális algoritmikus modell (ld. lentebb). Az ilyen egyszerű számítógépmodellek matematizált elméleteivel a matematika számítógép-tudománynak nevezett eléggé fiatal tudományágának olyan részterületei foglalkoznak, mint például a számításelmélet.”

[link]

Valójában akkor lenne a Brainfuck Turing teljes ha nem 30 000 memóriacellája lenne hanem végtelen. Na jó de csak véges sok lehet, ha akarunk „építeni” egyet otthonra. Egyrészt ez egy matematikai modell amiben lehet végtelen, a másik hogy végtelen de ebből csak véges sokat használunk fel mindig. A gyakorlatban lehet véges sok, de ha kevés akkor tudjuk bővíteni mondjuk van 200 giga memóriám, de ha nem elég akkor még veszek hozzá. A memóriát szemléletesebb, ha egy szalagnak képzeljük el, amiben lehet jobbra vagy balra mozogni és lehet róla olvasni meg lehet rá írni, ha nem elég hosszú, akkor tudunk hozzá toldani amennyi kell.

Ezt a 8 műveletet le tudom faragni 7-re ha nagyon akarom. A kivonás műveletet ki tudom váltani összeadás művelettel ha kettes komplemens szerint használom a számokat. Viszont ennél jobbat tudok, legyen csak 2 műveletem melyből leírható az összes függvény amit egyáltalán le lehet írni bárhogy is. Azt már beláttuk hogy a Brainfuck géppel leírható, erre vezemem vissza amit nevezzük Brainfuck2 gépnek.

Egy olyan Brainfuck2 gépem legyen mely csak 2 műveletet ismer.:

C : ciklikusan permutál

E : értelmez

A Brainfuck gép utasításkészletét permutálja ciklikusan a „C”

Pl. : „< > + - . , [ ]” a sorrend erre alkalmazva a C-t:

„> + - . , [ ] <” lesz belőle.

Az E művelet a ciklikus permutáció legbaloladlibb elemét válassza ki.

„> + - . , [ ] <” esetében a „>” lesz.

Egyszerűség kedvéért először úgy képzeljük el a Brainfuck2 gépet hogy a Brainfuck2 nyelvet lefordítja Brainfuck nyelvre melyet végrehajt egy Brainfuck gép. (Másodjára) igazából ne így képzeljük el, a Brainfuck2 gép hajtja végra a Brainfuck2 nyelv által leírt utasításokat, a Brainfuck2 gépbe nincs beleépítve egy Brainfuck gép, hanem a Brainfuck2 gép egy olyan állapotgép melynek a C utasítás értelmezése a korábbi utasításoktól függ, vagyis a C utasítás 8 különböző állapotba lehet. Ezt le tudom redukálni MINDÖSSZE 1 DB utasítássá, ez viszont mindenkinek egy kis önálló agytorna, hogy hogyan.

Második megközelítésben viszont a legelső válaszoló leírta a helyes és rövid választ.

Egyszerűség kedvéért vegyük az R -> R-be (valósból valósba) leképező egyváltozós függvények „H” halmazát, ez az összes függvénynek csak egy részhalmaza, de ahhoz hogy belássuk, hogy igazat írt elég ezt tekinteni.

Egy ilyen f(x) függvényt tekinthetjük valós számpárok halmazának ahol igaz minden x és y valós számra, hogy f(x)=y amit (x,y) számpárnak tekinthetjük. Minden x-nek egy y párja lehet vagy másként egy függvény egy helyen nem vehet fel egyszerre 1-nél több értéket.

A „H” halmazból válasszunk teljesen véletlenszerűen egy függvényt. Elárulom, hogy 0 valószínűséggel lesz olyan függvény ami leírható zárt alakba. Semmilyen eddig ismert függvénnyel nem lesz leírható, semmilyen algoritmussal sem. (***) Azt hogy miért ahhoz mélyebben meg kell érteni a végtelen fogalmát és kell érteni a valószínűség számításhoz is. Ehhez rengeteg előismeretre is szükség van. A lényeg nagyon röviden, hogy ugyan végtelen sok függvényt le tudunk írni algoritmikusan, ehhez képest az összes függvény halmaza még végtelenebb. Ha összehasonlítom a két végtelent a kettő „arányában” megegyezik azzal mintha a „kisebb” végtelen helyett üres halmazt veszek. Vagy másként több függvény létezik mint amennyi algoritmus.

(***)

Pongolán megfogalmaza, személetes példával:

Miért is lenne pont az mint egy eddig ismert függvény? Szemléletesen, de nem precíz magyarázatként ahhoz hasonló mintha lenne egy 10 oldalú „kockám” amit el kezdek dobálni és minden dobásnál pont tiszta véletlenül mindig a PI jegyeit dobnám, ha más is dobna vele akkor ő is pont mindig teljesen véletlenül a PI következő számjegyét dobná. Vagy ha nem a PI-jét akkor a gyök 2 számjegyeit vagy log(10)-ét vagy éppen a 2-őét dobná hogy 2 aztán 0 aztán 0 aztán 0 aztán 0 aztán 0 … stb, de semmi trükk csak teljesen véletlenül így hozná a sors. Ugye nem hihető hogy pont véletlen így alakulnának a dobások? Ugyanígy ha egy függvényt választanánk véletlenszerűen akkor az sem egyezne meg semmilyen eddig leírt függvénnyel vagy egyáltalán leírható függvénnyel.

Mj.:

A függvény definíciójából következően egy függvény attól függetlenül létezik, hogy le tudjuk e írni.

Például egy elektronikus napló adatbázisa is egy függvény, amit nem valószínű hogy le lehet írni valami képlettel vagy algoritmussal. Az elemek egyenkénti felsorolásával van leírva az adatbázis rendszerbe. Ezt csak véges elemszámú függvényekre lehet megtenni.

„De engem az érdekel hány olyan "elemi" függvény/művelet van, amire a többi visszavezethető.”

Ilyen értelemben a Brainfuck2 két művelete nem volt ennek megfelelő.

Ajánlom figyelmedbe a linkelt wikis oldalt a Turing-gépről az egészet például az informatikai modelljén túl a formális, matematikai modelljét is.

Szándékosan hardverfüggetlenül közelítettem a kérdést.

A mai szokásos programozási nyelvek procedurális imperatív és/vagy objektumorientált paradigmájúak, de minden ilyen programkód átírható vele ekvivalens funkcionális paradigmájú prog. nyelv-en, ami nem más mint adott szabályrendszer szerint tisztán matematikailag leírni. (Gyakorlatban sokkal bonyolultabb lehet így leírni meg futási időben meg memória használatban lényegesen pazarlóbb lehet, de pusztán csak matematikailag tekintve ez fel sem merül.)

Ennek értelmében a Brainfuck Turing-gép és utasításkészlete megfogalmazható matematikai függvényekként. Ez esetben is bonyolultabb lesz a leírás.

Ekkor az alábbi függvényeim vannak:

+ - > < , . [] ahol a „[]” egy függvénynek számít. Meg van egy φ interpretációs függvényem, ami nem olyan értelemben függvény, mint a többi. Tulajdonképpen mindegy hogy jelölöm, ha egyértelmű, legegyszerűbb ha maradok ezeknél a jelöléseknél.

Matematikában megszoktuk, hogy egy függvénynek van egy (vagy több) paramétere vagy másként argumentuma vagy még másként mondva egy (vagy több) bemenete melyből csinál egy kimenetet. Pl. sin(90)=1, ahol „beraktuk” a 90-et és „kiadta” az 1-et.Függvényeknél mindenki ismeri az értékkészlet és az értelmezési tartomány fogalmát. Azt is mindenki tudja, hogy a sin függvény egyváltozós függvény.

A Brainfuck-t gépnél azt mondtuk, hogy kezdetben minden memóriacella értéke 0 és a memóriacella pointer a legelső memóriacellán áll vagy másként a szalag író-olvasó fej a szalag legelején áll. Ez után kezdük el végrehajtani az utasításokat. Ez nem más mintha matematikailag egy C típusú (C-nek nevezem) vektor lenne ezek a memóriacellák. Több feleképpen definiálhatom, én most úgy döntöttem önkényesen, hogy a + - > < . függvények egyváltozós függvények legyenek. Értelmezési tartományuk és értékészletük az alábbi T típusú halmaz legyen {mutató értéke, cellák vektora, kimenetre írandó}. Vagyis az alábbi 5 függvény kap egy ilyen paramétert és visszaad egy másik ilyen halmazt. A [] függvény kétváltozós függvény első paramétere egy T típusú halmaz a másik paramétere pedig egy F típusú függvények vektora legyen melyeket megfelelően kiszámítva visszaad egy T típusú halmazt.

A Brainfuck-t gépnél azt mondtuk, hogy a „Byte bekérése és a pointernél tárolása” a ,-nél. Matematikailag mondhatom azt hogy elemek sorozata egy V vektorkoponensben ahol mindig a következő elemet „kérem le” Vagyis a , (vessző) egy háromváltozós függvény ahol az egyik paramétere egy T típusú halmaz a másik egy egész szám hogy hányadik vektorkoponens a következő pedig egy V vektor és természetesen az értelmezési tartománya T típusú halmaz.

A „-” függvényt helyettesíthetem „+”-al mivel megtehetem hogy a C típusú vektor komponesei a {0,1} halmazból vegyék fel értékeiket. Így a „+” tulajdonképpen logikai tagadó műveletet csinál az aktuális C vektorkomponesre, de vehetem úgy is hogy nem a {0,1} hanem a {0,1,2 … k-1} halmazból vehet fel értéket és a „+” pedig moduláris összeadást csinál az aktuális vektorkomponensen, így nincs szükség a „-”-ra.

Így elég ez a + > < , . „[]” meg a φ függvényre ami 6+1 függvény.

A Brainfuck-t nyelven való leírásnál tekinthetjük úgy hogy implicit egy csomó függvényparaméter. Egyedül a V vektor-t kell megadni explicit.

Ezzel a pár függvénnyel leírható az összes többi, ami egyáltalán leírható. Ami meg nem az nem írható le sehogy máshogy sem.

A φ függvény mondja meg hogy kell értelmezni a kimeneti bemeneti szimbólumok sorozatát és hogyan kell értelmezni a többi 6 függvényt. Ilyen φ függvény van még az első osztályos matekba is csak ezt nem is kell tudniuk a gyerekeknek. Ott ez mondja meg pl. hogy az 5 konstansszimbólum jelenti az öt értéket.