Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Поток Научпоп доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 51
Не совсем по теме статьи, но вот еще задачка: найти минимальное число, поиск по которому в гугл ничего не выводит
Пример пустой выдачи для числа
в твите можно легко вместить почти бесконечность.
1) все знают запись 9.(9) ,
2) переносим период до точки (9).9,
3) ну возвращаем назад (9).(9)
получаем почти бесконечность , понятную людям
я победил
Такого числа не существует. Если мы говорим об обычном смысле слова "число".
В задаче не было прописано ограничение что оно должно быть конечным, вещественым и была свобода в нотации.
Да. Еще есть неявное условие, число должно быть настоящим числом. Ваша штука - не число. Если ее умножить на десять, то оно будет равняться самому себе, значит это не число
Тогда заявка:
Наибольшее число, которое можно уместить в твите
должно быть отвергнуто по той же причине, что это ненастоящее число
потому как набольшее плюс один равно самому себе, иначе оно не наибольшее.
и эта заявка не должна рассматриваться потому что это не число, а не какой-то там парадокс
Если ее умножить на десять, то оно будет равняться самому себе, значит это не число
Ноль протестует.
Создается впечатление, что есть какая-то произвольность (для дилетанта, вроде меня, глубокая сеть внутренних ссылок от произвольности неотличима).
Например, можно "определить"
Число девяток в десятичной записи числа 0.(9)
А можно
Число троек в десятичной записи числа 0.(9)
Или даже
Число единиц в десятичной записи числа 0.(9)
Интуитивно чувствуется, что эти предложения отличаются от, например, такого
Число пар семерок в десятичной записи номера шага, на котором Ахиллес догонит черепаху
А куда относится следующее вообще непонятно
Число двоек в десятичной записи номера первого нуля функции Римана, не лежащего на критической прямой
В контексте заметки понятно, что это вероятно выходит на проблематику, обозначенную в самом конце: представление об определимости и невыразимости истины. В итоге кажется, что рассказ оборвался в тот самый момент, когда только начался ответ на вопрос.
Такого числа не существует. Если мы говорим об обычном смысле слова “число”.
Такое число существует. Смотрите за руками:
9+1 = 10
9…9 +1 = 10…0
…999 + 1 = 0 - т.к. единичка “уезжает в бесконечность”, т.е.
…999 = -1
Далее вспоминаем, что 0.999… = 1 (известный “баг” десятичной записи дробей). Таким образом:
…999.999… = 0
Так то!
(9).(9)
получаем почти бесконечность , понятную людям
Шикарные бесконечности, чего тут не понять.
я победил
А потом прихожу я, и говорю, что ∞ всё-таки больше (хоть и ненамного). А потом приходит кто-то ещё и говорит, что у меня была счётная ∞, а он принёс несчётную ∞. А потом приходит Пряник и вводит нотацию Пряника 8, в которой ∞8∞ означает бесконечность бесконечной несчётности. Ведь «в задаче не было прописано ограничение что оно должно быть конечным, вещественым и была свобода в нотации». А потом…
В эпистемологии Колмогоров-related stuff называется «фоновые знания». На которые неявно ссылается текст твита, и через эту дыру пролезает что угодно.
Начал читать нормально, потом все быстрее и всё “меньшим глазом” (одним глазом, в полглаза,…). И такая мысль посетила меня.
Эх, эту бы энергию да в мирных целях! То есть, автор потратил кучу сил и времени, чтобы сказать что? Непонятно. 😎
Ну можно в твит просто бесконечную сумму записать
А почему, собственно, мы зацикились на десятичной систем счисления? Шестнадцатиричное число будет больше, но можно и углУбить.
Ещё одно подтверждение пословицы "без внятного ТЗ результат хз." Если бы чел строго задал нотацию, то получил бы число, а в общем виде получаем только пучок философских рассуждений.
Итак, существует конечное число возможных твитов, и некоторые из них описывают числа. Следовательно, существует лишь конечное число чисел, которые мы вообще можем задать с помощью твита.
Неверно
Кстати да. Если мы свободно можем переопределять нотацию снаружи записи, то бездна ещё глубже - мы произвольное число можем обозначить, причём даже не твитом, а всего одним символом.
Да даже систему правил менять особо не обязательно...
Unix Time. Количество секунд прошедших с 1 января 1970ого года
Собственно, критикуемое утверждение задано в крайне наивной форме. В нём благодаря багу с параметризацией даже есть интересная лазейка, позволяющая выйти в континуальные множества. Не в каждый момент, конечно, но если квант времени всё-таки не существует, то за любой интервал времени я могу перебрать континуум вариантов
Вот пример: 1/(t-floor(t)), где t - текущее физическое время в секундах, а floor(t) оно же округлённое вниз до целых.
Всё. Раз в секунду мой твит указывает на любое неограничено большое число
Кстати да. Если мы в твите можем написать алгоритм получения какого угодно числа, то мы можем и написать алгоритм получения скольки угодно возможного количества чисел.
Вот количество алгоритмов - да, конечно, потому что конечно количество символов и соответственно, перестановок.
Вся остальная статья рушится.
Вы можете записать конечное число алгоритмов заданной длины, но вы не сможете понять какой из них победил.
Тупо перебором и сравнением можно.
Только вот проблема в том что сами алгоритмы - ограничены. Но вот машины их исполняющие - нет. Мы можем придумать бесконечно много вариаций вычислительный машин сколь угодно большой сложности (по сути запихнув большую часть алгоритма в них)
Нет, мы не можем выявить лучшую программу полным перебором. Если какая-то программа всё ещё работает, в общем случае нельзя понять вернёт ли она результат или она будет работать "вечно".
Например тут, чтобы понять, что алгоритм никогда не остановится, жюри должно доказать теорему Ферма (доказали только в 1994)
найти n > 2, для которого выполнится условие великой теоремы Ферма
def generate():
s = 6
while True:
for n in range(3, s - 2):
for x in range(1, s - n - 1):
for y in range(1, s - n - x):
yield x, y, s - n - x - y, n
s += 1
def fermat(g):
for x, y, z, n in g:
if x**n + y**n == z**n:
return n
fermat(generate())А тут и сейчас никто не знает остановится эта программа или нет
найти первое нечётное совершенное число
def generate():
n = 1
while True:
yield n
n += 2
def odd_perfect(g):
for n in g:
if sum(d for d in range(1, n) if n % d == 0) == n:
return n
odd_perfect(generate())
То есть на текущем уровне знаний жюри не сможет определить остановится ли вторая программа вообще. Неизвестно дождётся результата или нет.
Хуже - в будущем ничего не изменится - оно и там не сможет выявить победителя, это не проблема нашей тупости и неспособности доказать конкретную теорему - проблема остановки неразрешима в принципе. Нет общего алгоритма, который бы мог определять завершит ли работу программа или нет.
А зачем нам парится об останове? Если теоритически мы можем ждать сколь угодно долго? А если ещё возмём математику с актуальной бесконечностью (“математику Чака Нориса”) - то можем и до самой бесконечности подождать.
P.S.
У вас в первой программе - странный цикл. Там сразу видится способ показать что никогда не остановится - даже если великая теорема Ферма не верна ( там проверяется равенстово x^n + y^n = (const - (x+y))^n - высшие степени сокращаются и получается поиск целочисленных корней многочлена высоких степеней с целыми коофициентами да ещё и на ограниченном отезке).
Вторая программа принимается - но вы как-то очень странно циклитесь по нечётным числам - можно же напрямую в цикле без привлечения елдов.
Неизвестно, может та самая программа, которая всё ещё бежит и даст когда-нибудь самый большой ответ. А узнать закончится ли она мы не можем. Поэтому сколько угодно долго мы бы ни ждали, окончательного ответа мы дать не сможем. Лучшее, что можно сделать - сообщать текущего известного кандидата в каждый момент времени, но это уже не про математику
P.S. программу накидывал без тестирования, как иллюстрацию. вполне вероятно, что там неточночти или кривой код
Кстати недавно наткнулся на очень интересный ответ из mathoverflow https://mathoverflow.net/a/25830/35921
Вот перевод части из нее, относящееся к этому треду:
Другой пример использует релятивистскую физику. Предположим, что вы хотите решить экзистенциальный теоретико-числовой вопрос вида ∃nφ(n). В общем случае истинность такого утверждения подтверждается одним конкретным числовым примером, и в принципе не существует способа получить ответ «да» или «нет» на подобный вопрос за конечное время.
Тогда можно сделать следующее: сесть в ракету и летать вокруг Земли, в то время как ваш аспирант - а затем его аспиранты, их аспиранты и так далее до бесконечности - будут искать подходящий пример. При этом вы заранее договариваетесь, что, если такой пример когда-либо будет найден, на вашу ракету будет отправлен сигнал.
Тем временем вы должны ускоряться, неограниченно приближаясь к скорости света, таким образом, чтобы из-за релятивистского замедления времени вечность, прошедшая на Земле, соответствовала лишь конечному промежутку времени на ракете. Таким способом ответ можно было бы узнать за конечное время.
Если же представить ракеты, летающие вокруг других ракет, то в принципе за конечное время можно было бы узнать ответ на любое арифметическое утверждение.
Разумеется, у этой истории есть множество проблем. Начать хотя бы с того, что для необходимого сокращения времени потребовалась бы неограниченная энергия. Тем не менее можно построить пространства-времена Маламента - Хогарта, позволяющие обойти эти проблемы и дающие одному наблюдателю доступ к бесконечной временной истории другого наблюдателя.
Эти примеры подводят к любопытному возможному аргументу против тезиса Чёрча - Тьюринга. Он основан на идее о том, что в природе может существовать ещё не реализованная вычислительная мощность, возникающая благодаря тому факту, что мы живём в квантово-механическом релятивистском мире.
Скриньте мой твит: "число, на единицу большее, чем наибольшее число, которое может быть описано в твите"
Насколько я помню: ∞ + 1 = ∞, т.е. если записать ∞ то это будет максимальное число. И при увеличении оно так и останется бесконечностью.
Можно записать еще и вот так limx→01/x=+∞
Это смотря в какой группе. В кольце целых чисел (как и действительных) нет такого числа как бесконечность. Поэтому вопрос о наибольшем и вызывает интерес. Иначе бы ответом было просто слово "бесконечность", а дальше математичнодвинутые головы приплели бы сюда алеф-арифметику.
Но мы про действительные числа. А там бесконечности нет. Вот если бы работали на колесе, честно бы сказали, что бесконечность - наибольшее число.
Предел же - это из области математического анализа и запись "предел стремится к бесконечности" там имеет особый смысл. Предел стремится к бесконечности не требует существования бесконечности как числа, но лишь указывает, что по мере приближения аргумента к тому, к чему он там приближается - подпредельное выражение неограниченно растёт.
А если читать конкретно, что это число, записанное цифрами, а не алгоритм вычисления, то победит 9999... (сколько символов "9" поместится в твит).
Можно просто в 1 символ
∞
Опять очередная демагогия, сводящаяся к "человеческий язык неконсистентен, на нем можно сказать синтаксически корректный бред. Особенно если пытаться на нем описывать его свойства".
Очередная демагогия. Прежде чем рассуждать о том какое число можно записать, неплохо было бы описать какие числа считаются "самыми большими". А их не много. Или хотя бы - как автор определяет "большое число".
Если правильно помню по возрастанию то "большие числа" это "три трит" и его степени, потом "занятый бобер" и потом "трёхцветное двоичное дерево". Причем уже в самом тритрите количество цифр невычислимо современными средствами. Про степени вообще молчу.
Остальные два числа описываются алгоритмами получения, поскольку есть мнение что уже даже число бобра невозможно записать современными математическими определениями.
9e9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999!
160 символов.
Определение числа Райо можно сократить и уместить в 280 символов.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Наибольшее число, которое можно уместить в одном твите