Meseország mindenkié
Eredeti szerző: jotunder
A magyar miniszterelnök ma aljas módon a neonácik oldalára állt, belehazudott az egész ország arcába és uszított a meleg polgártársaim ellen.
Ezért én most a lehető legegyszerűbb és leggyermetegebb módon, matematikus olvasóink valószínűleg nem fognak megdícsérni érte, el fogom magyarázni az Entscheidungsproblem-et, ami az emberiség egyik legérdekesebb matematikai (filozófiai?) problémája, mely problémát egy bizonyos Alan Turing nevű brit, meleg, csodálatos matematikus oldott meg 1937-ben.
Szinte mese lesz, mert meseország mindenkié. Mindenkinek joga van arra, hogy megértse ezt, mert nincs meleg vagy heteroszexuális matematika, nincs meleg vagy heteroszexuális tehetség, nincs meleg vagy heteroszexuális bölcsesség, csak matematika van, tehetség és bölcsesség, ahogy nincs meleg vagy heteroszexuális Magyarország sem, csak Magyarország… nincs. Ma nincs, egyszer talán majd lesz.
******************************************************
Az Entscheidungsproblem valójában egy filozófiai probléma és az emberi elme határairól szól. Talán többről. Talán az isteni elme határairól is. Megválaszolhatunk-e minden kérdést? Mindenható-e a logika? Mindenható-e az elme?
Persze nem várhatjuk el, hogy logikai eszközökkel válaszoljunk olyan kérdésekre, minthogy mi az Élet értelme vagy létezik-e Isten. Az Entscheidungsproblem arról szól, hogy létezik-e egy olyan titokzatos algoritmus, amely logikai állításokról dönti el, hogy igazak vagy hamisak.
Turing (és tőle függetlenül Alonzo Church filozófus-matematikus) bizonyította be, hogy az elménknek is vannak határai, a mindent megoldó algoritmus nem létezik. És most a kedves Olvasó ezt meg fogja érteni. Igen, az egyik legérdekesebb matematikai/filozófiai problémát pont a mai napon fogja megérteni a kedves Olvasó.
*******************************************************
Tegyük fel egy pillanatra, hogy létezik egy ilyen csodálatos algoritmus. Ez nyilván azt jelentené, hogy egy nagyon egyszerű feladatot is meg tudna oldani. El tudná dönteni egy számítógépprogramról (mondjuk BASIC nyelvű), hogy a következő két állítás közül melyik igaz rá:
X. A program egy NULLÁK-ból és EGYES-ekből álló végtelen sorozatot ír ki.
Y. A program nem ezt teszi. Bármi mást, csak nem ezt. Lehet, hogy hibaüzenettel leáll, lehet, hogy egyszer leír egy A betűt, vagy csak véges sok NULLÁT és EGYEST. Jegyezzük meg, hogy minden, a billentyűzeten leírható, jelsorozatot potenciális programnak észlel az algoritmus, József Attila Mama című versét is. Hát azt pont egy Y típusú jelsorozatnak.
Az algoritmusunk tehát megérti a programokat anélkül, hogy lefuttatná őket, hiszen a döntését véges idő alatt kell meghoznia. Nem olyan egyszerű ez. Képzeljük el, hogy a program, amiről az algoritmusnak el kell döntenie, hogy az X vagy az Y típusba tartozik, a következő. Elkezdi sorban nézegetni a számokat és amikor talál egy ikerprímet, mint például a 3,5 vagy a 11,13 , akkor leír egy EGYEST. Ilyen programot kilencéves gyerekek is tudnak írni. De most gondoljon bele az Olvasó. Ha az algoritmusunk el tudná dönteni, hogy ez a program X vagy Y típusú, akkor ezzel meg tudná oldani az ikerprímszámsejtést (mármint, hogy van-e végtelen sok ikerprímpár), ami a matematika egyik leghíresebb megoldatlan problámája.
Valaki azt állítja, hogy a birtokában van a fenti SZUPER algoritmus. Mi most kimutatjuk, hogy téved. Nem hazudik, mint Magyarország miniszterelnöke, csak téved.
A fent már említett kilencéves gyereket megkérjük arra, hogy írjon egy SZIMPLA nevű programot/algoritmust, ami felsorolja az összes olyan véges jelsorozatot, amit a billentyűzeten egyáltalán le lehet írni. Ezek között a jelsorozatok között lesz a XH3%777 , a FUCKYOU (igen, külön neki), és egy olyan jelsorozat is, ami egy valóságos számítógépprogram és outputként kiír végtelen sok egyest.
A SZIMPLA algoritmus outputja tehát a J(1), J(2), J(3),… végtelen sorozat, amelynek minden eleme egy véges jelsorozat, és minden jelsorozat pontosan egyszer szerepel az outputban.
Ezek után megépítjük a HIPER nevű algoritmust. Ami a következő módon működik. A SZUPER algoritmusnak odaadjuk J(1)-et. Ha SZUPER azt mondja, hogy J(1) egy Y típusú jelsorozat, akkor HIPER kiír egy 0-t. Ha SZUPER azt mondja, hogy J(1) egy X típusú jelsorozat, akkor addig futtatjuk J(1)-et, amíg le nem írja az ELSŐ számot (mert tudjuk, hogy végtelen sok NULLÁT vagy EGYES-t írna le, ha hagynánk bomolni). Ha ez a szám 0, akkor a HIPER kiír egy 1-t. Ha 1, akkor a HIPER kiír egy 0-t.
Ezek után a SZUPER algoritmusnak odaadjuk J(2)-t. Ha SZUPER azt mondja, hogy J(2) egy Y típusú jelsorozat, akkor HIPER kiír egy 0-t. Ha SZUPER azt mondja, hogy J(2) egy X típusú jelsorozat, akkor addig futtatjuk J(2)-et, amíg le nem írja a MÁSODIK számot. Ha az 0, akkor a HIPER kiír egy 1-t. Ha az 1, akkor a HIPER kiír egy 0-t.
Ezek után a SZUPER algoritmusnak odaadjuk J(3)-t. Ha SZUPER azt mondja, hogy J(3) egy Y típusú jelsorozat, akkor HIPER kiír egy 0-t. Ha SZUPER azt mondja, hogy J(3) egy X típusú jelsorozat, akkor addig futtatjuk J(3)-at, amíg le nem írja a HARMADIK számot. Ha az 0, akkor a HIPER kiír egy 1-t. Ha az 1, akkor a HIPER kiír egy 0-t.
És így tovább…….
A HIPER algoritmus tehát egy X típusú jelsorozat, hiszen az outputja egy NULLÁK-ból és EGYESEK-ből álló végtelen sorozat.
És akkor mi van, kérdezi most az Olvasó?
HIPER egy jelsorozat, tehát a kilencéves gyerek SZIMPLA nevű programja felsorolta. Ő volt J(n), ahol n esetleg egy nagyon nagy szám, százbillió számjegyből áll, talán annál is több számjegyből. HIPER X típusú jelsorozat, tehát az outputjának n-edik karaktere vagy egy NULLA vagy egy EGY.
Tegyük fel, hogy ez a T nevű érték NULLA.
Emlékezzünk most vissza arra, hogy a HIPER outputjának mi is az n-edik jegye. Ha a J(n) nevű program X típusú, akkor a HIPER outputjának n-edik jegye pontosan akkor NULLA, ha a J(n) program outputjának az n-edik jegye EGYES. Dehát előbb beszéltük meg, hogy ez a bizonyos jegy, amit T-nek neveztünk, NULLA volt, akkor pedig mégse lehet NULLA.
Hoppácska.
Ha kétségbeesésünkben feltesszük, hogy a T nevű érték EGYES, akkor pont ugyanakkora bajba kerülünk. Más lehetőség pedig nincs. Ellentmondásba ütköztünk.
Tehát SZUPER nem létezik.
************************************************************
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16517964-6ae3707b72324' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16517964&origin=www.orulunkvincent.hu&obj_id=192691293-16517964-6ae3707b72324&n=1' data-name='like-post-frame-192691293-16517964-6ae3707b72324' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>
@Hottentottenstottertrottelmutterattentäterlattengi: Ezt tényleg nem adják fb-talanoknak, de majd keresek videót róla, mostanában az a kedvenc tanulási módom. Ha, khm, nehéz 🙂
@mafi mushkila: hát igen, csak gyűlnek a feladatok… eddig csak az volt, hogy két egész szám hányadosából eljutsz a 0-hoz, most már az is, hogy c osztója a-nak is és b-nek is, meg hogy a és b minden közös osztója osztja c-t is…
(ha még gondolkodnál a „de miért jutok 0-hoz?” problémán, fogalmazd át az eljárás lépéseit a „két egész szám hányadosa” speciális esetére.)
@mafi mushkila: hát igen, csak gyűlnek a feladatok… eddig csak az volt, hogy két egész szám hányadosából eljutsz a 0-hoz, most már az is, hogy c osztója a-nak is és b-nek is, meg hogy a és b minden közös osztója osztja c-t is…
(ha még gondolkodnál a „de miért jutok 0-hoz?” problémán, fogalmazd át az eljárás lépéseit a „két egész szám hányadosa” speciális esetére.)
@MEDVE1978: Ha a többségi társadalom mibenlétét kellene megfogalmaznunk, azt mondhatnák, hogy a társadalom többsége ilyen és/vagy olyan minősége miatt már átélte a diszkriminációt. Miközben valószínűleg maga is megvalósította másokkal szemben.
@MEDVE1978: Ha a többségi társadalom mibenlétét kellene megfogalmaznunk, azt mondhatnák, hogy a társadalom többsége ilyen és/vagy olyan minősége miatt már átélte a diszkriminációt. Miközben valószínűleg maga is megvalósította másokkal szemben.
@dr Brcskzf Gröőő: WTF? Mert eddig mit csinálunk, nem egész számokat? Tördeltünk? Ha nem tördelem, honnan lesz hányadosom? Mit csináljon a micsodával a milyen micsoda?
Monnyátok, hogy jóindulattal csináljátok, úgy jobban szórakozom! 🙂
@dr Brcskzf Gröőő: WTF? Mert eddig mit csinálunk, nem egész számokat? Tördeltünk? Ha nem tördelem, honnan lesz hányadosom? Mit csináljon a micsodával a milyen micsoda?
Monnyátok, hogy jóindulattal csináljátok, úgy jobban szórakozom! 🙂
@MEDVE1978: a gyerekeidnek vagy bárki más gyerekeinek az tetszik, ami tetszik; piszkosul nem kötelező semmilyen mesét sem kedvelni, de még olvasni sem, senkinek.
Épp erről van szó: az a szerencsétlen, ostoba náci némber azt akarja, hogy _ő_ szabhassa meg, hogy mások & mások gyerekei mit olvashassanak. – Tipikus inkvizíciós, egyeduralmi hozzáállás. (…Az egész ember és akciója nem ér meg annyi mondatot, amennyit pillanatnyilag rá pocsékolunk.)
@MEDVE1978: a gyerekeidnek vagy bárki más gyerekeinek az tetszik, ami tetszik; piszkosul nem kötelező semmilyen mesét sem kedvelni, de még olvasni sem, senkinek.
Épp erről van szó: az a szerencsétlen, ostoba náci némber azt akarja, hogy _ő_ szabhassa meg, hogy mások & mások gyerekei mit olvashassanak. – Tipikus inkvizíciós, egyeduralmi hozzáállás. (…Az egész ember és akciója nem ér meg annyi mondatot, amennyit pillanatnyilag rá pocsékolunk.)
@mafi mushkila: senki nem várhatja el tőled, hogy ezt megértsd. valójában ez egy rafinált dolog. viszont a matematikusoknak van egy beépített aspergerje (nekem egészen biztosan van), ami azt okozza, hogy általában azt gondolják, hogy amit ők szépnek gondolnak, az objektíve szép. persze igazuk van 🙂
@mafi mushkila: senki nem várhatja el tőled, hogy ezt megértsd. valójában ez egy rafinált dolog. viszont a matematikusoknak van egy beépített aspergerje (nekem egészen biztosan van), ami azt okozza, hogy általában azt gondolják, hogy amit ők szépnek gondolnak, az objektíve szép. persze igazuk van 🙂
@jotunder: Jó, de itt most egy easy-peasy kezdő kis dolgot akartak mutatni nekem! Csak sajnos nem értem a szavakat 🙂
…Mostanában olyanokat olvasok, hogy a spektrumnak az fele, amerre ti laktok, csak a mai berendezkedésben jelent hátrányt, számít említendőnek vagy kezelendőnek (inkább a manage értelemben), ezt nem tudom valójában felmérni, de gondoltam, bedobom…
@mafi mushkila: az easy-peasy kezdő kis dolog az az euklideszi algoritmus, és az tényleg az. Ha sok éve nem foglalkoztál vele, akkor kell egy kis erőfeszítés (de nem nagyobb, mint felidézni a Himnusz harmadik versszakát).
Csak frissítsd fel az emlékeidet, hogy:
1.) mit jelent az, hogy az A és B (az egyszerűség kedvéért pozitív) egész számok legnagyobb közös osztója (még guglizni is ér)
2.) mi az a maradékos osztás (itt is ér).
3.) Ha ez megvan, már csak azt kell belátnod, hogy ha a nagyobb A számot maradékosan elosztod a kisebbik (de nem nulla) B számmal, akkor a _maradéknak_ és a B-nek a legnagyobb közös osztója ugyanaz, mint A-nak és B-nek a legnagyobb közös osztója. (Az a jó, ha erre magadtól rájössz. De csak azért ne guglizz, hogy legyen aha-élményed.)
4.) Utána jön ennek a lépésnek az ismételgetése. (Most B-t osztod el maradékosan a maradékkal, és kapsz egy újabb maradékot, stb.)
És azt sem ördöngősség megérteni, hogy miért jutunk előbb utóbb egy olyan számpárhoz, ahol már maradék nélkül osztja a kisebbik a nagyobbikat (és így ezek legnagyobb közös osztója a kisebbik).
@mafi mushkila: „honnan fogom tudni, hogy mindig ez fog történni, még ha meg is tapasztalom sokszor” Ennek van egy egyszerű oka. Amikor levonunk egyet, akkor a számláló csökken és a nevező nem változik. Amikor reciprokot képezünk, akkor a számláló és a nevező helyet cserél. Tehát a számláló és a nevező összege két lépésben biztos csökken. A végtelenségig nem csökkenhet ez az összeg, tehát eljutunk egy olyan törthöz, aminél az algoritmus megakad: ez a tört a nulla. Nézd meg a korábbi példán: 43/18 -> 25/18 -> 7/18 ->18/7 -> 11/7 -> 4/7 -> 7/4 -> 3/4 -> 4/3 -> 1/3 -> 3/1 -> 2/1 -> 1/1 -> 0/1. Egyre kisebb számok írják le az aktuális törtet, és ezek a számok mindaddig csökkenthetők, amíg a nullát nem érjük el. Ezért érjük el a nullát biztosan. Eukleidész nem csak ezt vette észre, hanem azt is, hogy – ha nem egyszerűsítjük a törteket – az egyes lépésekben a számláló és a legnagyobb közös osztója nem változik. A játék végén egy 0/c alakú törthöz érünk, tehát 0 és c legnagyobb közös osztója – ami a c – az eredeti számláló és nevező legnagyobb közös osztója is egyben.
@nudniq: és, ha ez megvan, utána jön az, hogy amit Bourbaki először írt, az pont ugyanez, csak egy-egy maradékos osztást esetleg sok lépésben csinálunk (a törtből sorra levonunk egyet, megint egyet, amíg a tört nagyobb, mint egy, azaz a számlálóból levonogatjuk a nevezőt addig, amíg tudjuk, és végül a számláló:nevező maradékos osztás maradéka marad a számlálóban, ez kisebb, mint a nevező, ekkor a tört kisebb, mint 1, így reciprokot vonunk, és ez a szerepcsere azt okozza, hogy most jön az előző nevező maradékos osztása az imént kijött maradékkal, és így tovább.)
@Bourbaki: jajj, lelőtted. pedig szerintem rájött volna magától. 🙂
@jotunder: szerintem pedig itt pont az aspergerrel merőben ellentétes dolog működése látszik: a teljesen univerzális emberi igény a másikkal való kommunikációra.
Érezzük, hogy a másik meg akar valamit érteni abból, amit mi mondani akarunk, de olyan nyelven beszélünk, ami annak a másiknak nem anyanyelve (sőt, valószínűleg nem is ezt a nyelvet ismeri, hanem egy másikat, ami a mi nyelvünknek közeli rokona, de nem tökéletes a kölcsönös érthetőség).
Ekkor elkezdünk erőfeszítéseket tenni: átfogalmazunk, máshogy fogalmazunk, megpróbálunk rájönni, milyen nyelveken érthet az a másik, és mi ezekből a nyelvekből melyikeken tudjuk (kb.) megfogalmazni azt, amit mondani akarunk, és áttérünk… ez elég alapvető emberi élmény annak, aki már került idegen anyanyelvű emberrel kommunikációs helyzetbe úgy, hogy nem volt mindkettőjük által tökéletesen beszélt közvetítő nyelv.
És én itt nagyon hasonló kommunikációs próbálkozásokat látok…
@nudniq: Én tegnap biztattam, hogy rájöjjön, de egyértelműen kifejezte, hogy „it does not spark joy”, ill. hogy utálja a számokat. Ezért inkább elmondtam neki, mert valamennyi kíváncsiság maradt benne. A maradékos osztás bonyolítja a dolgot. Természetesen ez is benne van az euklideszi algoritmusban, és algoritmikus szempontból nagyon fontos, de minimalista szempontból – csupán a lényegre koncentrálva – nincs rá szükség. Hasonlóan, az SL(2,Z) csoportot generálják az (1 1|0 1) és (0 -1|1 0) mátrixok, ahol az első az (x,y) -> (x+y,y) operációhoz tartozik, a második az (x,y) -> (-y,x) operációhoz. Az a fantasztikus, hogy Eukleidésztől egyenes út vezet a moduláris formákhoz, ami a modern számelmélet (csoportelmélet, fizika stb.) mély eszköze.
@Bourbaki: miután elküldtem az első hsz-emet, rájöttem, hogy nem kellett volna belekevernem a maradékos osztást (főleg, hogy a törtes algoritmusban csak elbújva van jelen, és annak a megértetése most a fő cél, szóval jobb lett volna csak azt mondani: A és B legnagyobb közös osztója ugyanaz, mint A-B és B legnagyobb közös osztója, stb).
Dehát „kimondott szó: kilőtt nyíl” már nem tudtam visszaszívni, így egy következő hsz-ben próbáltam kicsit helyrehozni, hogy miért is ugyanaz a törtes módszer, mint a maradékos osztásos.
@nudniq: OK, elnézést, ha kavartam. Előadásra készülök, és nem olvastam el figyelmesen mindent. Tanítani nehéz!
Azért öröm nézni, hogy a hülyeség nem ismer határokat:
http://www.bbc.com/news/uk-54422505
@Muad’Dib: és megint az a kicseszett excel. Áldás, amikor arra használják amire való, átok, amikor azt hiszik mindenre jó.
@Bourbaki: Egyet meg kell érts: rajtatok kívül van, akit ez egyáltalán nem hoz lázba, és még vagyunk mi, akiket viszont leginkább csak a végeredmény érdekel. gyök(2)=p/q nix megoldás? Szuper, ha épp erre a tényre van szükségem, és hálás vagyok a „Jó Tündérnek”, aki bebizonyította, de ennyi. Ahogy hálás vagyok Shannon-nak, hogy az info elmegy veszteség nélkül A-ból B-be, Mills-nek, hogy bizonyította a Böhm-Jacopini sejtést, az anyagtudósok sokaságának, Fert-Grünberg-nek, hogy terabyte-okat tudok pár négyzetcentin tárolni… szóval sok mindenkinek, sokmindenért, de a részletek nem (igazán) érdekelnek (persze ez nem teljesen igaz, csak sarkítok az érthetőség kedvéért).
A lelkesedésed (meg @Big JT-é) mindig eszembe juttatja, midőn az idők hajnalán, mat profunk egy szuszra felvésett bő kéttáblányi bizonyítást, majd szembefordulva a nagyelőadó közönségével, arcán ragyogó mosollyal kérdezte: Ugye milyen gyönyörű? Namost, mint földhözragadt, kezdő villanymérnök-palánták, kábé háromnegyedünk, úgy a második tábla közepéig már biztosan elvesztette a fonalat, s ebből valami valszeg az arcokon is meglátszott, ezért kedvesen megkérdezte: csak nincs valami, ami nem tiszta? 🙂
Szóval pechetekre (és sajnos a miénkre is), a homo sapiens nagy része sosem lesz képes veletek osztozni az ” a^x + b^x = c^x ” kapcsolatos Szent Grálok csodálatában :-(.
Nincs rajta Orbán neve, de a támogatást megadta hozzá vasárnap:
img.index.hu/imgfrm/8/1/8/6/MED_0016278186.jpg
@Muad’Dib:
Ilyenkor jut eszembe ikaruss 0. informatikai törvénye: minden adat Excel sheeten kezdi, és fejezi be életét.
@ijontichy: A poszt egy olyan alapvető filozófiai kérdésről szól, ami Descartes-tot (így írják?) és Leibniz-et os foglalkoztatta, és más lenne a világ, ha nem az lenne igaz, ami végül kiderült. A bizonyítás acquired taste-t igényel, akár a kézművessör vagy a modern képzőművészet és nem gondolom, hogy bárkitől elvárható, hogy megértse.
@jotunder: „és nem gondolom, hogy bárkitől elvárható” Ezért írtam @Bourbaki-nak (és nem @poszt), hogy ne keseredjen el, hogy ennyi „földhözragadt” veszi körül. Valójában sokunkat (aki már feléri ésszel, hogy sajnos mennyi mindent nem tud) megesz a sárga irigység 🙂 (amúgy a kézműves sört pont meg akartam említeni valamilyen formában, de aztán nem szaporítottam tovább a bitfestéket)
@ijontichy: Elég öreg vagyok ahhoz, hogy tudjam „rajtunk kívül van, akit ez egyáltalán nem hoz lázba”, annak pedig örülök, hogy „még vagytok ti, akiket viszont leginkább csak a végeredmény érdekel”.
@ijontichy: Az emberek nagy részének van olyan szakmája, hobbija stb., amihez sokkal jobban ért, mint mások, mert sokat foglalkozik vele, szereti, van hozzá érzéke. A matematikusnál ez a dolog a matematika. Annyi nehézség van, hogy a matematika nehezen kommunikálható kívülállóknak, egyrészt mert tömör nyelvet használ (egyetlen képletben elfér több oldalnyi információ), másrészt mert belülről építkezik, belső fogalmakat használ. Szóval kihívás, ha valamit nem matematikusoknak el kell magyarázni, ugyanakkor fontos is, hogy legyen kapcsolat a nem matematikusokkal.
@Bourbaki:
Hmmm, ezt a reciprokos dolgot én is elkezdtem „ökörködni” (szerintem vagy 25 éve nem foglalkoztam matekkal) és én így okoskodtam (de lehet hülyeség):
Ugye van az 1-nél nagyobb x/y. Akkor (x/y)*(y/x)=1 . Továbbá (y/x) – (z*x/x) <1 hiszen addig vonogatunk egyet amíg kisebb számot nem kapunk mint 1. Akkor (y/x) – (zx/x) <1 , (y-zx)/x <1 tehát y – zx <x . Magyarán bizonyítottuk, hogy a levonások végén mindig az eredetinél kisebb számlálót kapunk. Így mivel egész számokról beszélünk tuti, hogy a számláló nullában fog végződni.
@Muad’Dib: Elég bizonyítani, hogy ha 1-et levonunk, az már csökkenti a számlálót (a nevező megtartása mellett). Ami pedig világos, hiszen 1 levonása a számlálót a nevezővel csökkenti: x/y – 1 = (x-y)/y. A reciprok képzésénél persze a számláló szükségképpen nő, hiszen a nála nagyobb nevező kerül a helyére (x/y -> y/x). De ez nem gond, a lényeg az, hogy a számláló és a nevező *maximuma* két egymás utáni lépésben mindig csökken, hiszen reciprok képzése után mindig jön az 1 levonása. Márpedig a végtelenségig nem csökkenhet a számláló és a nevező maximuma, ezért az algoritmus elakad. Mivel az algoritmus csak a nullánál akad el (tehát pozitív törtre mindig van lépése), ezért jut el mindig a nullába.
Például ha kiindulok egy törtből, aminek a számlálója és nevezője is legfeljebb egymillió, akkor biztos lehetek abban, hogy legfeljebb kétmillió lépésen belül elérem a nullát.
@Bourbaki:
Végül is ha jól látom én ezt bizonyítottam csak kicsit nyakatekerten. 🙂
@Bourbaki: Az érződött, hogy a csökkenés elkerülhetetlen, de már az a magabiztosság nincs meg bennem, hogy tudjam, hogy ez nem akadhat el semmin sehol, hogy az adott feltételek között homogén és univerzális is. Sejteni sejthetem ennyiből, még egyszerűnek is tűnik ebből a mostani magyarázatodból, de hivatalosan nem lepődhetnék meg, ha ugyanerre azt mondanátok, hogy hát igen, úgy néz ki, viszont így vagy így tönkre lehet tenni. Vagy azt, hogy logikus a gondolatmenet, de nem elégséges a bizonyításhoz.
Különben nem a számokat utálom, csak ha olyasmit kell velük csinálni, ami nem fekszik 🙂 A számok aranyosak.
@mafi mushkila: „hogy tudjam, hogy ez nem akadhat el semmin sehol” Az algoritmus nem akad el egyetlen pozitív törtszámnál sem, mert minden ilyenre lép egyet: ha 1-nél kisebb (és pozitív) a törtszám, akkor veszi a reciprokát (az eredmény egy pozitív törtszám), ha pedig 1-nél nem kisebb a törtszám, akkor levon belőle 1-et (és az eredmény egy pozitív törtszám vagy a nulla).
Szóval az a bizonyítás rendben van. Az algoritmus addig megy, amíg el nem éri a nullát. És a nulláig legfeljebb kétszer annyit lép, mint a kiindulási számláló és nevező maximuma.
@Bourbaki: „És a nulláig legfeljebb kétszer annyit lép, mint a kiindulási számláló és nevező maximuma.”
Na, erről beszélek, nyuszómuszó! Van itt egy ilyen kis ártatlan adalékod, műhelytitkod – vagy lehet, hogy nem is ártatlan és ezen is minden más múlik, egész tudományterületek múlnak, hogy pont így van, nemtom. De ezzel az erővel lehetne olyan titkod is, amitől megsavanyodik az egész. …Nem a matematikát véleményezem!, az szent, csodás, hiszünk benne, tapasztaljuk. Hanem a nem matematikus viszonyát a matematikához mutatom. A te rendben lévő bizonyításod az nekünk csak bemondás, mit tudjuk mi azt.
Tudsz olyat mutatni, ami matematikai értelemben bizonyítás, és ugyanakkor egy laikus sem kételkedhet? Vagy ez, amiről itt beszélünk, pont azért jött elő, mert ez minden bizonyítások ősanyja? Ennél már nem lesz jobb? Ti hogy tanultátok, hogy mi az „bizonyítani”?
@mafi mushkila: „Tudsz olyat mutatni, ami matematikai értelemben bizonyítás” Én olyat mutattam, kérlek szólj, ha nem értesz valamit.
Elmondom részletesebben, lassabban. Egy pozitív törtszám magasságán a számlálójának és a nevezőjének a maximumát értjük (tehát a kettő közül a nagyobbat). Pl. 67/129 magassága 129. Az algoritmusnak kétféle lépése van: reciprokképzés (ami a magasságot nem változtatja) és 1 levonása (ami a magasságot csökkenti). A reciprokképzést mindig az 1-nél kisebb törtekre alkalmazzuk, tehát őt rögtön követi az 1 levonása. Pl. a 67/129-ből az algoritmus 129/67-et csinál, amiből pedig 62/67-et csinál. A 67/129 magassága 129, a 129/67 magassága 129 (ugyanaz), a 62/67 magassága 67 (csökkent). Tehát két lépésben a 129-es magasság csökkent 67-re. A magasság legfeljebb csak annyiszor csökkenhet, amekkora ő maga, tehát az algoritmus legfeljebb csak annyit léphet, mint a kiindulási magasság kétszerese.
Nézzük meg ezt egy példán, zárójelbe írom a pozitív törtek után a magasságukat: 67/129 (129) -> 129/67 (129) -> 62/67 (67) -> 67/62 (67) -> 5/62 (62) -> 62/5 (62) -> 57/5 (57) -> 52/5 (52) -> 47/5 (47) -> 42/5 (42) -> 37/5 (37) -> 32/5 (32) -> 27/5 (27) -> 22/5 (22) -> 17/5 (17) -> 12/5 (12) -> 7/5 (7) -> 2/5 (5) -> 5/2 (5) -> 3/2 (3) -> 1/2 (2) -> 2/1 (2) -> 1/1 (1) -> 0.
Ebben a példában a 129-es magasság csökkent, mégpedig így: 129 -> 67 -> 62 -> 57 -> 52 -> 47 -> 42 -> 37 -> 32 -> 27 -> 22 -> 17 -> 12 -> 7 -> 5 -> 3 -> 2 -> 1. Minden csökkenés egy vagy két lépésben történt, tehát számolás nélkül tudjuk, hogy legfeljebb 258 lépésben eljutottunk a nullához (valójában 23 lépésben jutottunk el hozzá).
Bármilyen törtből indul el az algoritmus, legfeljebb annyit tud lépni, mint a magasság kétszerese. Ezt magyaráztam el részletesen fent.
@Bourbaki:
Bocs, jobban megnéztem, tulajdonképpen nem teljesen azt bizonyítottam amit írtál nekem. Mondjuk úgy, hogy túlbonyolítottam kissé. De amúgy matematikailag nincs hiba a bizonyításomban? Tehát jól gondolom, hogy az én módszeremmel is bizonyítva lett, hogy a a tört számlálója el fogja érni a nullát?
@mafi mushkila: „bizonyítani” annyit tesz, mint néhány tautológiát és néhány triviális kombinálási mechanizmust fölhasználva összerakni az állítást. a használható tautológiák és kombinálási mechanizmusok listája előre rögzítve van és komoly erőfeszítéseket tesznek, hogy még rövidebbé, még triviálisabbá tegyék.
én pl. legutóbb valami olyasmire próbáltalak rávezetni, hogy Bourbaki játéka valós számokat használ meg olyan lépéseket, hogy „nagyobb-e mint 1?” „vedd a reciprokát!”, „csökkentsd 1-gyel!”; ezek abban a speciális esetben, ha a szóbanforgó valós szám két egész szám hányadosa, lefordíthatók úgy, hogy „a számláló vagy a nevező a nagyobb?”, „cseréld föl a számlálót és a nevezőt!” „csökkentsd a számlálót a nevezővel!”, amiből összerakható egy másik, ekvivalens játék, amit két számmal játszunk, viszont csak egy szabálya van: „csökkentsd a nagyobbat a kisebbbel!” — és erről hátha könnyebb látni, hogy pozitív egészekre véget ér.
azt már Platón is leírja, hogy ha ebben a módosított játékban egy négyzet átlójából és éléből indulunk, akkor két lépésben egy másik négyzet átlóját és élét kapjuk, tehát ezt a végtelenségig lehet ismételgetni, mert az nem számít, hogy egyre kisebbek azok a négyzetek — és itt kell a hit vagy gyakorlat vagy nemtudoménmi, hogy ezen meg se hökkenjünk, hogy hé, az előbb azt mondtam, hogy ez nyilván nem mehet a végtelenségig, most meg azt, hogy ezt nyilván minden határon túl ismételhetem; hogy ne zavarjon, hogy a valóságban egy Mackó sajtot nem tudok minden határon túl egyre kisebb darabokra vágni; hogy ne azt gondoljam, hogy ez igazából egy indirekt bizonyítás volt, nyilvánvalóan hamis állításra lyukadtam ki, tehát valamelyik föltevésem hibás kell hogy legyen (ami hihetetlen, attól még lehet igaz, és a matematikusok nagyon leleményesek tudnak lenni, ha valamiről el kell hinni, hogy nem hamis, csak hihetetlen).
@Muad’Dib: Te azt bizonyítottad, hogy a levonásokkal a számláló mindig csökken. De nem csak levonások vannak, hanem reciprokképzés is, amikor pedig a számláló nő. Pl. az 5/7-ből az algoritmus 7/5-öt csinál, tehát az 5 számláló a 7 számlálóra növekedett. Az persze igaz, hogy az új számláló is bemegy az új nevező alá (az újabb levonások által), ami pedig a régi számláló volt. Szóval a levonás-sorozatok végén megjelenő számlálók is csökkennek, és hát a végtelenségig nem csökkenhetnek.
Összefoglalva: szerintem jól gondoltál mindent, csak nem írtad le minden részletében.
@Bourbaki:
Szuper, köszönöm. Őszintén szólva jól esett egy kis agytorna. 🙂 Nagyon szerettem a matematikát, de nagyon-nagyon régóta nem használom napi szinten semmilyen formában.
Penrose, aki Nobel-díjat kapott fizikából a posztban szereplő tételre alapozta tézisét, miszerint a tudat feljebbvaló a formális logikánál.
@jotunder:
Penrose nem ezért a tézisért kapta a Nobel-díjat. 🙂
A tézis – „a tudat feljebbvaló a formális logikánál” -, ebben a formában szerintem teljesen értelmetlen. A tudat és a logika között a feljebbvaló reláció értelmezhetetlen.
Ennél szerintem jobb NJ már korábban is idézett két kis gondolata:
1. Mint ahogy a görög vagy a szanszkrit nyelv létezése történeti tény, nem pedig feltétlen logikai szükségszerűség, ugyanúgy józanul feltételezhetjük, hogy a logika és a matematika is történeti eredetű és esetleges kifejezési formák.
2. Az agy nyelve nem egyezik meg a matematika nyelvével.
Igaz, hogy ő nem Turing-Churchre alapozta ezeket a „téziseket”.
@dr Brcskzf Gröőő: Váááá! Pontosan erről akartam kérdezni, überszuper! Más kérdés, hogy nem egészen értem mindenhol (főleg az elején meg a végén), de mennyire klassz, hogy ezen már érzem, hogy a saját kérdésemhez kapcsolódik.
@Bourbaki: A bevezetőm a kérdésekhez félreérthető lehetett, abban nem kételkedtem, hogy ez már egy valódi bizonyítás volt, hanem azokon belül próbáltam kérni olyat, ami felfoghatóbb számomra. Aminek a bizonyítás-mivolta beláthatóbb. De ezt is megpróbálom megérteni rendesen, önmagában követhetőnek tűnik.
Nagyon köszönöm mindkettőtöknek az erőfeszítéseket 🙂