Comments 173
Взять хотя бы проблему останова.
Тут уже потребуется анализ потока исполнения для ответа на вопрос: «окажется ли указатель исполнителя за пределами произвольно заданного диапазона памяти». Если ответ утвердительный, то по индукции следует, что алгоритм никогда не остановится.
С каким именно диапазоном надо работать? Мы задаём его заранее или мы должны проверить на 10 ячейках, на 100, на 1000 и так далее… И где остановиться?
Диапазон — свободная переменная. Задача анализатора понять, что какой бы диапазон мы ни задали — указатель из него выйдет. Я это не уточнил, но благодаря индукции ему доступна информация о том, что объёма памяти на 1 бит меньше уже не хватает.
Вот "понять, что какой бы диапазон мы ни задали — указатель из него выйдет" требует неизвестного времени. Может статься, это время будет линейно расти с увеличением размера диапазона. А может, даже экспоненциально. Т.е. ограничить время, не зная заранее размер диапазона, никак.
Детальнее можете изучить, читая про гипервычисления https://en.m.wikipedia.org/wiki/Hypercomputation и далее по ссылкам.
Четырёхзначная логика лишена парадоксов.
Забыли проверить утверждение «Это утверждение Жёлтое (истинность зависит от контекста)».
Все бесконечности равны.
Охх.
Получается, что Санта сам не может быть вещественным числом. Однако, ранее мы постулировали, что такой Санта среди вещественных чисел есть. И тем самым, кстати, нарушили один из основных принципов доказательства от противного — недоказуемая посылка в нём может быть только одна — которая далее и опровергается. А в «доказательстве» Кантора их две — одна явная, а другая не очень.
Какая вторая? Что «Пусть такой Санта существует»? Ну так он конструктивно получается по нашему соответствию «вещественные -> натуральные». Пусть есть инъективная «f: R -> N», упорядочим вещественные числа по их образу, рассмотрим двоичное представление, построим число, у которого n-ая цифра после запятой равна отрицанию n-ой цифры после запятой n-го числа. Вот и Санта.
Проверить остановку — не проблема.
Оракул, который принимает любой алгоритм на вход и бросает на выход ошибку формально подходит под ваш критерий, но не даёт никакой информации.
Математика свернула не туда.
яснопонятно
Какое-то дикое извращение интуиционистской логики с попутным отрицанием Кантора, Гёделя и Тьюринга и замахом на безупречную матлогику.
Забыли проверить утверждение «Это утверждение Жёлтое (истинность зависит от контекста)».
Без дополнительных утверждений это неопределённость.
Ну так он конструктивно получается
Не получается. Исходя из первой гипотезы любое вещественное число, как бы мы его ни генерировали, уже будет иметь прообраз. А канторово число — не более, чем попытка угнаться за хвостом, так же как и в случае с 0.(9), который эффективно равен 1.
Охх.
Раз уж вас триггерит теорема Кантора, то можете подумать ещё и вот над чем: если разделить множество действительных чисел на счётное подмножество и его дополнение, то теорема кантора фактически "доказывает", что в дополнении можно найти хотя бы 1 число. Однако, не сложно показать, что существует отображение счётного множества на счётное множество, дополненное 1 элементом. То есть для доказательства несчётности необходимо не просто доказать, что мощность дополнения не меньше 1 и даже не достаточно доказать, что его мощность счётна. Нужно доказать, что мощность дополнения более чем счётна. Получаем порочный круг — чтобы доказать несчётность одного множества, нужно доказать несчётность его подмножества. Уроборос.
Оракул, который принимает любой алгоритм на вход и бросает на выход ошибку формально подходит под ваш критерий
Он даёт некорректный ответ, так как исполнитель сможет исполнить алгоритм, который не зависит от оракула.
Без дополнительных утверждений это неопределённость.
Именно это оно и утверждает, а следовательно истинно. Раз уж на то пошло, как выглядит исчисление высказываний в вашей логике? Как выглядят матрицы для конъюнкции и импликации? Какой цвет у «Из фиолетового следует зелёный»?
Не получается. Исходя из первой гипотезы любое вещественное число, как бы мы его ни генерировали, уже будет иметь прообраз. А канторово число — не более, чем попытка угнаться за хвостом, так же как и в случае с 0.(9), который эффективно равен 1.
Вещественное пространство по определению полно — к чему бы мы не гнались, это последовательность с конкретным пределом. Этот предел — вещественное число и не имеет образа. Последовательность 0.9, 0.99, 0.999… так же стремится к 1, а 3, 3.1, 3.14, 3.141… — к пи.
то теорема кантора фактически «доказывает»,
То есть для доказательства несчётности необходимо не просто доказать
Тут стрелочки в разные стороны смотрят. Это совершенно нормально, что по следствиям теоремы нельзя пройти в обратном порядке и получить доказательство теоремы.
Он даёт некорректный ответ, так как исполнитель сможет исполнить алгоритм, который не зависит от оракула.
Как мы делим алгоритмы, для которых допустимо кидать ошибку или нужно обязательно дать ответ остановится или нет?
Именно это оно и утверждает, а следовательно истинно.
Если жёлтый — это неопределённый, то абсурд получается:
Раз уж на то пошло, как выглядит исчисление высказываний в вашей логике? Как выглядят матрицы для конъюнкции и импликации?
В статье есть ссылка на книгу, где вы найдёте все ответы.
Какой цвет у «Из фиолетового следует зелёный»?
Фиолетовый, ибо я не смог это выражение интерпретировать.
Последовательность 0.9, 0.99, 0.999… так же стремится к 1,
Обратите внимание, что каждый бит этих двух записей одного числа попарно отличается.
Это совершенно нормально
Доказательство опирающееся на собственное доказательство — это не нормально.
Как мы делим алгоритмы, для которых допустимо кидать ошибку или нужно обязательно дать ответ остановится или нет?
Странный вопрос. Видим ошибку — кидаем. Не видим — не кидаем.
Если жёлтый — это неопределённый, то абсурд получается:Выше вы писали, что «Это утверждение Жёлтое» само жёлтое. Или всё же фиолетовое, но тогда оно ложно, потому что абсурд != неопределённость?
Обратите внимание, что каждый бит этих двух записей одного числа попарно отличается.
Не показатель. Хорошо, сделаем так. Пусть мы отобразили все вещественные числа в натуральные, пронумеруем образы по возрастанию, получили новое отображение в [1..], будем работать с ним. Рассмотрим число, равное
x = \sum_{n=1}{\infty} (F^{-1}(n) > 1/2^n ? 0 : 1)/2^n
F^{-1}(n) — прообраз n. Я не пользуюсь представлением числа вообще. Эта последовательность фундаментальна, так как разница между соседними членами не больше чем 1/2^n, следовательно сходится в R. Если некоторому F(x) = k, то 0 = x — x = 1/2^k.
Доказательство опирающееся на собственное доказательство — это не нормально.
В каком месте доказательства выше используется разность множеств?
Странный вопрос. Видим ошибку — кидаем. Не видим — не кидаем.
Да нет же, существовать он может, но должен бросить ошибку, так же как и для любого другого некорректного кода.
Из «алгоритм существует» следует ли что «алгоритм корректен»? Если да, тогда корректен ли тот же алгоритм + отрицание? Что вернёт такой алгоритм при применении на себя?
… берём случайное вещественное число и проверяем есть ли оно уже в нашем рядуВот здесь Цермелло-Френкель с аксиомой выбора рассмеялись.
Именно поэтому не бывает, например, пятеричной логики.Например, бывает. Бывают многозначные логики. И даже бесконечнозначные. И успешно используются.
Но, к сожалению, математика как свернула не туда, так там до сих пор и буксует.Ну так эт, ждём
Вот здесь Цермелло-Френкель с аксиомой выбора рассмеялись.
Вероятностный метод смотрит на Цермелло-Френкеля в недоумении.
Бывают многозначные логики. И даже бесконечнозначные.
Это уже нечёткая логика. И это большой вопрос можно ли называть её логикой вообще.
Вероятностный метод смотрит на Цермелло-Френкеля в недоумении.Вероятностный метод предполагает оценку выбранного элемента. Аксиома выбора она про то, что выбор вообще возможен («берём случайное вещественное число» — утверждение о возможности выбора из бесконечного множества). А любые утверждения с использованием аксиомы выбора, как бы, ничего конструктивного не производят.
Это два не пересекающихся раздела математики. Да и аксиома выбора не про выбор одного элемента из множества, а про населённость декартова произведения семейств множеств.
Однако, машина Тьюринга, в отличие от любой реальной машины, обладает бесконечным объёмом памяти, что не позволяет вот так вот в лоб за конечное время проверить остановимость алгоритма. Тут уже потребуется анализ потока исполнения для ответа на вопрос: "окажется ли указатель исполнителя за пределами произвольно заданного диапазона памяти". Если ответ утвердительный, то по индукции следует, что алгоритм никогда не остановится. Если же отрицательный, то задача сводится к варианту с конечной памятью.
Хотя понятно, что в условиях ограниченного числа ячеек памяти алгоритм или свалится с ошибкой выхода за диапазон, или зациклится, практической ценности рассмотрение такого ограничения не имеет, поскольку количество возможных состояний с ростом числа ячеек возрастает экспоненциально. Можно создать нетривиальный алгоритм, который будет очень долго перекладывать байтики и никогда не повторится. А еще у него будет хитрое и почти невероятное условие, по которому он завершит вычисление. Для каких-то частных случаев останов можно будет предсказать, но в общем случае нет. Такой алгоритм бесконечность считать не будет, но срок времени близкий к времени существования вселенной — запросто. В качестве примера — взлом какого-нибудь криптостойкого кода в условиях, когда неочевидно, что закодированная информация вообще осмысленна.
Понятно, что остановится… А вот, когда — шут знает...
Начал читать и сразу вопрос: Почему желтые утверждения (истинность которых неизвестна) не являются корректными (т.е. голубыми)? Судя по картинкам это так.
Они не корректные лишь с точки зрения классической логики, где никаких неопределённостей быть не может.
Ну вот "2 = +" это синтактический мусор, а "A = B" это вроде бы ок (при условии что А и B тоже синтаксически коректны). Почему оно не в голубом множестве на одной из первых картинок?
Апд. Наверное надо добавить ещё какой-то цвет, это те утверждения про которые мы ещё не думали. Потому что иначе не понятно на следующих картинках как выражение может быть одновременно и желтое и фиолетовое.
В классической логике это обходится так: A=B — это не утверждение, а формула с двумя свободными переменными. Утверждением оно станет, когда вы подставите вместо этих переменных какие-либо утверждения. И только тогда в классической логике можно спрашивать правдиво оно или ложно. А без подстановки — нельзя.
Ну а в четырехзначной как?
В статье же написано..
Вот есть утверждение "This is True" для него мы показали что оно "Can be True" и "Can be False" и поэтому жёлтое. А про "A=B" я ничего не могу показать, каким образом мы его смогли раскрасить?
Кстати firefox ругается на ваши cлайды :(
The loading of “https://raw.githubusercontent.com/nin-jin/slides/master/absurd/fire.jpg” in a frame is denied by “X-Frame-Options“ directive set to “deny“.
Доказательство кантора — конструктивное
Это не так ибо там пропущен шаг конструирования биекции.
оно «строит» число неравное другим числам диапазона.
С тем же успехом можно строить и такое число: идём по ряду натуральных чисел и на каждом шаге прибавляем единичку, а не 0 или 1/2^n как в диагональном методе. Предельный переход и мы получили натуральное число, которое не равно никакому натуральному числу. Это типичный парадокс актуальной бесконечности.
Конструктивисты смотрят на этот метод как на… плохо смотрят, короче.Интуиционисты одобрительно поддакивают конструктивистам.
Понятно, что для произвольного вещественного числа вероятность получить именно его на очередной итерации бесконечно мала. Но так как у нас есть неограниченное число попыток, то математическое ожидание, что оно нам попадётся в ряду хотя бы раз, равно единице.Здесь на слезах Кантора можно будет построить небольшую ГЭС. Но там цирк начинается еще на словах «берём случайное вещественное число».
Бессмысленную риторику, я, конечно, пропущу.
2 = + — некорректное синтаксически высказывание. Его отсекает formation rule.
Вы путаете причину и следствие. formation rule такой, какой он есть, именно для того, чтобы отсекать абсурд. Но не весь абсурд возможно отсечь синтаксически. О чём и свидетельствуют многочисленные парадоксы.
Конструктивисты смотрят на этот метод как на…
О том и речь. Математики разбились на школы и смотря на выводы соседей крутят у виска.
Непонятно, как вы сделали такой вывод.
Бессмыслица не даёт никакой информации о внешних, по отношению к ней, объектах. Вы считаете иначе?
свое доказательство
Вы очень любите приводить везде код на никому не понятных языках. Вы хоть иногда задумываетесь о смысле сего действа?
Бессмысленную риторику, я, конечно, пропущу.
Надо читать как "я почти ничего не понял, так что буду доё докапываться до собеседника по тому, что понял".
Вы путаете причину и следствие. formation rule такой, какой он есть, именно для того, чтобы отсекать абсурд. Но не весь абсурд возможно отсечь синтаксически. О чём и свидетельствуют многочисленные парадоксы.
Именно, поэтому в формальных языках, помимо formulation rules, обычно есть derivation rules.
Бессмыслица не даёт никакой информации о внешних, по отношению к ней, объектах. Вы считаете иначе?
Если некоторое утверждение бессмысленно, то как вы вообще можете разделить объекты на внешние и не внешние по отношению к нему?
Вы очень любите приводить везде код на никому не понятных языках. Вы хоть иногда задумываетесь о смысле сего действа?
О, а вот это — прям каноничный случай парадокса Блаба, прям можно поместить в рамочку и вешать на стенку.
приводить везде код на никому не понятных языках
на никому не понятных
Я надеюсь, вы осознаёте, что если вы чего-то не знаете, то это не значит, что этого не могут знать другие?
Для бессмысленного выражения все объекты внешние.
彼らが理解していない言語で他の人に何かを言うことのポイントは何ですか？
彼らが理解していない言語で他の人に何かを言うことのポイントは何ですか？Смысл в том, что когда вы рассуждаете об основах математики, большинство людей ожидают, что вы хотя бы отдаленно знакомы с синтаксисом latex и формальных ассистентов.
Никто с вами не будет обсуждать формальные исчисления на японском языке или на языке разноцветных прямоугольников.
彼らが理解していない言語で他の人に何かを言うことのポイントは何ですか？
人々があなたとコミュニケーションをとろうとするために使用する言語を理解していない場合、それはあなたの問題であり、あなただけの問題です
Вы очень любите приводить везде код на никому не понятных языках.
Верну-ка я вам ваш старый аргумент.
С таким уровнем аргументации вам сюда: https://fallacy.hyoo.ru/#selected=shape~complexity/filter=selected
В данном случае вы применяете эту технику: https://fallacy.hyoo.ru/#selected=dummy/filter=selected
Жалоба на то, что собеседник намеренно использует непонятный синтаксис, не является аргументом. Вы подменили неопределённость ложью. Что лишний раз показывает непродуктивность бинарного мышления, свойственного классической логике.
https://fallacy.hyoo.ru/#selected=shape~complexity/filter=selected
Хабр всё еще торт? :)
Ужас какой, мой iq уменьшился на 5 от просмотра этой статьи.
1) вы ощутили себя глупым и это знание вычло всего лишь 5 единиц из вашего IQ. Завидую вашей психологической защите.
2) Вы ощутили себя глупым и ваш iq упал до 5. Вы почти присмерти, хлеб сложно будет купить, слова лучше записать на бумажке для кассира. Не завидую вашей психологической защите.
3) Вы издеваетесь и смеясь автору в лицо, сообщаете, что отупели из-за чтения. То есть автор виноват, что вы отпупели.
Хм… пока расписал ваш комментарий понял, что раз вы неточно сформулировали мысль, то есть не предположили вариативности трактовки, думаю вы про пункт 2. Заходите ко мне, попьем чайку
А если серьёзно, рекомендую «Введение в метаматематику» Стивена Клини. Большинство вопросов отпадут.
Но что если утверждение будет говорить о своей собственной ложности?
Если оно правдиво, то из его содержания следует, что оно ложно. Получаем противоречие и отбрасываем. Если же оно ложно, то из отрицания её содержания следует, что оно правдиво. Опять противоречие — снова выбрасываем.
У вас логическая ошибка. Если оно ложное — то из её отрицания следует его не-ложность, т.е. один из трёх вариантов — правдивость, абсурд, неопределенность.
Пока что эта ошибка ни на что не повлияла, но она показывает качество "проработки" логики.
Может показаться, что мы не разрешили парадокс, а лишь убежали от него. И если заменить ложность на абсурдность, то парадокс вернётся вновь. Но давайте рассмотрим и выражение "это утверждение абсурдно".
Предлагаю вместо этого рассмотреть утверждение "это утверждение либо ложно, либо абсурдно".
Если оно правдиво — получаем парадокс. Если оно ложно — получаем парадокс. Вроде бы оно должно быть абсурдным… но в таком случае оно должно быть хотя бы правдивым.
Для обоснования приводится выражение вида "это выражение невозможно доказать". Давайте проанализируем его, как мы умеем. [...]
Если же оно правдиво и непротиворечиво, а ложность мы уже отвергли, то получается, что мы его доказали
Нет, мы его не доказали, ведь кроме ложности для доказательства следует отвергнуть также вариант "абсурд".
Если утверждение "эта система утверждений корректна" ложно, то система утверждений не корректна, то есть противоречива. Если же это утверждение — правда, то система утверждений корректна, что не вызывает противоречий. Соответственно это утверждение не может быть ни чем иным как правдой.
Всё это замечательно, вот только эти рассуждения не имеют никакого отношения к непротиворечивости системы аксиом вашей логики (которые вы даже не попытались привести).
У вас логическая ошибка. Если оно ложное — то из её отрицания следует его не-ложность, т.е. один из трёх вариантов — правдивость, абсурд, неопределенность.
Это не ошибка, а опускание несущественных деталей для простоты восприятия. Неопределённости тут нет, ибо не-ложность исключает и неопределённость. А абсурд — это нулевая гипотеза, которую нет смысла рассматривать отдельно, ибо он и так получается при отвержении всех остальных вариантов. Если выражение абсурдно, то на этом рассуждения заканчиваются и гипотеза отбрасывается.
Если оно правдиво — получаем парадокс… но… оно должно быть хотя бы правдивым.
Эта дихотомия разбирается в разделе про Гёделя.
Всё это замечательно, вот только эти рассуждения не имеют никакого отношения к непротиворечивости системы аксиом вашей логики
Вы невнимательно прочитали. Попробуйте ещё раз. В теореме Гёделя непротиворечивость задаётся как исходная посылка.
Ну а логика не моя. В конце статьи есть ссылка на её описание с аксиомами, правилами вывода, таблицами истинности и вот этим всем.
Это не ошибка, а опускание несущественных деталей для простоты восприятия.
В таких низкоуровневых вещах не бывает несущественных деталей.
Неопределённости тут нет, ибо не-ложность исключает и неопределённость.
С какого перепугу?
Вы невнимательно прочитали. Попробуйте ещё раз. В теореме Гёделя непротиворечивость задаётся как исходная посылка.
С какого перепугу?
Ну а логика не моя. В конце статьи есть ссылка на её описание с аксиомами, правилами вывода, таблицами истинности и вот этим всем.
Но я критикую ваш пост, а не ту ссылку с аксиомами, правилами вывода и прочим.
До кучи:
Вкратце, доказательство Кантора выглядит так: предположим, что для любого вещественного числа существует соответствующее ему уникальное натуральное число. Теперь введём в рассмотрение Санту — некоторое вещественное число, которое по построению не соответствует ни одному натуральному. А в рамках исходной гипотезы, в которой мы не сомневаемся, пока она не опровергнута, его определение эквивалентно следующему: "Санта — это такое вещественное число, которое не равно… никакому вещественному числу".
Вы сейчас что, в принципе запретили приходить к противоречию в рассуждениях от противного? Я ведь точно так же могу поступить с каждым вашим утверждением из этого поста!
Например, вот с этим:
Если оно правдиво, то из его содержания следует, что оно ложно. Получаем противоречие и отбрасываем.
Но ведь в рамках исходной гипотезы утверждение правдивое, значит нельзя рассматривать случай когда оно ложное. Получается, никакого противоречия нет и утверждение из парадокса лжеца — не абсурдное, как попытались показать вы, а правдивое!
Возьмём пустой ряд вещественных чисел и начнём заполнять его так: берём случайное вещественное число и проверяем есть ли оно уже в нашем ряду. Если оно уже есть — генерируем новое. И так далее, пока не встретим число, которое ещё не посчитали. Добавляем его в конец ряда и всё по новой.
Предоставьте ваш алгоритм и генератор случайных вещественных чисел, а мы найдём числа которые он не покрывает.
В теории вероятностей нет никаких генераторов случайных чисел. Есть только выборка из множества, с заданными отношениями вероятностей между элементами. Это не конструктивная математика.
тогда я могу сказать что я буду брать случайное доказательство до тех пор пока оно не окажется правильным. Таким образом я докажу любую теорему. Профит.
Апд. В предыдущем комментарии я процитировал ваше высказывание. оно явно конструктивное.
Это не конструктивная математика.
Как так получается конструктивное доказательство не конструктивно
Апд2. Ну как бы если строить теорию вероятности по честному, через меру и сигма алгебры, то там придется решать задачу с несчётными множествами по новой. Так что никуда от них не уйдёшь. Собственно поэтому нужно сначала решить вопрос с множествами а потому уже браться за теорию вероятности. Иначе теория вероятности превращается в "вероятность встретить динзовара 50%".
А какой ответ вас мог бы удовлетворить? Теорвер принципиально не конструктивен. В нём нет никакого алгоритма генерации случайного числа, ибо тогда оно перестало бы быть случайным.
На практике от теорвера бесконечно больше пользы, чем от несчётных множеств. Так что из двух аксиом, стоит выбирать более продуктивную.
То что аксиоматическая теория вероятностей построена на теории меры вас видимо не беспокоит. Как и интеграл Лебега.
В математике много теорий которые можно вывести друг из друга. Выбор какая теория будет базовой, а какая производной, достаточно произвольный. Хорошие кандидаты на базовость — достаточно простые, интуитивно верные и содержащие не выводимые из других теорий части.
Но всё, на самом деле, ещё хитрее: из частей одной теории могут выводиться части другой, из которых уже новые части первой. Главное, чтобы в выводах не было циклов.
Осень.
Возьмём любое натуральное число, например единицу (для простоты), добавим к нему одну десятую, получим действительное число, а помимо того — алгоритм задания взаимного соответствия, который можно применить к любому натуральному числу и в результате получить соответствующее каждому натуральному действительное число. Подчеркну — каждому натуральному, не смотря на бесконечность их количества.
Теперь берём число, например, 0.5. И видим, что если мы применили выше показанный алгоритм, то для действительного числа 0.5 не останется натуральных чисел, не вошедших в отношение с действительными.
Более полный вариант доказательства счётности мог бы выглядеть так — сначала отменяем общепринятую в неаксиоматической теории множеств аксиому (которая есть просто привычное всем определение). Это определение сообщает нам, что счётным можно признать множество, каждому элементу которого можно сопоставить натуральное число. Если мы заменим эту аксиому на следующую — счётным можно признать множество, каждому элементу которого можно сопоставить уникальный идентификатор, то сразу появляется пространство для манёвра в случае с числом 0.5 и сопоставлением натуральных чисел с их суммой с одной десятой. Например, можно задать идентификатор в виде натурального числа, соответствующего интервалу в одну десятую, и ещё пары натуральных чисел a и b, соответствующих соотношению a/b, дающему в результате целевое значение для действительного числа, которому мы сопоставляем идентификатор.
Точно так же можно разрешить все парадоксы в вашей статье — просто меняем ваши аксиомы или вводим новые. Например, брадобрей может удовлетворять всем условиям, если мы удалим аксиому, запрещающую множествам бреющихся и бреемых пересекаться. Тогда Санта станет живым.
Ну и более общий вариант — ваша сколько угодно многомерная логика всё же опирается на логический вывод, который остаётся всё тем же — задаём аксиомы, строим правила вывода и далее получаем следствия. И для этого набора существуют вполне строгие правила — если вы получили абсурд (или противоречие), то значит вы задали некорректный набор аксиом. Или неполный (в явном виде у вас вообще аксиомы не обозначаются, что сводит их количество к нулю). Как только задаите корректный набор аксиом и правил вывода, так сразу исчезнут все парадоксы и абсурды.
Кстати, абсурд, это отсутствие смысла. А смысл задаётся исходными аксиомами. Если смысла нет — вы некорректно задали набор аксиом, потому что он позволяет выводить бессмыслицу. То есть нет разницы между противоречием и абсурдом, они оба есть следствие некорректности (неполноты) набора аксиом.
А еще вот никогда не понимал «парадокс Брадобрея»: сначала принимается аксиома, что существует 2 не пересекающихся множества. Затем вводится новая аксиома, что множества пересекаются. А вывод об абсурдности делается на основании несоответствия первого набора аксиом новой аксиоме. Получается, что первый набор аксиом, который не полностью описывает систему, оценивают против набора, который полностью ее описывает и делается вывод, не о неполноценности «неполного набора», а об абсурдности всей системы. Странно…
Понятно, что для произвольного вещественного числа вероятность получить именно его на очередной итерации бесконечно мала.
Не «бесконечно мала», а «точно равна нулю» и поэтому даже если у вас бесконечно число попыток, то множиться оно будет на 0. И все последующие рассуждения про равенство бесконечностей уже не имеют смысла. Чтобы ваш аргумент сработал, вам нужно определить свою теорию вероятности. Но с этим будут некоторые проблемы.
Но давайте попробуем порассуждать, что будет если «бесконечно мала вероятность» все таки есть. Возьмем интервал [0, 1] и допустим, что вероятность попасть бесконечно тонкой указкой в число 0.5 (и любое другое) равно dk. dk это такое специально число, с особыми свойствами — «бесконечно малая величина». Основное свойство — любая конечная сумма таких величин равна самой величине, то есть dk + dk = dk
В нашем примере интеграл от 0 до 1 по dk равен 1, это требование тер вера. Теперь возьмем интервал [0, 2] и допустим, что вероятность попасть бесконечно тонкой указкой в число 0.5 (и любое другое) равно dq. Интеграл от 0 до 2 по dq будет равен 1. Отсюда можно сделать вывод, что 2*dq = dk, то есть dq + dq = dk, но выше мы договорились, что dq + dq = dq. Беда. Если же сказать, что dq = dk, то получится, что вероятность попасть в 0.5 на интервале [0,1] такая же как и на интервале [0, 2], то же беда.
Понятие «бесконечно малых» было популярно в 19 веке, но сейчас не используется в стандартной математике, потому что его было сложно определить точно. Есть нестандартный анализ, в котором «бесконечно малая величина» есть. Удобно сказать, что dx это такое специальное число, «бесконечно малое число», за это топил Лейбниц. Кроме проблемы, описанной выше возникает намного большая. Если dx добавить в поле вещественных или комплексных чисел, то появляются делители нуля, а поле перестает быть полем. Это значит, что уравнения уже просто так не решаются, существенная часть результатов линейной алгебры идет лесом и много чего еще.
Не «бесконечно мала», а «точно равна нулю» и поэтому даже если у вас бесконечно число попыток, то множиться оно будет на 0.
Бесконечно малое — это вообще функция. Пределом её будет ноль, но это не имеет значения. Важно, что для любой дельты в окрестности заданного числа вероятность попасть в неё не нулевая.
Тут есть ещё и такое элегантное доказательство:
- Вероятность быть выбранным на очередной итерации равна для любых чисел — это постулируем.
- Если вероятности на одной итерации равны, то и вероятности на бесконечном числе итераций тоже равны.
- Сгенерируем одно случайное число. Вероятность его выборки хотя бы раз на бесконечном числе итераций равна 1 ибо мы его уже сгенерировали.
- Следовательно вероятность выборки любого числа на бесконечном числе итераций хотя бы раз равна 1.
Понятие «бесконечно малых» было популярно в 19 веке, но сейчас не используется в стандартной математике, потому что его было сложно определить точно.
Это первый курс матана..
Вероятность получить число 1 на каждом шаге х. Вероятность не получить его за n шагов (1-х)^n. Как раскрыть эту неопределенность?
В чём неопределённость-то?
x=0, n=infinity
Тут нет неопределённости, предел равен нулю.
на каком основание вы разрешаете очерёдность взятия пределов?
если предположить линейную связь между 1/x и n то получится как известно e
можно предположить что 1/x растёт быстрее тогда получится 1, можно предположить обратное и получить 0. Чтобы это решить надо понять связь между множеством числа шагов, т.е. натуральных чисел и множеством вещественных. Т.е. от главного вопроса у вас уйти не получится, как я писал уже выше
- Взятие предела по x до n теряет информацию и даёт явно некорректный результат (невозможно сгенерировать никакое число).
2,3. Нет никакой связи между ними. Иначе они бы выражались одной переменной.
Хорошо теперь рассмотрим вероятность сгенерировать число A на шаге n+1, Это x * (1 — x) ^ n = 0 для любого n.
Вероятность сгенерировать конкретное число за любое конечное число шагов бесконечно мала, да.
Ой. Это был не тот контр пример, лучше рассмотреть вероятность получить на каком-то шаге любое натуральное число на от 1 до n, т.е. x * n. Теперь чтобы найти вероятность получить любое натурально число, надо взять n = бесконечность. Поскольку это должно быть < 1 вам придётся наверно сначала брать предел по икс. Тогда все же как понять очерёдность пределов...
Не очень понял суть, но чего вы пытаетесь добиться? Опровергнуть теорию вероятностей?
Да я показываю что ваша интерпретация теории вероятности не верна.
Даже если вам это удастся, вы же понимаете, что из этого не будет следовать, что существуют несчётные множества?
Существование несчетного множества это другая теорема. О том, что множество всех подмножеств несоизмеримо с исходным. Правда классическое доказательство — от противного.
Там тоже используется Санта, причём в чистом виде, безо всяких диагональных методов.
Санта — выдуманная вами сущность. Вы ее сами вводите, сами показываете, что получается ерунда, но вывод почему-то делаете не о том, что это проблема в ваших рассуждениях, а о том, что это с теоремами (которые в оригинале никакого Санту не вводят) что-то не так.
Вы, прежде, чем бросаться обвинениями, ознакомьтесь сперва с предметом: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%B0%D0%BD%D1%82%D0%BE%D1%80%D0%B0
Вообще, Савватеев тут говорит замечательную мысль: "если вы не готовы поверить в существование Санты, то вы не математик".
Вы, прежде, чем бросаться обвинениями, ознакомьтесь сперва с предметом:
Ctrl+F, "Санта", 0 результатов. Сформулируйте строго, что вы пытаетесь доказать или оспорить, тогда и посмотрим, кого надо знакомить с предметом.
Ну в видео оно немного путано объясняется. Проще рассуждать так. Рассмотрим произвольную функцию f: A -> 2^A.
Определим B как
В = {x ∈ A: x ∉ f(x)}. (1)Теперь давайте узнаем существует ли y ∈ A такой что f(y) = B. Тут начнём действовать от противного — пусть существует.
Если y ∈ B то по условию (1) имеем y ∉ f(y) — противоречие.
Если y ∉ B то по условию (1) имеем not (y ∉ f(y)) => y ∈ f(y) — противоречие.
Следовательно не существует такого y, который был бы образом B для функции f.
Таким образом для любой функции f, существует такой B, который не принадлежит отображению f. Следовательно биекция невозможна.
Т.е. Санта это "множество всех подмножеств"?
Так ответьте на последний вопрос. Всё таки x * n чем равно, и как это показать? Условно говоря если 1/x "больше" n тогда вероятность не найти данное число равна одному. И наоборот.
Вы говорили о бесконечно малой вероятности, а это число, его и обсуждали. Бесконечно малые как функции или ряды мне известны, но вы же не имели в виду, что вероятность выбрать вещественное число равна какому-то ряду?
В множестве R содержится счётное количество дельта окрестностей и несчетное количество чисел. Занумеровать окрестности — пожалуйста, занумеровать сами числа — не выйдет.
Постулат #1 верен только если вероятность равна 0, иначе интеграл по бесконечности чисел разойдётся, а должен быть 1. Хотите чтобы сходился к 1 — вводите бесконечно малые числа и разгребайте последствия.
Допустим, ваша математика не противоречива, и нам дарован свыше волшебный генератор вещественных чисел, которым вы так лихо оперируете (сама принципиальная осуществимость которого уже крайне сомнительна).
Решите задачу #1: Какова вероятность на произвольной итерации получить положительное, либо отрицательное число?
Решите задачу #2: Какова вероятность на произвольной итерации получить число больше, либо меньше одного миллиона? (подсказка: воспользуйтесь выводом из первой задачи, значение один миллион не имеет значения)
Решите задачу #3: Какова вероятность на произвольной итерации получить число в диапазоне от нуля до миллиона, если пользоваться результатами первых двух задач?
Решите задачу #4: Какое количество попыток необходимо совершить, чтобы получить число в диапазоне от нуля до миллиона с вероятностью 50%, исходя из результата третей задачи? (подсказка: значение 50% не влияет на ответ, но у вас может быть другое мнение)
Мне интересен ваш ход мыслей.
Если оно ложно, значит доказать его всё же можно. А если можно доказать, то оно правдиво. Противоречие — отбрасываем. Если же оно правдиво и непротиворечиво, а ложность мы уже отвергли, то получается, что мы его доказали. А оно говорит о своей недоказуемости. Опять противоречие — снова отбрасываем. А так как мы только что доказали, что оно не может быть ни правдивым, ни ложным, значит оно абсурдно.
Теорема Гёделя не о том, что существуют недоказуемые утверждения в сферическом вакууме, а о том, что существуют утверждения, недоказуемые в заданном наборе аксиом. Да, они будут истинными, но ваше утверждение о том, что мы "доказали" утверждение по Гёделю и тем самым якобы получили противоречие — неверно, потому что теорема Гёделя не входит в вышеуказанный набор аксиом.
Получается, что Санта сам не может быть вещественным числом. Однако, ранее мы постулировали, что такой Санта среди вещественных чисел есть.
Не постулировали, а предположили.
в заданном наборе аксиом
В произвольном достаточно сильном.
Да, они будут истинными, но ваше утверждение о том, что мы "доказали" утверждение по Гёделю и тем самым якобы получили противоречие — неверно, потому что теорема Гёделя не входит в вышеуказанный набор аксиом.
Не смог распарсить эту мысль. Я ничего "по Гёделю" не доказывал.
Не постулировали, а предположили.
Как-то очень уж безусловно предположили. Это и называется постулат.
В произвольном достаточно сильном.
Но, тем не менее, заранее заданном и фиксированном. Суть теоремы — для любого фиксированного набора аксиом, обладающего определеными свойствами, есть утверждения, которые не могут быть доказаны или опровергнуты в рамках именно этого набора аксиом (а не любого "произвольного достаточно сильного"). Если верность этих утверждений показана каким-то другим способом — никакого противоречия не возникает.
Не смог распарсить эту мысль.
Бывает.
Как-то очень уж безусловно предположили. Это и называется постулат.
Это ВЫ "безусловно предположили". А Кантор тут ничего не предполагает — он просто приводит алгоритм, который строит вещественное число, не входящее в "пересчитанные". Поэтому вы "опровергли" сами себя, но не Кантора.
Определение. Вещественное ℝ число есть бесконечная десятичная дробь, то есть выражение вида:
±a(0),a(1)a(2)...a(n)… где a(0)∈ ℤ, т a(i)∈{0,1,2,3,4,5,6,7,8,9} для ∀ i∈ ℕ ( Отсюда ru.wikipedia.org/wiki/Конструктивные_способы_определения_вещественного_числа#Теория_бесконечных_десятичных_дробей )
Факты:
(1) Все точки отрезка [0, 1] имеют мощность континуума c ( https://ru.wikipedia.org/wiki/Континуум_(теория_множеств) )
(2) Счётны множества всех конечных слов над счётным алфавитом и множество всех слов над конечным алфавитом. ( ru.wikipedia.org/wiki/Счётное_множество )
(3) Счётными являются объекты, получающиеся в результате рекурсивных процедур.
Получается, что, с одной стороны на интервале [0,1] все вещественные числа мы можем записать в десятичном виде по определению, а с другой стороны, согласно определению выше — это множество будет иметь континуальную мощность.
Но, множество таких записей в силу (2) счётно, а значит на интервале [0,1] существуют такие числа из ℝ, которые не попадают в наше множество, а значит их невозможно записать в виде бесконечной десятичной дроби. И не по причине того, что там бесконечность. Построить процесс перечисления(вычисления) всех возможных записей десятичных дробей вплоть до бесконечности как раз никакого труда не составляет(см. ниже). А получается в принципе нельзя, т.к. они не представимы в таком виде, поскольку дополнение с/ℵ(0) ≠ ∅
Получается, что не любое вещественное ℝ число представимо в виде бесконечной десятичной дроби?
Поскольку все десятичные числа на интервале [0,1] имеют вид 0,a(1)a(2)...a(n)…, при том, что числа {0,05; 0,050; 0,0..05(0) } — неотличимы, то нам достаточно рассмотреть множество S всех строк из десятичного алфавита без терминального 0(в том числе бесконечной длины), которое будет содержать все возможные записи мантисс действительных чисел в силу определения.
S = {
0.1 -> '1', 0.2 -> '2', ..., 0.9 -> '9',
0.01 -> '01', ..., 0.99 -> '99',
0.001 ->'001', ..., 0.999 ->'999',
…
}
Для каждой длины строки n несложно рекурсивно перебрать все возможные комбинации:
n=1: 0...9
n=2: 01,02, ...,99
n=3: 001, ..., 999
…
n: (0 n раз)1… (9 n раз)
∀ n∈ ℕ
С точки зрения заполнения интервала [0,1] процесс построения чем-то похож на заполнение ru.wikipedia.org/wiki/Канторово_множество, но только наоборот(не вырезаем, а достраиваем относительно десятой части каждого полученного отезка).
При n→∞ получим бесконечное множество S строк различной длины, которое перечисляет все возможные комбинации цифр десятичного алфавита по построению.
Такое множество задаётся рекурсивным способом, а значит в силу (3) оно является счётным.
На множестве S естественным образом (по длине строки и десятичным знакам) задаётся отношение частичного порядка и взаимно однозначное соотношение между ℕ и S можно задать аналитически, а не только рекурсивно.
Если,
( a ) len(s) — функция, возвращающая длину строки;
( b ) pad(n, l) — функция, преобразующая число n в строку и добавляющая слева число нулей так, чтоб общая длина строки стала равна l;
( c ) num(s) — убираем з строки лидирующие нули и строку преобразуем в целое число;
(d) ⌊x⌋ — «антье», целая часть числа, округленная в меньшую сторону.
то пусть: ∀s∈S, ∀n∈ℕ, l = len(s), k = num(s)
F(s) = 10^(l-1) — ⌊k/10⌋ + k — 1 (для строки вычисляем её номер)
G(n) = pad(x,l), где x — корень уравнения: x — ⌊x/10⌋ = n — 10^(l-1) + 1 (по номеру вычисляем строку, но тут потребуется рекурсия глубины l для вычисления решения уравнения)
Примечание: Ещё раз, чтоб не было безсмысленных споров — это рассуждение не доказательство счётности континуума, а рассмотрение случайно возникшей гипотезы, что не все вещественные числа представимы в десятичной форме, даже бесконечной длины, из-за того, что не понимаю, где тут ошибка :) Поможете её опровергнуть?
Множество бесконечных строк над конечным алфавитом несчетно.
Про построение — фокус в хвостах рядов. Множество голов рядов — счётно, а вот хвостов — нет.
А можете пояснить, что вы имеете в виду под «голов» и «хвостов», и какой «фокус»?
Вкратце:
1) Я же рассматриваю только интервал [0,1], который есть континуум.
2) Затем, согласно определению десятичной записи числа определяю множество строк, которые фактически соответсвуют всем возможным формам записи таких чисел, в том числе и бесконечной длины.
3) Показываю биекцию между этим множеством и множеством натуральных чисел.
4) Констатирую, что дополнение счётного множества до континуума непусто, из чего делаю вывод, что «все возможные формы записи десятичного числа на интервале [0,1]» не содержат некоторые вещественные числа.
Какой конкретно шаг, или какое утверждение, на ваш взгляд ошибочно?
P.S.
Множество бесконечных строк над конечным алфавитом несчетно.
Это да. Но построение множества «всех возможных форм записи десятичного числа на интервале [0,1]» (S) легко описывается как рекурсией, последовательно перебирая все возможные вараинты для каждой длины строки, так и аналитически между таким множествои и натуральными числами задаётся биекция при помощи вычислимых процедур, что однозначно говорит о его счётности. Либо тут S строится некорректо и не содержит некоторые десятичные числа, описывая лишь некоторое счётное подмножество вещественных числел таким построением. Но тогда какие числа(какого вида) сюда не входят? Вот этого я понять не могу…
Вещественное число это не бесконечная десятичная дробь, а предел последовательности. Видимо ошибка здесь.
Но вся незадача, возникла от того, что сама по себе процедура представления «всех форм представления вещественных чисел в десятичной форме на интервале [0,1]» формирует счётное множество, из чего следует либо: (1) либо такое построение описывает представление не всех вещественных чисел — но, тогда какие не описывает?; (2) либо существуют десятичные числа, принципиально не представимые в десятичном виде — тогда что это вообще такое?
Но натуральные числа обладают тем же самым свойством — для записи бесконечно большого натурального числа тоже нужно бесконечное число цифр.Не существует «бесконечно большого натурального числа». Существуют лишь натуральные числа произвольно большого, но все еще конечного размера.
Вы путаетесь между понятиями актуальной и потенциальной бесконечности.
Для любого, сколь угодно большого натурального числа, необходимо счетное и конечное количество цифр для его записи.
Для любого иррацинального числа, сколь угодно большого количества цифр будет недостаточно, чтобы записать его.
Счётны множества всех конечных слов над счётным алфавитом и множество всех слов над конечным алфавитом.Ключевое слово – «конечных». Запись числа Пи не является конечной в десятичной форме.
Счётными являются объекты, получающиеся в результате рекурсивных процедур.Ключево слово – «результат». То есть только при условии остановки вычисления в том смысле что каждый элемент множества потенциально осуществим – вычисляется за конечное число итераций.
на интервале [0,1] все вещественные числа мы можем записать в десятичном виде по определению«Можем записать» – это очень сильное утверждение, поскольку бесконечное количество чисел на этом интервале будет иметь бесконечное представление, а бесконечное количество цифр мы записать не можем в том смысле, на который вы опираетесь.
Но, множество таких записей в силу (2) счётноНет, потому что это множество будет состоять в том числе из актуально бесконечных, а не только конечных записей.
Получается, что не любое вещественное ℝ число представимо в виде бесконечной десятичной дроби?Зависит от того, как вы определяете «любое вещественное число» и «представимость». В классическом понимании, вещественное число можно представить в виде потенциально бесконечной десятичной дроби в том смысле, что вы можете сконструировать алгоритм, позволяющий узнать i-ую цифру записи, для любого конечного значения i. Но это не значит, что записать полностью число пи – потенциально осуществимая операция, поскольку требует актуально большого количества цифр. В таком смысле можно говорить, что иррациональные числе не представимы в виде десятичной дроби.
нам достаточно рассмотреть множество S всех строк из десятичного алфавита без терминального 0Здесь ошибка состоит в том, что каждому иррациональному числу будет соответствовать мантисса актуально бесконечной длины, а значит и «натуральное число бесконечной длины», но таких натуральных чисел просто не существует.
Игнорируйте эту часть. Вы очевидно ссылаетесь на вторую часть определения, а я крутикую первую.Счётны множества всех конечных слов над счётным алфавитом и множество всех слов над конечным алфавитом.Ключевое слово – «конечных». Запись числа Пи не является конечной в десятичной форме.
Тут скорее имеет смысл поднять вопрос, будет ли содержать такое множество слова бесконечного размера. Содержит ли множество натуральных чисел значения бесконечной длины? В смысле потенциальной бесконечности – да, в смысле актуальной бесконечности – нет.
Вы путаетесь между понятиями актуальной и потенциальной бесконечности.
Не путаю) Я не знал от такой классификации бесконечностей. Спасибо большое за ссылки.
В классическом понимании, вещественное число можно представить в виде потенциально бесконечной десятичной дроби в том смысле, что вы можете сконструировать алгоритм, позволяющий узнать i-ую цифру записи, для любого конечного значения i.
В принципе, это же рассуждение применимо и к натуральным числам, поскольку некоторое натуральное тоже число можно представить в виде потенциально бесконечной десятичной записи цифр. Ограничений на длину такой записи нет.
Здесь ошибка состоит в том, что каждому иррациональному числу будет соответствовать мантисса актуально бесконечной длины, а значит и «натуральное число бесконечной длины», но таких натуральных чисел просто не существует.
Собственно, это как раз то самое противоречие, к которому я и пришёл. Натуральное число бесконечной длины — это же бесконечность, как предел ряда натуральных чисел, а он сам по себе не является натуральным числом. Я рассматриваю не совсем строки «бескончной дины», а математический объект, который по построению не имеет ограничений сверху на длину своего представления. В том же самом смысле, в котором «сверху» не ограничено множество натуральных чисел.
Как хорошо заметил 0xd34df00d
Все интересные на практике числа вычислимы (включая всякие там корни из двух, пи, е и так далее), но есть бесконечно много невычислимых чисел. Показать на них пальцем конструктивно не получится по определению.
По сути, ларчик просто открывался: Я строил множество заведомо вычислимых чисел. А порядок на множестве вычислимых действительных чисел изоморфен порядку на множестве рациональных чисел.
Соответственно множество всех вычислимых чисел является счётным множеством, а множество вот всех невычислимых чисел — несчётным.
В принципе, это же рассуждение применимо и к натуральным числам, поскольку некоторое натуральное тоже число можно представить в виде потенциально бесконечной десятичной записи цифр. Ограничений на длину такой записи нет.
Но любая бесконечная последовательность цифр натуральным числом от этого не станет (…11111 вам как контрпример).
Вещественное число это как раз бесконечная десятичная дробь. А предел последовательности мы посчитать не можем пока у нас нет определения вещественного числа.
А аксиоматически определить вещественные числа труда не составляет.
С точки зрения современной математики, множество вещественных чисел — непрерывное упорядоченное поле. Это определение, или эквивалентная система аксиом, в точности определяет понятие вещественного числа в том смысле, что существует только одно, с точностью до изоморфизма, непрерывное упорядоченное поле.
А пример привести можете? У меня вот не так давно не получилось...
Ну берёте обычное R и строите его нестандартный аналог R*.
А является ли R* полем?
Кстати, то ли я что-то фундаментально не понимаю, то ли существует вышеупомянутое непрерывное упорядоченное поле, но счётной мощности
Q не является непрерывным. Более того, любое упорядоченное поле будет содержать Q, а непрерывное замыкание Q даёт R.
Есть бесконечно много структур, ...
Практически всё сказанное в этом тезисе, мягко говоря, неверно. Ну, или я вас и со второго раза не понял.
Множество вещественных чисел — непрерывное упорядоченное поле. Это определение, или эквивалентная система аксиом, в точности определяет понятие вещественного числа в том смысле, что существует только одно, с точностью до изоморфизма, непрерывное упорядоченное поле. (см. пример доказательства)
Но, множество таких записей в силу (2) счётно
Нет, потому что слово — конечная последовательность символов, а вещественные числа записываются бесконечными.
а вещественные числа записываются бесконечными.
Не все, а некоторые. Например, все целые и рациональные числа, которые очевидно являются так же и вещественными не требуют для своей записи бесконечной последовательности символов. Более того, формально можно даже рассматривать и строки «произвольной длины» — n, если аналитически задать выражение от n, а n устремить к бесконечности.
Собственно о том и речь, что как буд-то получается, что даже имея возможность записать некоторое вещественное число с бесконечной точностью, то у вас это всё равно не получится, т.к. среди вещественных существует ещё некоторое подмножество континууальной мощности таких чисел, которые множеству записей при помощи цифр конечного алфавита не принадлежат. Вот я и хочу понять, в чём именно я ошибаюсь:)
что ваш алгоритим заполнения не работает
Да, вы правы. Спасибо.
Допустим, нам нужно сгенерировать рациональное периодическое число. Тогда ответьте, на каком номере итерации алгоритма будет сгененировано число 0.(1) (равное 1/9)? Или другими словами — если можно рассматривать реальные числа как последовательность десятичных знаков, то что мешает удалить из этой последовательности запятую и рассматривать оставшиеся знаки (бесконечное их количество) как натуральное число?
И ещё вопрос — а существует вообще доказательство бесконечной длины реальных чисел? Для рациональных чисел это известно — они периодические и период повторяется бесконечное число раз. А для остальных? Может у них есть период? Но бесконечно большой? Или просто где-то есть конец.
Иррациональные алгебраические числа получаются посредством выполнения алгоритма извлечения корня, но как раз для такого подхода ваш ответ приводит отличное опроврежение в виде «приведите номер шага алгоритма, когда мы получим всё число».
И если вы не приведёте шаг алгоритма, то получается, что генерация алгебраических чисел невозможна, что возвращает нас к двум видам бесконечности, которые используются при опровержении возможности получить натуральное число с бесконечным количеством знаков. Или другими словами — это же опровержение можно использовать для бесконечности длины алгебраических чисел (а заодно и для трансцендентных).
Получается, что либо мы отказываемся от бесконечности «и там и там» (для реальных и для натуральных чисел), либо мы соглашаемся с наличием бесконечности, но тоже «и там и там».
что мешает удалить из этой последовательности запятую и рассматривать оставшиеся знаки (бесконечное их количество) как натуральное число
Определение натуральных чисел.
а существует вообще доказательство бесконечной длины реальных чисел?
Реальных — это каких? Если вы имеете в виду вещественные — то это просто одно из их определений.
Вы, в общем-то, возразили против чуть ли не самой известной аксиомы математики (о обесконечности числового ряда). И сослались при этом на саму математику. Как вам доказывать что-то при таком противоречивом наборе аксиом, я не знаю.
Допустим, нам нужно сгенерировать рациональное периодическое число. Тогда ответьте, на каком номере итерации алгоритма будет сгененировано число 0.(1) (равное 1/9)?Ни на каком, у этого рационального числа знаменатель не степень десятки, о чём я упомянул.
Или другими словами — если можно рассматривать реальные числа как последовательность десятичных знаков, то что мешает удалить из этой последовательности запятую и рассматривать оставшиеся знаки (бесконечное их количество) как натуральное число?Выше ответили.
И ещё вопрос — а существует вообще доказательство бесконечной длины реальных чисел?Выше ответили.
Или просто где-то есть конец.У некоторых есть конец (число 0.3), у некоторых нету (число пи).
Иррациональные алгебраические числа получаются посредством выполнения алгоритма извлечения корня, но как раз для такого подхода ваш ответ приводит отличное опроврежение в виде «приведите номер шага алгоритма, когда мы получим всё число».Не осилил. Если вы спрашиваете алгоритм нумерования алгебраических чисел, то вот он: перебираю все строки из метаматических операторов, цифр и буквы Х в лексиграфическом порядке. Каждую строку проверяю на то, является ли она валидным уравнением. Если да, и уравнение степени k, то k его корней добавляю в множество всех алгебраических чисел (изначально пустое). Очевидно, что в множестве будут дубликаты, но это ничего страшного, меньше чем счётно все равно не бывает бесконечности (продумывать удаление дубликатов мне сейчас лень). Обратите внимание, что «решать „уравнение не надо (и не возможно). Числа в моём конструкте определяются как Pair<String, int> — кортеж из уравнения и порядкового номера его корня по возрастанию.
Получается, что либо мы отказываемся от бесконечности «и там и там» (для реальных и для натуральных чисел), либо мы соглашаемся с наличием бесконечности, но тоже «и там и там».Не осилил. И натуральных, и вещественных чисел бесконечно. Одних счётно, других несчётно.
Я думаю любое вещественное число можно сопоставить с последовательностью, например бинарным поиском (на отрезке [0,1]). Кажется эта последовательность и будет двоичной запись. Потом эту последовательность можно перевести в десятичную запись.
Ошибку в алгоритме показали, я добавлю об ошибках на уровне определений.
Не все, а некоторые.
Неважно. Суть в том, что множество "записей" вещественных чисел с помощью алфавита вообще не является "множеством слов над алфавитом", следовательно, ваши ссылки на (2) и все следующие из этого выводы ошибочны.
формально можно даже рассматривать и строки «произвольной длины»
Произвольная (сколь угодно большая), но конечная длина и бесконечная длина — это принципиально разные понятия.
«Счётная» — не значит «конечная». Множество натуральных чисел счётно и бесконечно. Бесконечности сами по себе тоже бывают разные. Множества вещественных и натуральных чисел оба бесконечные, но одно «алеф-ноль», а второе «алеф-один».
Получается, всё, что нам нужно сделать — это исполнить алгоритм, на каждом шаге запоминая полное состояние памяти и сравнивая его со всеми предыдущими состояниями. Как только состояния совпадут — говорим, что алгоритм не останавливается.
Как это работает для программы, которая выводит "Press any key for exit" и ждет нажатия any key, даже если мы точно знаем, в какой момент она будет нажата, и подаем это на вход анализатора? По-моему никак.
Никак, машина Тьюринга не умеет в ввод/вывод.
Я что здесь, не понял. Программа такая есть, а машиной Тьюринга она смоделированна быть не может? Я может быть не прав, но вроде подразумевается, что компьютер это машина Тьюринга да ещё и с конечной лентой разве нет? А если нет, то в чем практическая польза машины Тьюринга если она не применима к реальным программам? Если машина Тьюринга не может описать реальную программу, то и никакие выводы основанные на рассуждениях с машиной не применимы к реальным программам. Получается пчелы против меда, компьютер не может быть описан математически, какой то это абсурд или магия.
Если мне не кажется, то состояние ожидание ввода вывода это и есть не останов/зацикливание машины Тьюринга. При этом факт ввода это изменение состояния ленты НЕ машиной Тьюринга — извне, но при этом это изменение может прервать бесконечный цикл и завершить программу. Т.е. по какой угодно логике, ваш оракул должен выдать программа не завершается (сама по себе с заданной лентой, что как бы подразумевается).
Машина Тьюринга — модель простейшего вычислителя. Ничего удивительного, что он не поддерживает ни DMA, ни прерывания, ни синхронизацию ядер, ни кеши разных уровней. Тем не менее она позволяет математикам выводить некоторые теоремы для детерминированных алгоритмов с одним входом.
Любая модель имеет границы применимости, на то она и модель. К программам со вводом-выводом эту модель можно применить аж двумя способами:
- во-первых, любой ввод-вывод можно рассматривать как останов программы и повторный запуск;
- во-вторых, любые вводимые данные можно считать записанными на ленту заранее.
Кеши, ядра, дма, и т.д. никак не влияет, это все просто оптимизации не дающие ничего принципиально отличного от машины Тьюринга, и следовательно никак не отображаются на модель.
Моделирование программы которая ждёт ввода с записанным на ленту вводом это не моделирование, точнее это моделирование другой программы. И мы все такие программы не раз писали называются они тесты.
Ещё раз — ожидание ввода это неостанов для машины Тьюринга и никак иначе. С выводом чуть сложнее т.к. лента у Тьюринга бесконечная то и блокировок не бывает, т.е. ожидание вывода моделируется наложением искусственного для Тьюринга ограничения на размер ленты(не насаму ленту, а на количество ячеек используемых программой через входной параметр) и тоже зацикливание.
Ну и на последок, если бы машина Тьюринга не могла моделировать реальные программы, то это было бы просто не более чем занятное упражнение в математику не имеющее инженерную ценность. Но это далеко не так. Машина Тьюринга это модель не простейшего вычислителя (хотя я думаю имелось ввиду инженерная сложность а не теоретическая), а самого мощного того который может вычислить все что вообще возможно вычислить. А т.к. компьютер не более чем калькулятор и МЕНЕЕ способный чем машина Тьюринга, то утверждение что компьютер и ЛЮБАЯ программа не может быть представлены машиной Тьюринга это ложное утверждение.
Ядра — конкурентный доступ к единой памяти. Кеш влияет на видимость изменений разными ядрами. DMA меняет состояние памяти в обход исполнителя. Простите, что разрушаю тут ваши иллюзии.
Моделирование программы которая ждёт ввода с записанным на ленту вводом это не моделирование, точнее это моделирование другой программы. И мы все такие программы не раз писали называются они тесты.
А по другому никак, иначе придётся моделировать человека, который собственно вводит.
Ядра — конкурентный доступ к единой памяти
Вы вероятно забыли про факт того что ВСЕ дохулион ядер конкурентно пишущих по одному и ТОМУ же адресу будут сериализованны шинной памяти, многоканальность она про одновременный доступ по РАЗНЫМ адресам. Следовательно что моноядерник что дохулион ядерник это тоже самое — машина Тьюринга.
DMA меняет состояние памяти в обход исполнителя
Ну так об это и шла речь — это и есть ввод/вывод и моделируется он прекрасно = зацикливанием и переписыванием ленты.
А по другому никак, иначе придётся моделировать человека, который собственно вводит.
Да нет, не нужно никого моделировать. Что делает программа ожидающая ввод? Висит. Поэтому если мы моделируем ввод то программа ОБЯЗАННА повесить машину Тьюринга. Если мы ввод не хотим моделировать, то да можно записать данные на ленту заранее.
Вам же mayorvp вверху почти правильно написал как это моделируется:
* Программа разбивается на подпрограммы которые ничего не ожидают — привет фп чистые функции.
* В модель вводится програма «менеджер» которая запускает подрограммы и ЗАЦИКЛИВАЕТСЯ на момент ввода вывода.
Так что еще разок — вся инженерная/программисткая сложность современных компьютеров принципиально/фундаментально/теоретически ни как не отличается от машины Тьюринга и прекрасно ею моделируется. А модель из 2 пунктов вверху это вобщем то описание того как компилятор фп языка подходит к проблеме чистых не чистых функций и позволяет ФП программистам писать не упражнения в математику, а нормальные полезные программы.
Наверное мой предыдущий ответ не лучшим спосособом доносит такую мысль:
* Общепринято с помощью машины Тьюринга моделировать ЧИСТЫЕ функции — алогритмы с предоставленным входом, для например анализа алгоритмической сложности. Такое моедилирование и анализ не вызывают ни у кого никаких проблем. И я думаю вы наставиаете, что это и есть то единтсвенное на что способна модель машины Тьюринга.
* В таких чистых функциях, любое зацикливание означает некорректность алогритма.
* Реальные/полезные программы не чистые — имеют побочные эффекты (ввод/вывод), а в терминах машины тьюрига, любой побочный эффект моделируется зацикливанием и поэтому не отличим от некорретного алгоритма.
* Реальные компьютеры — детерминированны (ГПСЧ — детерминирован), а любое истинно недетерминированное поведение невозможно БЕЗ ввода/вывода.
* Чтобы избежать проблемы неразличения причины зацикливания (некорретность или ввод) и происходит разбиение реальной программы на подпрограммы двух типов.
* Чистые, что означает они ничего не ожидают/нет в(ы)вода/побочных эффектов и поэтому их зацикливание == некорректность
* Менеджер — исключительно ожидает ввод/вывод и поэтому его зацикливание не является признаком некорректности.
Любой кто писал корректный сложный локфри код делал это же самое разбиение на участки и затем анализировал свой алгоритм на коретность с учетом гарантий модели памяти в его языке. Так что да, анализ (не очень больших, сложных, многопоточных) программ возможен чисто технически вот прям дюбом квалифициованным инженром. Да делать это для всей программы не представляется практически возможным без автоматизации. Какие нибудь агды или идрисы могут помочь. Схема такая — разбиваете вашу программу на части описанные выше, учитываете гарантии предоставляемые вашим железом и компилятором, а дальше полный перебор (с учетом ограничений вытекающих из гарантий) всех состояий вашей программы (возможного ввода/вывода) и доказательство или опровержение корректности (зацикливание) вашей программы. Т.е. техническая проблема как раз с той частью программы которая — менеджер, проверка всех возможных входных данных (с учетом ограничений) и является ресурсоемкой на практике, но не является принципиальной/теоретической проблемой.
Ну и то что я все это время пытаюсь донести — зацикливание != некорретность в общем случае для реальных програм. И даже наоборот, я могу специально написать тест который будет проверять, что программа ДОЛЖНА зациклиться/ожидать ввод, т.к. это поведение является частью спецификации и следовательно корректным. И для моделирования такого поведние/тестирования мне нужен оракул который скажет, что программа зациклилась/ожидает ввод.
Насколько мне известно уже идет реальная работа в этом направлении называется верификация программ, да сложно и не всегда возможно полное доказательство на практике из за ограниченности ресурсов, но в ТЕОРИИ/ФУНДАМЕТНАЛЬНО полностю разрешимая проблема, т.к. реальный компьютер НЕ способен выполнить ЛЮБУЮ программу. Думаю что для кого нибудь 8086 процессора (с учетом всех его ограничений на доступную память) уже возможно на практике верефицировать/доказать корректность ЛЮБОЙ программы которую можно на нем запустить только это не практично т.к веротяно затребует мощности самых передовых суперкомпьютеров для анализа, что бы выполнить его в разумное время.
Да нет, не нужно никого моделировать. Что делает программа ожидающая ввод? Висит. Поэтому если мы моделируем ввод то программа ОБЯЗАННА повесить машину Тьюринга.
Ну и что дальше, как её отвиснуть?
Т.е. мы можем проверить программу только до первого ввода. Дальнейшее поведения зависит от ввода.
А следовательно не существует соответствия, и одна безконечность, внезапно, может быть больше другой безконечности. Как минимум на один элемент.
Бесконечность плюс один все еще равняется бесконечности. Но тогда имеет место
Бесконечность = бесконечность + один
откуда
0 = 1.
Вроде все сделал, как автор предлагает, что-то несусветица вышла.
«Опровержение» теоремы Кантора, конечно, «шедеврально». В комментариях выше автор говорил, дескать, нет построения биекции в доказательстве, проводимом Кантором.
Вот только это построение и не нужно, доказательство, по своему построению, применимо для любой предполагаемой биекции из N в R. Не буду говорить и о проблемах с аксиомой выбора.
Проблема останова лжеца Гёделя и брадобрея Кантора