Загадки и решения Теории типографских чисел (TNT) Гёделя, Эшера, Баха
https://stackoverflow.com/questions/644569
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В восьмой главе книги Дугласа Хофстадера «Гедель, Эшер, Бах» читателю предлагается перевести эти два утверждения на язык TNT:
«b — степень 2»
и
«б — степень 10»
Верны ли следующие ответы?:
(Предполагая, что «∃» означает «существует число»):
∃x:(xx = b)
то есть«существует число x такое, что произведение x, умноженное на x, равно b»
Если это верно, то следующий не менее тривиален:
∃x:(x.x.x.x.x.x.x.x.x.x = b)
Я в замешательстве, потому что автор указывает, что они сложны и что на решение второго потребуется несколько часов;Должно быть, я упустил что-то очевидное, но я этого не вижу!
Решение
Ваши выражения эквивалентны утверждениям «b — квадратное число» и «b — 10-я степень числа» соответственно.Преобразовать «силу» утверждений в TNT значительно сложнее.
Другие советы
В общем, я бы сказал, что «b — степень 2» эквивалентно «каждый делитель b, кроме 1, кратен 2».То есть:
∀x((∃y(y*x=b & ¬(x=S0))) → ∃z(SS0*z=x))
РЕДАКТИРОВАТЬ:Это не работает для 10 (спасибо за комментарии).Но, по крайней мере, это работает для всех простых чисел.Извини.Я думаю, вам все-таки придется использовать какие-то последовательности кодирования.Я предлагаю «Теоремы Гёделя о неполноте» Рэймонда Смалляна, если вам нужен подробный и более общий подход к этому вопросу.
Или вы можете закодировать числовые последовательности, используя китайскую теорему об остатке, а затем закодировать рекурсивные определения, чтобы можно было определить возведение в степень.Фактически, именно так вы можете доказать, что арифметика Пеано является полной по Тьюрингу.
Попробуй это:
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 и число k такие, что y является произведением различных простых чисел, и последовательность, закодированная k через эти простые числа, начинается с 1, обладает свойством, что следующее элемент c из a равен 10*a и заканчивается на b"
За кнопкой спойлера в посте скептически настроенного ученого есть решение проблемы «b — это степень 10». здесь.Это зависит от китайской теоремы об остатках из теории чисел и существования арифметических последовательностей простых чисел произвольной длины.Как указал Хофштадтер, это нелегко придумать, даже если вы знаете соответствующие теоремы.
как насчет:
∀х:∀у:(SSx∙y = b → ∃z:z∙SS0 = SSx)
(по-английски:любой коэффициент b, равный ≥ 2, сам должен делиться на 2;буквально:для всех натуральных чисел x и y, если (2+x) * y = b, это означает, что существует натуральное число z такое, что z * 2 = (2+x).)
Я не уверен на 100%, что это разрешено в синтаксисе ТНТ и исчисление высказываний, я давно не просматривал GEB.
(редактировать:для b = 2н по крайней мере проблема;Я понимаю, почему 10н будет сложнее, поскольку 10 не является простым числом.Но 11н будет то же самое, за исключением замены одного термина «SS0» на «SSSSSSSSSSS0».)
Для выражения «b — степень 10» вам фактически не нужна китайская теорема об остатках и/или кодирование конечных последовательностей.Альтернативно вы можете действовать следующим образом (мы используем обычные символы |, >, c-d, как ярлыки для формул/терминов с очевидным значением):
Для простого числа p обозначим EXP(p,a) некоторую формулу в TNT, говорящую, что «p — простое число, а a — степень p».Мы уже знаем, как его построить.(По техническим причинам мы не считаем S0 степенью p, поэтому ~EXP(p,S0).)
Если p — простое число, мы определяем EXPп(c,a) ≖ ⟨EXP(p,a) ∧ (c-1)|(a-1)⟩.Здесь символ | это ярлык для «разделения», который может быть легко определен в TNT, используя один существующий квантификатор и умножение;то же самое справедливо и для c-1 (a-1, соответственно), что означает «d такое, что Sd=c» (Sd=a, соответственно).
Если EXP(p,c) выполняется (т.е.c — степень p), формула EXPп(c,a) говорит, что «a является степенью c», поскольку тогда a ≡ 1 (mod c-1).Имея свойство P чисел (т.е.неотрицательные целые числа), в TNT существует способ ссылки на наименьшее число с этим свойством:⟨P(a) ∧ ∀c:⟨a>c → ~P(a)⟩⟩.
Можно сформулировать формулу, выражающую «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 — наименьшее такое, что EXP5(в,д) ∧ ЕХР5(d,e)" → (d-2)|(e-a))).
Объяснение: Пишем b = a⋅c = 2Икс⋅5й (x,y>0) и выберите d=5я>b таким образом, что z и y взаимно просты (например,z может быть простым числом).Тогда «наименьшее е...» равно (5я)й = дй ≡ 2й (mod d-2), а (d-2)|(e-a) влечет за собой a = 2Икс = е мод (д-2) = 2й (у нас 'd-2 > 2й' и 'd-2 > a'), и поэтому x = y.
Примечание: Этот подход можно легко адаптировать для определения того, что «b является степенью n» для любого числа n с фиксированным разложением a.1а2...ак, где каждыйя является степенью простого числа pя и пя = пдж → я = j.
Вот что я придумал:
∀c:∃d:<(c*d=b)→<(c=SO)v∃e:(d=e*SSO)>>
Что переводится как:
Для всех чисел c существует число d, такое, что если c, умноженное на d, равно b, то либо c равно 1, либо существует число e такое, что d равно e, умноженному на 2.
Или
Для всех чисел c существует число d, такое что, если b кратно c и d, то либо c равно 1, либо d кратно 2.
Или
Если произведение двух чисел равно b, то одно из них равно 1 или одно из них делится на 2.
Или
Все делители числа b либо равны 1, либо делятся на 2.
Или
b — степень 2
Я думаю, что большая часть вышеизложенного показала только то, что b должно быть кратно 4.Как насчет этого:∃b:∀c:<<∀e:(c∙e) = b & ~∃c':∃c'':(ssc'∙ssc'') = c> → c = 2>
Я не думаю, что форматирование идеальное, но там написано:
Существует b такое, что для всех c, если c является делителем b и c простое число, то c равно 2.
Вот что я придумал для утверждения «b — степень 2»
∃б:∀а:~∃с:((a * ss0) + sss0) * c = b
Я думаю, что это говорит: «Существует число B, так что для всех чисел A не существует числа C, такое, что (A * 2) + 3 (другими словами, нечетное число больше 2), умноженное на C, дает вам б. " Таким образом, если B существует и не может быть нулевым, и у него нет странных делителей, превышающих 2, то не обязательно будет 1, 2 или другая сила 2?
Для открытого выражения, означающего, что b является степенью двойки, у меня есть ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b
Это фактически говорит о том, что для всех a S(Sa ∙ SS0) не является фактором b.Но в обычных терминах S(Sa ∙ SS0) 1 + ((a + 1) * 2) или 3 + 2a.Теперь мы можем перефразировать это утверждение так: «Ни одно нечетное число, равное хотя бы 3, не является делителем b».Это верно тогда и только тогда, когда b является степенью двойки.
Я все еще работаю над задачей b в степени 10.
мое решение для b - это степень двойки:∀х:∃y x.y=b ( isprime(x) => x = SS0 )
isprime() не должно быть сложно написать.
