괴델, 에셔, 바흐 TNT(Typographical Number Theory) 퍼즐 및 솔루션

StackOverflow https://stackoverflow.com/questions/644569

  •  22-07-2019
  •  | 
  •  

문제

Douglas Hofstader가 쓴 Godel, Escher, Bach의 8장에서 독자는 다음 두 가지 진술을 TNT로 번역해야 합니다.

"b는 2의 거듭제곱입니다"

그리고

"b는 10의 거듭제곱입니다"

다음 답변이 맞나요?:

('∃'가 '숫자가 존재함'을 의미한다고 가정):

∃x:(x.x = b)

즉."x에 x를 곱하면 b와 같은 숫자 'x'가 존재합니다."

그것이 맞다면 다음도 똑같이 간단합니다.

∃x:(x.x.x.x.x.x.x.x.x.x = b)

나는 이 문제가 까다롭고 두 번째 문제를 해결하는 데 몇 시간이 걸릴 것이라고 저자가 지적했기 때문에 혼란스럽습니다.분명 여기서 뭔가를 놓쳤나 봐요. 그런데 그걸 볼 수가 없어요!

도움이 되었습니까?

해결책

귀하의 표현은 "B는 제곱 번호"및 "B는 각각 숫자의 10 번째 힘"과 동일합니다. "Power of"진술을 TNT로 변환하는 것은 상당히 까다 롭습니다.

다른 팁

일반적으로 "B는 2의 전력"이라고 말합니다. "1은 2의 배수를 제외하고 B의 모든 제수"와 동일하다고 말합니다. 그건:

∀x (((y (y*x = b & ¬ (x = s0)) → ∃z (ss0*z = x))

편집 : 이것은 10에 맞지 않습니다 (의견에 감사드립니다). 그러나 적어도 그것은 모든 프라임에 효과가 있습니다. 죄송합니다. 결국 어떤 종류의 인코딩 시퀀스를 사용해야한다고 생각합니다. Raymond Smullyan의 "Gödel의 불완전 성 정리"를 제안합니다.

또는 중국의 나머지 정리를 사용하여 숫자 시퀀스를 인코딩 한 다음 지수를 정의 할 수 있도록 재귀 정의를 인코딩 할 수 있습니다. 사실, 그것은 기본적으로 Peano 산술이 완전하고 있음을 증명할 수있는 방법입니다.

이 시도:

D(x,y)=∃a(a*x=y)
Prime(x)=¬x=1&∀yD(y,x)→y=x|y=1
a=b mod c = ∃k a=c*k+b

그 다음에

∃y ∃k(
 ∀x(D(x,y)&Prime(x)→¬D(x*x,y)) &
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z<x→¬D(z,y))→(k=1 mod x)) &
 ∀x∀z(D(x,y)&Prime(x)&D(z,y)&Prime(z)&z<x&∀t(z<t<x→¬(Prime(t)&D(t,y)))→
  ∀a<x ∀c<z ((k=a mod x)&(k=c mod z)-> a=c*10))&
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z>x→¬D(z,y))→(b<x & (k=b mod x))))

"B는 10의 힘"을 표시 해야하는 경우, 실제로 "y y y and yume k a k가있어 y는 뚜렷한 프라임의 산물이되고, 이들 프라임으로 시작하는 시퀀스는 1로 시작합니다. 다음은 다음과 같은 특성을 가지고 있습니다. A의 요소 C는 10*a이고 b로 끝납니다.

회의적인 과학자의 게시물에서 스포일러 버튼 뒤에 "B is a Power 10"문제에 대한 해결책이 있습니다. 여기. 그것은 숫자 이론에서 나온 중국의 나머지 정리와 임의로 길이의 산술의 존재에 의존한다. Hofstadter가 지적했듯이 적절한 이론을 알고 있더라도 생각해 내기가 쉽지 않습니다.

어때요 :

∀X : ∀Y : (SSX ∙ y = B → ∃Z : Z ∙ SS0 = SSX)

(영어로 : ≥ 2 인 B의 모든 요소 자체는 2로 나눌 수 있어야합니다. z * 2 = (2+x).)

나는 이것이 구문에서 허용되는 것을 100% 확신하지 못한다. TNT 그리고 제안 미적분학, GEB를 잊은 지 오래되었습니다.

(편집 : b = 2의 경우N 적어도 문제; 왜 10이 있는지 알 수 있습니다N 10이 프라임이 아니기 때문에 더 어려울 것입니다. 그러나 11N 하나의 용어 "SS0"을 "SSSSSSSSSSS0"으로 바꾸는 것 외에는 동일합니다.)

"b는 10의 거듭제곱입니다"라고 표현할 때 실제로 중국 나머지 정리 및/또는 유한 수열 코딩이 필요하지 않습니다.또는 다음과 같이 작업할 수도 있습니다(명확한 의미가 있는 공식/용어에 대한 단축키로 |, >, c-d와 같은 일반적인 기호를 사용합니다).

  1. 소수 p에 대해 "p는 소수이고 a는 p의 거듭제곱"이라는 TNT의 공식을 EXP(p,a)로 표시하겠습니다.우리는 이미 그것을 만드는 방법을 알고 있습니다.(기술적인 이유로 S0를 p의 거듭제곱으로 간주하지 않으므로 ~EXP(p,S0)입니다.)

  2. p가 소수이면 EXP를 정의합니다.피(c,a) ≖ ⟨EXP(p,a) ∧ (c-1)|(a-1)⟩.여기, 상징 | 하나의 존재 정량 자 및 곱셈을 사용하여 TNT에서 쉽게 정의 할 수있는 "분할"에 대한 바로 가기입니다.c-1(a-1, resp.)에 대해서도 마찬가지입니다. 이는 "Sd=c인 d"(Sd=a, resp.)를 의미합니다.
    EXP(p,c)가 성립하는 경우(즉,c는 p의 거듭제곱입니다. 공식 EXP피(c,a)는 a가 1(mod c-1)이므로 "a는 c의 거듭제곱"이라고 말합니다.

  3. 숫자의 속성 P를 가짐(예:음이 아닌 정수), TNT에서 이 속성을 사용하여 가장 작은 숫자를 참조하는 방법이 있습니다.⟨P(a) ∧ ∀c:⟨a>c → ~P(a)⟩⟩.

  4. "b는 10의 거듭제곱입니다"를 표현하는 공식을 기술할 수 있습니다(더 나은 가독성을 위해 ⟨ 및 ⟩ 기호를 생략하고 SS0 및 SSSSS0 대신 2와 5를 씁니다).
    ∃a:∃c:∃d:(EXP(2,a) ∧ EXP(5,c) ∧ EXP(5,d) ∧ d > b ∧ a⋅c=b ∧ ∀e:(e>5 ∧ e|c ∧ EXP5(e,c) → ~EXP5(e,d)) ∧ ∀e:("e는 EXP와 같은 가장 작은 값입니다.5(c,e) ∧ EXP5(d,e)" → (d-2)|(e-a))).

설명: b = a⋅c = 2라고 씁니다.엑스⋅5와이 (x,y>0) d=5를 선택합니다.지>b z와 y가 서로소가 되는 방식으로(예:z는 소수일 수 있습니다.)그러면 "가장 작은 e..."는 (5지)와이 = 디와이 ≡ 2와이 (mod d-2), 그리고 (d-2)|(ea)는 a = 2를 의미합니다.엑스 = e mod (d-2) = 2와이 ('d-2 > 2 입니다.와이' 및 'd-2 > a'도 마찬가지), 따라서 x = y입니다.

주목: 이 접근 방식은 고정된 분해 a를 사용하여 임의의 숫자 n에 대해 "b는 n의 거듭제곱입니다"를 정의하는 데 쉽게 적용할 수 있습니다.1ㅏ2...ㅏ케이, 여기서 각각은나 는 소수 p의 거듭제곱이다나 그리고 피나 =피제이 → i=j.

다음은 다음과 같습니다.

∀C : ∃D : <(c*d = b) → <(c = so) v∃e : (d = e*sso) >>

다음으로 번역됩니다.

모든 숫자 C에 대해, 숫자 d가 존재하는지, C 시간 d가 b와 같으면 c가 1이거나 d가 e 시간 2와 동일하도록 숫자 e가 존재한다.

또는

모든 숫자 C의 경우, 숫자 d가 존재합니다. B가 C의 계수이고 D가 1 또는 d이면 D가 2의 계수입니다.

또는

두 숫자의 곱이 B 인 경우 그중 하나는 1이거나 그 중 하나는 2로 나눌 수 있습니다.

또는

B의 모든 제수는 1이거나 2로 나눌 수 있습니다.

또는

B는 2의 힘입니다

위의 대부분은 B가 4의 배수라는 것을 보여 주었다고 생각합니다. ': (ssc's ssc ') = c> → c = 2>

형식이 완벽하다고 생각하지 않지만 읽습니다.

모든 C에 대해 C에 대해 C가 B의 계수이고 C가 프라임이면 C와 동일하게 B가 존재합니다.

"b는 2의 거듭제곱이다"라는 진술에 대해 내가 생각해낸 내용은 다음과 같습니다.

∃b:∀a:~∃c:((a * ss0) + sss0) * c = b

나는 이것이 "숫자 B가 존재한다고 말합니다. 따라서 모든 숫자 A에 대해 (a * 2) + 3 (즉, 2보다 큰 홀수)가 C를 곱하여 C가 존재하지 않도록합니다. 당신에게 b. " 따라서 B가 존재하고 0이 될 수없고 2보다 홀수 디바이저가 없으면 B는 반드시 1, 2 또는 2의 다른 전력이 아닌가?

열린 표현은 B가 2의 힘이라는 의미에서 ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

이것은 모든 a, s (sa ∙ ss0)에 대해 B의 계수가 아니라고 효과적으로 말합니다. 그러나 정상적인 용어로, s (sa ∙ ss0)은 1 + ((a + 1) * 2) 또는 3 + 2a. 이제 우리는 "최소한 3 인 홀수가 B의 계수"라고 명령문을 다시 표시 할 수 있습니다. B가 2의 힘 인 경우에만 사실입니다.

나는 여전히 B를 연구하고 있습니다. 10 문제의 힘입니다.

B에 대한 내 솔루션은 두 가지입니다.

isprime ()은 글을 쓰기 어렵지 않아야합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top