Puzzle MU - MU puzzle

The Puzzle MU je hádanka, kterou uvádí Douglas Hofstadter a nalezen v Gödel, Escher, Bach zahrnující jednoduchý formální systém zvaný „MIU“. Hofstadterova motivace spočívá v kontrastu uvažování ve formálním systému (tj. Odvození vět) s uvažováním o samotném formálním systému. MIU je příkladem a Postkanonický systém a lze jej přeformulovat jako a systém přepisování řetězců.

Hádanka

Předpokládejme, že existují symboly M, Já, a U které lze kombinovat a vytvářet řetězce symbolů. Puzzle MU žádá jednoho, aby začal řetězcem „axiomatic“ MI a transformovat jej do řetězce MU v každém kroku použijte jedno z následujících pravidel transformace:^[1][2]

Č.	Formální pravidlo[poznámka 1]			Neformální vysvětlení	Příklad
1.	XJá	→	XIU	Přidat U na konec libovolného řetězce končícího na Já	MI	na	MIU
2.	MX	→	Mxx	Zdvojnásobte řetězec po M	MIU	na	MIUIU
3.	XIIIy	→	XUy	Vyměňte všechny III s U	MUIIIU	na	MUUU
4.	XU Uy	→	xy	Odstraňte všechny U U	MUUU	na	MU

Řešení

Hádanku nelze vyřešit: není možné změnit řetězec MI do MU opakovaným uplatňováním daných pravidel. Jinými slovy, MU není teorémem formálního systému MIU. Abychom to dokázali, musíme vystoupit „mimo“ samotný formální systém.

Aby bylo možné prokázat taková tvrzení, je často výhodné hledat neměnný; to znamená nějaké množství nebo vlastnost, která se při používání pravidel nemění.

V takovém případě se můžeme podívat na celkový počet Já v řetězci. Toto číslo mění pouze druhé a třetí pravidlo. Zejména pravidlo dva jej zdvojnásobí, zatímco pravidlo tři sníží o 3. Nyní, invariantní vlastnost je to počet Jás není dělitelný od 3:

• Na začátku počet Jás je 1, který není dělitelný 3.
• Zdvojnásobení čísla, které není dělitelné třemi, jej ještě nerozdělí 3.
• Odečtení 3 od čísla, které není dělitelné 3, ho také nedělí 3.

Cílem tedy je MU s nulou Já nelze dosáhnout, protože 0 je dělitelné 3.

V jazyce modulární aritmetika, číslo n z Já dodržuje shodu

${displaystyle nequiv 2 ^ {a} ot equiv 0 {pmod {3}}.,}$

kde A počítá, jak často se použije druhé pravidlo.

Rozhodujícím kritériem pro odvoditelnost

Obecněji, libovolně daný řetězec X lze odvodit z MI podle výše čtyři pravidla pokud, a pouze pokud, X respektuje tři následující vlastnosti:

1. X je složen pouze s jedním M a libovolný počet Já a U,
2. X začíná s M, a
3. počet Já v X není dělitelné 3.

Důkaz

Jen když: Žádné pravidlo neposune M, změní počet M, nebo zavádí jakýkoli znak z M, Já, U. Proto každý X odvozený od MI respektuje vlastnosti 1 a 2. Jak je znázorněno před, respektuje také vlastnictví 3.

Li: Li X respektuje vlastnosti 1 až 3, ať ${displaystyle N_ {I}}$ a ${displaystyle N_ {U}}$ být počet Já a U v X, respektive, a nechat ${displaystyle N = N_ {I} + 3N_ {U}}$Vlastností 3 číslo ${displaystyle N_ {I}}$ nemůže být dělitelné 3, tedy ${displaystyle N}$ také nemůže být. To znamená ${displaystyle Nequiv 1 {ext {or}} Nequiv 2 {pmod {3}}}$. Nechat ${displaystyle nin mathbb {N}}$ takhle ${displaystyle 2 ^ {n}> N}$ a ${displaystyle 2 ^ {n} equiv N {pmod {3}}}$.^{[poznámka 2]} Vycházející z axiomu MIs použitím druhého pravidla ${displaystyle n}$ časy získá MIII...Já s ${displaystyle 2 ^ {n}}$ Já. Od té doby ${displaystyle 2 ^ {n} -N}$ je dělitelné 3 výstavbou ${displaystyle n}$s použitím třetího pravidla ${displaystyle {frac {2 ^ {n} -N} {3}}}$ časy získá MIII...IU...U, přesně s ${displaystyle N}$ Já, následovaný určitým počtem U. The U počítat lze vždy, i když je to nutné, jednou použít první pravidlo. Uplatňování čtvrtého pravidla dostatečně často, všechny U lze poté smazat a získat MIII...Já s ${displaystyle N_ {I} + 3N_ {U}}$ Já. Použití třetího pravidla ke snížení trojic Já do U na správných místech X. Celkem, X byl odvozen z MI.

Příklad

Pro ilustraci konstrukce v Li část důkazu, řetězec MIIUII, který respektuje vlastnosti 1 až 3, vede k ${displaystyle N_ {I} = 4}$, ${displaystyle N_ {U} = 1}$, ${displaystyle N = 7}$, ${displaystyle n = 4}$; lze jej tedy odvodit následovně:

MI ${displaystyle {stackrel {2} {o}}}$ MII ${displaystyle {stackrel {2} {o}}}$ MIIII ${displaystyle {stackrel {2} {o}}}$ MIIIIIIII ${displaystyle {stackrel {2} {o}}}$ MIIIIIIIIIIIIIIII ${displaystyle {stackrel {3} {o}}}$ MIIIIIIIUIIIIII ${displaystyle {stackrel {3} {o}}}$ MIIIIIIIUUIII ${displaystyle {stackrel {1} ​​{o}}}$ MIIIIIIIUUIIIU ${displaystyle {stackrel {3} {o}}}$ MIIIIIIIUUUU ${displaystyle {stackrel {4} {o}}}$ MIIIIIIIUU ${displaystyle {stackrel {4} {o}}}$ MIIIIIII ${displaystyle {stackrel {3} {o}}}$ MIIUII.

Aritmetizace

Kapitola XIX Gödel, Escher, Bach dává mapování systému MIU na aritmetiku následujícím způsobem. Nejprve lze každý řetězec MIU přeložit na celé číslo mapováním písmen M, Já, a U na čísla 3, 1 a 0. (Například řetězec MIUIU bude mapována na 31010.)

Zadruhé, jediný axiom systému MIU, konkrétně řetězec MI, se stává číslem 31.

Za třetí, výše uvedená čtyři formální pravidla se stávají následujícími:

Č.	Formální pravidlo[Poznámka 3]			Příklad
1.	k × 10 + 1	→	10 × (k × 10 + 1)	31	→	310	(k = 3)
2.	3 × 10m + n	→	10m × (3 × 10m + n) + n	310	→	31010	(m = 2, n = 10)
3.	k × 10m + 3 + 111 × 10m + n	→	k × 10m + 1 + n	3111011	→	30011	(k = 3, m = 3, n = 11)
4.	k × 10m + 2 + n	→	k × 10m + n	30011	→	311	(k = 3, m = 2, n = 11)

(Pozn .: Vykreslení prvního pravidla výše se povrchně liší od vykreslení v knize, kde je napsáno jako „[i] f jsme vytvořili 10m + 1, pak můžeme udělat 10 × (10m + 1) ". Zde však proměnná m byl vyhrazen pro použití pouze v exponentech 10, a proto byl nahrazen k v prvním pravidle. V tomto vykreslení bylo také uspořádání faktorů v tomto pravidle konzistentní s uspořádáním ostatních tří pravidel.)

Vztah k logice

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (červenec 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Systém MIU analogicky ilustruje několik důležitých konceptů v logice.

Lze jej interpretovat jako analogii pro a formální systém - zapouzdření matematických a logických pojmů pomocí symbolů. Řetězec MI je podobný jedinému axiom a čtyři pravidla transformace jsou podobná pravidla odvození.

Řetězec MU a nemožnost jeho odvození je pak analogická výroku matematické logiky, který nemůže být prokázáno nebo vyvrácen formálním systémem.

Rovněž demonstruje kontrast mezi interpretací na „syntaktické“ úrovni symbolů a na „sémantické“ úrovni významů. Na syntaktické úrovni neexistují žádné znalosti o nerozpustnosti skládačky MU. Systém není viz na cokoli: je to prostě hra zahrnující nesmyslné struny. Při práci v systému mohl algoritmus postupně generovat každý platný řetězec symbolů ve snaze generovat MU, a přestože by nikdy neuspěl, hledal by navždy, aniž by vyvodil, že úkol byl marný. U lidského hráče však po několika pokusech člověk brzy začne mít podezření, že hádanka může být nemožná. Jeden pak „vyskočí ze systému“ a začne uvažovat o spíše než pracovat v něm. Nakonec si člověk uvědomí, že systém nějakým způsobem existuje o dělitelnost třemi. Toto je „sémantická“ úroveň systému - významová úroveň, které systém přirozeně dosahuje. Na této úrovni lze logiku MU považovat za nemožnou.

Neschopnost systému MIU vyjádřit nebo odvodit fakta o sobě, například neschopnost odvodit MU, je důsledkem jeho jednoduchosti. Tuto schopnost však mohou mít složitější formální systémy, jako jsou systémy matematické logiky. Toto je klíčová myšlenka Godelova věta o neúplnosti.

Pedagogické využití

Ve své učebnici Diskrétní matematika s aplikacemi, Susanna S. Epp používá puzzle MU k zavedení konceptu rekurzivní definice a začíná příslušnou kapitolu citací z GEB.^[3]

Viz také

• Invariant (matematika)
• Neomezená gramatika

Poznámky

Reference

externí odkazy

• „Systém MIU společnosti Hofstadter“. Archivovány od originál dne 4. března 2016. Citováno 29. listopadu 2016. Online rozhraní pro výrobu derivací v systému MIU.
• "MU Puzzle". Archivovány od originál dne 14. května 2018. Citováno 13. května 2018. Online implementace JavaScriptu produkčního systému MIU.