뮤 퍼즐

MU 퍼즐은 더글라스 호프스타터가 말한 퍼즐로 바흐의 괴델에서 발견된 것으로 "MIU"라고 불리는 단순한 형식 시스템을 포함하고 있다.Hofstadter의 동기는 형식 시스템 내의 추론을 형식 시스템 자체에 대한 추론과 대조하는 것이다.MIU는 Post 표준 시스템의 한 예이며 문자열 개서 시스템으로 재구성할 수 있습니다.

퍼즐

기호가 있다고 가정해 봅시다.M,I,그리고.U조합하여 일련의 상징을 만들 수 있습니다.MU 퍼즐은 "축" 문자열로 시작하도록 요구합니다.MI그걸 현악기로 바꿔서MU각 단계에서 다음 변환 규칙 ^[1][2]중 하나를 사용합니다.

Nr.	정식 규칙[주 1]			비공식 설명	예
1.	xI	→	xIU	를 추가합니다.U으로 끝나는 문자열의 끝까지I	MI	로.	MIU
2.	Mx	→	Mxx	다음에 문자열을 두 배로 늘립니다.M	MIU	로.	MIUIU
3.	xIIIy	→	xUy	임의의 치환III와 함께U	MUIIIU	로.	MUUU
4.	xUUy	→	xy	모두 제거UU	MUUU	로.	MU

솔루션

퍼즐은 풀 수 없다: 문자열을 바꾸는 것은 불가능하다.MI안으로MU주어진 규칙을 반복적으로 적용함으로써.즉, MU는 MIU 형식 시스템의 정리가 아닙니다.이를 증명하기 위해서는 정식 시스템 자체를 '외부'해야 한다.

이와 같은 주장을 증명하기 위해서는 불변성, 즉 규칙을 적용하는 동안 변하지 않는 수량이나 속성을 찾는 것이 종종 유익합니다.

이 경우는, 다음의 합계수를 확인할 수 있습니다.I줄서서두 번째 규칙과 세 번째 규칙만 이 번호를 변경합니다.특히 규칙 2는 2배로, 규칙 3은 3으로 줄인다.이제, 불변의 특성은 그 수가I는 3으로 나눌 수 없습니다.

• 처음에, 의 수는Is는 3으로 나누어지지 않는 1입니다.
• 3으로 나누어지지 않는 숫자를 두 배로 한다고 해서 3으로 나누어지지 않는다.
• 3으로 나누어지지 않는 수에서 3을 뺀다고 해서 3으로 나누어지지 않는다.

따라서, 의 목표는MU0으로I0은 3으로 나누어지기 때문에 달성할 수 없습니다.

모듈식 산술의 언어로, n은I일치에 따르다

${\displaystyle n\equiv 2^{a}\equiv 04pmod {3}이(가) 아닙니다.},$

여기서 a는 두 번째 규칙이 적용되는 빈도를 카운트합니다.

파생성에 대한 결정 가능한 기준

보다 일반적으로, 임의의 문자열 x는 다음에서 도출할 수 있습니다.MI위의 4가지 규칙에 따르면 x가 다음 3가지 속성을 존중하는 경우에만 해당됩니다.

1. x는 1개로만 구성됩니다.M및 임의의 수의I그리고.U,
2. x는 로 시작한다.M,그리고.
3. 개수Ix는 3으로 나누어지지 않는다.

증명

다음 경우에만: 규칙이 없는 경우M의 수를 변경합니다.M또는 다음 중 임의의 캐릭터를 도입합니다.M,I,U따라서, 모든 x는 에서 파생됩니다.MI는 속성 1과 속성 2를 존중합니다.앞에서 설명한 바와 같이 속성 3도 존중합니다.

if: x가 속성1 ~ 3을 존중하는 경우 $(\$ $및$ $(\$를 다음 번호로 $합니다{\displaystyle {}_{}}$.I그리고.U(x), N ${\displaystyle =}$ ${\displaystyle N_{}}$I + ${\displaystyle {}_{}}$ N $({$ N$=N_{I}+3N_{U$로 $합니다{\displaystyle }$. 속성 3에서는 $숫자{\displaystyle {}_{}}$ $({$를 3으로 나눌 수 없으므로 N$({displaystyle$N})도 3으로 나눌 수 없습니다.$즉{\displaystyle }$, N ${\displaystyle >}$ ${\displaystyle \text{1}}$ ${\displaystyle 또는}$ N${\displaystyle }$>${\displaystyle 2}$ ( ${\displaystyle mod\mathrm{}}$3)$${\$displaystyle$ N$\equiv$ 1 {\$text${ $or }N\equiv$ 2 {\$pmod {3$입니다.$$N \ $displaystyle$ n \ $in$\$mathbbb {$ N $}$ } } $、$ ${\displaystyle {}^{}}$> N \ $displaystyle$ 2^ { $n$> n $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle 2^{}}$ ${\displaystyle 2}$ 2 2 2 2 N${\displaystyle }$2 2 2 2 ${\displaystyle 2}$ 2 2 2 2 2 n 2 2 2 2 2 n 2 n 2 that 2 MI, 두 $번째{\displaystyle }$ 규칙을 n회 적용하면 n회 n${displaystyle$ n$}$회$$ 취득됩니다.MIII...I$($ 2$^{n})$ $포함{\displaystyle {\mathrm{}}^{}}$ I. ${\displaystyle {2n}^{}}$ $N은$$$3으로 $나누어지므로{\displaystyle {\mathrm{}}^{}}$$,$ $n$을$$$구성$하면 3번째 $규칙{\displaystyle \frac{{\mathrm{}}^{}}{}}$ ${\displaystyle \frac{{2n}^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$ $3$을 적용하면 $2n - N$을 얻을$$$$수 있습니다.MIII...IU...U($정확히{\displaystyle }$ N$\displaystyle$ N$)$ I, 그 뒤에 몇 가지 수가 있습니다.U.그U카운트는 필요에 따라 첫 번째 규칙을 한 번 적용하여 항상 균등하게 만들 수 있습니다.네 번째 규칙을 충분히 자주 적용하는 것, 모두U그런 다음 삭제할 수 있으며, 따라서MIII...I${\displaystyle {NI}_{}}$ ${\displaystyle {}_{}}$ $(\$$유}}$ I세 번째 규칙을 적용하여 세 번째 규칙 적용I에Ux를 얻을 수 있습니다.모두 합하면 x는 로부터 파생됩니다.MI.

예

프루프의 일부인 경우 스트링의 구성을 설명하려면MIIUII특성 1 ~ 3을 고려하여 ${\displaystyle {NI}_{}}$ ${\displaystyle {}_{}}$({$디스플레이$ 스타일$N_${I}=$4$ $N{\displaystyle {}_{}}$ ${\displaystyle U_{}}$ ${\displaystyle {}_{}}$({$디스플레이 스타일$ N_${U$}=$1$ $N{\displaystyle }$ ${\displaystyle =}$ $({디스플레이 스타일$ N$=7$ $n{\displaystyle }$ ${\displaystyle =}$ $({디스플레이 스타일$ N$=4$로 유도됩니다.

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

산술화

에셔 괴델 19장 바흐는 MIU 체계와 산술의 매핑을 다음과 같이 제시한다.첫 번째로 모든 MIU 스트링은 문자를 매핑하여 정수로 변환할 수 있습니다.M,I,그리고.U(예를 들어 스트링과 같은 문자열)을 각각 3, 1, 0 입니다.MIUIU31010에 매핑됩니다).

둘째, MIU 시스템의 단일 공리, 즉 문자열MI31이 됩니다.

셋째, 위에 제시된 4가지 공식 규칙은 다음과 같습니다.

Nr.	정식 규칙[주 3]			예
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)

(NB: 위의 첫 번째 규칙의 렌더링은 책의 렌더링과 표면적으로 다릅니다.여기서 "i"는 10m+1을 만들 수 있다면 10×(10m+1)을 만들 수 있습니다.단, 여기서 변수 m은 10의 지수에서만 사용하도록 예약되어 있기 때문에 첫 번째 규칙에서는 k로 대체되었습니다.또, 이 렌더링에서는, 이 룰의 요소의 배치는, 다른 3개의 룰의 배치와 일치하고 있습니다.)

논리와의 관계

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2013년 7월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

MIU 시스템은 유추를 통해 논리학의 몇 가지 중요한 개념을 설명한다.

이것은 공식 체계에 대한 유추로 해석될 수 있습니다 - 기호를 사용하여 수학적이고 논리적인 개념을 캡슐화한 것입니다.MI 문자열은 단일 공리와 비슷하며, 네 가지 변환 규칙은 추론 규칙과 유사합니다.

그 MU문자열과 그 어원이는 불가능한 다음 수리 논리학의 또는 disproven는 공식적인 시스템에서 증명될 수 없는 성명과 유사하다.

그것은 또한 해석 사이에 기호들의"구문"수준과 의미의"의미"수준에 대비를 보여 줍니다.는 통사적 수준에는 맨유 퍼즐의 불용성에 대해 알 수 없다.그 시스템에:이것은 간단한 게임 의미 없는 문자열들과 관련된 언급하지 않았다.그 시스템 안에서 일하는 것, 알고리즘을 연속적으로 시도 맨유를 생성하기하고 성공하지 않을 것이다, 이것은 영원히, 이 모험이 헛된 것 deducing지 검색한 기호의 모든 유효한 문자열을 발생시킬 수 있다.인간 선수 들어 하지만 시도 이후에 쓰는 숫자는, 곧은 퍼즐은 불가능할 것이 아닌지 의심하기 시작한다.어는 다음 그 시스템에 대해 납득시키기 시작한다, 이내에 작업보다"그 시스템에서 점프".결국은 제도가 몇몇 방식으로 3으로 나눌 수 있음에 관한 것을 깨닫는다.시스템의 이것은"의미"수준 —이 시스템 안에서 자연스레를 확보한 의미의 차 수준이다.이런 눈높이에서는, 맨유 퍼즐이 불가능한 것 볼 수 있다.

그 단순함의 MIU 시스템의 무능이나deduce 자체에 신경을 하는 것이 맨유를 도출하기 위해 같은 사실을 표현하기 위해, 결과다.하지만, 수리 논리학의 시스템과 같은 더 복잡한 공식적인 시스템, 이런 능력을 갖게 된다.괴델의 불완전성 정리 이 사람이 핵심 아이디어다.

교육학적 용도

그녀의 교과서에서, 이산 수학 응용 프로그램과, 수잔나 S.에프 재귀적 정의의 개념을 소개했고, GEB의 말을 인용 관련 장이 시작되는 맨유 퍼즐을 사용한다.[3]

「 」를 참조해 주세요.

• 학적 불변 항의(수학)
• 제한 없는 문법

메모들

레퍼런스

외부 링크

• "Hofstadter's MIU System". Archived from the original on 4 March 2016. Retrieved 29 November 2016. MIU 시스템에서 파생물을 생성하기 위한 온라인 인터페이스입니다.
• "MU Puzzle". Archived from the original on 14 May 2018. Retrieved 13 May 2018. MIU 프로덕션 시스템의 온라인 JavaScript 구현.