Ну... для программистов ZFC всё-таки некоторый оверкилл, для доказательства большинства практических результатов, не относящихся к заумной теории чисел, достаточно аксиоматики Пеано. Да и теория категорий намекает, что топос порождаемый ZFC в общем-то не уникальный.

Мне кажется, Вы что-то путаете. ZFC и арифметика Пеано — это вообще разные вещи. Одна определяет, что есть множество и быть элементом множества, а вторая — что есть натуральное число и базовые операции с ним. А для программистов в работе не нужна ни первая, ни вторая, так как программисты нигде не сталкиваются с бесконечностями, а потому в теории все можно перечислить и для этого не нужны никакие заумные аксиомы. Да и почему Вы выбрали именно ZFC? Чем не устраивает, допустим, NBG?

Да и в теории чисел тоже как-то не особо смотрят на ZFC или арифметику Пеано. Там как-то тоже больше используются конечные мультипликативные/аддитивные поля по остатку какого-то конечного числа.

Это здорово, когда есть альтернативы. Но, видите ли, бывают такие редкие и волшебные «кактусы», которые всего одни в своем роде. И именно внутри них находится ответ на вопрос, который Вы так жаждете получить. Да, возможно, Вы и им найдете какую-то замену, потому что боязно подходить к его иглам. Но все эти «замены» — это всего-лишь контрафакт, которые все будут ходить вокруг-да-около. Потом Вы можете обратиться к знающим людям, которые в конце-концов скажут Вам, что сами они не уверены, но вроде то, что Вы ищете находится в том самом «кактусе».

И если Вы жаждете получить ответ на свой вопрос, именно жаждете, то рано или поздно Вы сожрете тот «кактус», сожрете его с потрохами, и никакие иглы Вас не остановят. Это будет больно, это будет трудно и мучительно, но когда Вы «перетравите» тот самый «кактус», Вы получите свой ответ. И более того, Вы получите знание, которым владеют немногие. Возможно, даже единицы. Вы в каком-то роде станете уникальны.

Видите ли, чем более базовое (не фундаментальное!) знание Вы ищете — тем больше материала можете найти. Просто потому что им владеет очень много людей. Но чем более специализированней знание — тем меньше источников существует. Видимо, Вы просто никогда с таким не сталкивались. Знаете, в свое время в универе у нас даже была шутка, что чем старше становится курс — тем меньше материала по классам мы можем найти в Интернете.

Тут очень в тему будет это короткое видео: https://www.youtube.com/watch?v=89xUz9fZBXA. К сожалению, в этой жизни за все стоящее надо бороться.

Вам, должно быть, лет 20. Поверьте, это проходит.

А откуда Вы знаете, что книга гавно, если Вы не понимаете, что в ней написано?

Я, например, прекрасно осознаю, что я знаю далеко не все. И когда я беру книжку и не понимаю, что в ней написано — то это значит, что книга не для меня. Но есть люди, которые ее поймут и для которых она будет очень ценной. Возможно, в будущем, когда я стану более подготовленным, я смогу и ее прочитать тоже.

Нуу, да. Казалось бы, численные методы должны быть о конкретных вычислениях, но вместо этого Вы получаете Талмуд с доказательствами. Но иначе просто никак.

Представьте, что я Вам скажу, что знаю супер-крутой метод оптимизации, который бьет все остальные методы и в плане скорости сходимости, и в плане выдаваемого результата. Но доказывать я Вам ничего не стану. Само собой Вы не станете верить мне на слово. Можно было бы конечно провести эксперименты, но метод может быть столь запутанный, что сама его реализация займет месяцы работы. Да кто ж станет таким заниматься? Поэтому и нужны книжки, где методы приводятся с доказательствами.

Это просто означает, что эта книжка была предназначена не для Вас. Хорошим тоном считается прочитать предисловие, когда Вы берете какой-то учебник или монографию по математике. Там обычно авторы прямо пишут, для кого предназначена книга. И если книга была предназначена для магистров, докторов или младших научных сотрудников — то совсем неудивительно, что Вы, будучи бакалавром, не смогли в ней разобраться.

Интегралы — это в непрерывной ТВ. Обычно сначала изучается дискретная и из непрерывного там только аппроксимация биномиального распределения через нормальный закон. Но в этом случае интеграл дают как данность. Уже потом или параллельно в курсе матанализа этот интеграл выводят.

А автору до непрерывной ТВ еще ой как далеко.

Вы говорите глупость. Очень многие советские книги — это просто таки кладезь. Книги Колмогорова, Шеня (правда, он то все еще печатается), Гельфанда, Шилова, Шабата — их книги достаточно строги, но в то же время легко читаются. Они как бы взяли лучшее от Бурбаки, то есть строгость выкладок, но при этом их стиль изложения остался легким и естественным. Если Вы зайдете на Амазон, то функциональный анализ Колмогорова и Фомина — все еще в топе. И люди, которые изучают функан, говорят, что именно после этой книжки они смогли понять эту теорию.

Для начала Вы должны принять очень неприятную штуку: Вам никто ничем не обязан. Никто не обязан Вам разжевывать математические концепции и в готовом виде «вкладывать» их Вам в голову. Математика — это тот предмет, над которым, к сожалению, надо думать. И думать самостоятельно. Иначе ее не понять. Поэтому бросайте писать вот такое

занимаются демонстрацией превосходства посвящённых в тему
вместо того, чтобы просто объяснить вещи несведущему читателю.
Они оставляют его один на один с математической тайнописью. Аннигилировать в пустоте.
Примерно так же пишут обычную учебную литературу.

Хотите изучать математику — Вам придётся разбиратьсяв ней. Придется пробираться через дебри непонимания. И это нормально. Иначе никак. Математика — это не программирование. Нет никаких руководств по ней. Вы не сможете скопировать чье-то доказательство себе в редактор и запустить его, чтоб потом модифицировать и посмотреть, что будет. Надо самостоятельно брать книжки и изучать по книжкам. Можно еще онлайн лекции (но только вместе с учебниками!). Но не по википедии! И не по развлекательным видео в интернетиках. Все же вики — это энциклопедия, а не учебник. А развлекательные видосики — ну, это просто развлекательные видосики. Чтоб «ух ты!» и «хаха!» было.

А теперь по поводу каких-то более конкретных рекомендаций. Бросайте штудирование школьных учебников. Школа давным-давно закончилась, да и математика там была неинтересной, догматической и просто вычислительной. Знакомы с самой базовой арифметикой, умеете хоть как-то решать системы линейных уравнений — это все, что Вам надо из школьного курса. Сила математики — в доказательствах, а не в вычислениях. Последние — всего лишь приятный инструмент математики. Но, к сожалению, стандартные школьные учебники не очень сильны в плане доказательств.

Начните изучение математики с того, что в технических универах называется началом дискретной математики. Именно там дается хорошее введение в язык математики и сущность математики. Из учебников могу порекомендовать Rosen . Также слышал очень хорошие отзывы про этот учебник, но сам я им никогда не пользовался.

Но это не значит, что Вы должны прямо засесть за эти учебники и не вставать, пока не разберете каждое слово в них. К сожалению, идеального учебника не существует. Даже в самом хорошем учебнике будут места, которые Вы не сможете постичь. Просто потому, что автор выбрал какие-то слова, которые у Вас в голове как-то не «кликают», не складываются в какую-то четкую картинку. В этом случае начинаете смотреть, а как это понятия, концепция или момент объясняют другие авторы. Вот тут уже можно и посмотреть какой-то развлекательный видосик, где Вам визуально покажут что да как. Но после — возвращаетесь обратно к учебнику. И продолжаете штудирование.

По поводу тем, мне кажется наиболее логичным следующий порядок:

1. Математическая логика. Конкретно логика первого порядка. Логические операторы. Правила логического вывода. Основы аксиоматической теории. Вот тут уже объясняется, что есть матдоказательство и какие существуют стратегии доказательств (их всего 3: прямое доказательство, контрапозитивное и от противного; некоторые авторы отдельно выделяют также доказательства по индукции, но это Вы изучите позже).

2. Комбинаторика. Правила «И-ИЛИ». Перестановки, комбинации, комбинации с повторениями. Бином и мультином Ньютона, биномиальная теорема. Это все надо не просто прочитать определения, а надо уметь выводить их формулы самостоятельно. Только тогда Вы поймете, в каких задачах надо их использовать. Дальше закон включения-исключения. Это вроде все, что надо для базы.

3. Наивная теория множеств. Это основной язык математики и один из фундаментальных теорий математики, то есть на ее основе и на ее языке строится вся остальная математика. Есть и другие фундаментальные теории, например, теория типов или теория категорий, но широкого распространения они приобрели лишь в узких и довольно специфических областях математики, до которых Вам еще рано.

Изучайте именно наивную теорию множеств, а не аксиоматическую, так как последняя Вас просто убьет. Да и подавляющее большинство математиков пользуется именно наивной теорией и не лезет в дебри аксиоматической. Главное — помнить, что нельзя создавать множество всех множеств — и все будет оке.

Тут Вы должны изучить язык теории множеств, операции над множествами, доказательства о включения одних множеств в другие, равенство множеств, и так далее. Отношения и функции. Инъекция, суръекция и биекция. Что есть мощность множества, какие бывают мощности. Бесконечно счетные и несчетные. Диагональный метод Кантора. Уметь всем этим пользоваться! Континуум-гипотеза. Парадокс Рассела и мотивация появления аксиоматической теории множеств.

Тут в принципе должно произойти просветление и осознание, что ВСЕ теории в математике должны базироваться на аксиомах, а не так, как это было прежде в 19ом столетии, когда очень часто математики пользовалась не аксиомами, а скорее интуицией и умозрительными рассуждениями при доказательствах своих результатов, что часто приводило к противоречиям. По факту наша современная математика — ей около столетие, потому что к началу 20го столетия накапливается столько парадоксов, что с начала и где-то по первую половину 20го столетия идет переосмысливание многих разделов математики и постановка их на новый аксиоматический фундамент.

4. Индукция. Тут надо понять, что такое индуктивное доказательство, и почему оно работает. Прорешать много задач (хотя это верно для всех разделов). Узнать про well-ordering principle, но пока только для натуральных чисел! А то так недалеко уйти в жуткое место под названием Аксиома выбора, которую Вы пока не поймете. Полезете читать об этом в интернет, и там вам разные сумасшедшие понарассказывают кучу псевдо-философской пошлой софистики, от которой неподготовленные умы становятся теми, кого математики называют фриками.

Уметь пользоваться простой, сильной и структурной индукцией, также уметь решать задачи с помощью well-ordering principle. Индукцию в принципе любят в вычислительных науках, так как очень многие алгоритмы доказываются через индукцию.

Ну, полагаю, для начала Вам и этого хватит. Тут работы месяца на 4-6, если Вы будете все читать и решать задачи. И да, Вам придется решать задачи. Без этого математику не выучить. Это не прослушать какой-то подкаст, пока Вы ужинаете. Как я сказал в самом начале — изучать математику — это сложно и больно. Но если Вам удасться покорить эти 4 шага — Вы уже будете довольно подкованы в математическом языке. И Вы будете владеть математикой куда лучше, чем большинство народа. А дальше уже можно двигаться в зависимости от Ваших интересов.

Это неважно. Дайте мне описание Вашей машины и алгоритма для решения «сложных» задач, и я всегда смогу построить и «скормить» Вашей физической эмуляции НМТ такой входной пример, что она будет вынуждена «наплодить» безумное количество головок. Иначе говоря, она не способна решать произвольные примеры этих «сложных» задач. А нам именно это интересно в НМТ, поскольку они то способны решать любые входные примеры «сложных» задач.

В этом то как раз и заключается гипотеза экспоненциального времени, что какой бы алгоритм или устройство Вы не придумаете, всегда найдется такой нехороший пример задачи, что алгоритм/устройство будут вынуждены либо работать экспоненциально долго, либо наплодить экспоненциально много подобных «головок».

ПС. На самом деле тут я немножко привираю, когда говорю, что НМТ способны быстро решать задачи, которые не способны решать классические машины. На сегодняшний день это не доказано. Потому то гипотеза экспоненциального времени называется именно гипотезой. Да и проблема NP vs. P — все еще открытая проблема.

Поэтому, по-хорошему, каждый раз, как я делаю подобное заявление, надо добавлять фразу «... кроме случая, когда NP=P». Но этот вариант крайне маловероятен. Скажем так, в то что NP=P верят в основном фрики. Большинство народа верит в неравенство этих вычислительных классов.

Вы, кажется, упускаете мою главную мысль. Машины Тьюринга — это не вычислительные устройства. Это формальная вычислительная модель. И Тьюринг ее задумывал именно как модель абстрактного вычислителя. Это всего лишь абстракция (и я делаю на этом ударение). И как любой абстракции ей как-то плевать на физические ограничения нашего мира. Поэтому Тьюринг ничего не упустил в ней, потому что упускать нечего.

Но при этом это настолько простая и удобная абстракция, что именно ее чаще всего используют в качестве эталонной модели абстрактного вычислителя. Не лямбда-вычисления, не RAM-машины и не конечные автоматы. Именно машины Тьюринга стали стандартом. А все благодаря простоте их описания, легкости визуализации, но в то же время мощности, которая позволяет на них реализовывать все то, что наша интуиция называет алгоритмами.

ПС. А еще благодаря именно своим абстрактным машинам Тьюринг доказал невычислимость проблемы Остановки.

Как МТ, только на каждой ячейке переход головки не просто в следующее место, а может породить новые головки, которые перейдут каждая на свою ячейку.

Ну, да — это по факту и есть недетерминизм. К сожалению, такой подход нереализуем. Все дело в экспоненциальном взрыве. Смотрите, допустим, в какой-то момент времени в результате выполнения «алгоритма» (или концептов) головка разделилась надвое (заметьте, что головка — это материальный объект, который состоит из атомов; это замечание будет важно в дальнейшем). Теперь алгоритм построен так, что каждая из этих головок снова делится надвое. Теперь у нас 4 головки. Через пару итераций они снова все вынуждены разделиться согласно алгоритму. И потом снова, и снова, и снова. И допустим до выполнения задачи они разделились 1000 раз. То есть в конце выполнения алгоритма-концепта у вас будет 2¹⁰⁰⁰ головок. Это число с 302 цифрами. Это в базиллион раз больше, чем предполагаемое количество элементарных частиц в видимой Вселенной! В нашей Вселенной не хватит просто материи для такого количества головок. Да и нет такого количества энергии, чтоб выполнить подобные вычисления

Вы можете возразить, типа, какой дурак будет создавать такой алгоритм. Но именно подобный алгоритм позволяет НМТ решать сложные задачи. Все дело в том, что неспроста НМТ называется формальной и умозрительной моделью. Никто и никогда не реализовал НМТ. И дело тут даже не в бесконечной ленте (в этом случае и детерминированную машину Тьюринга никто не реализовывал). Дело в том, что когда мы говорим, что какая-то задача на НМТ решается за время T, то это значит, что среди всех возможных сценариев «размножения» головок найдется путь длины не больше Т, который приводит к решению задачи. То есть НМТ не запускает все сценарии размножения головок. Она как бы «знает» самый эффективный сценарий, который завершается решением задачи за время Т. Но Ваша то машина не знает этого сценария. И Вы не знаете. И люди тоже не знают. Никто не знает. А НМТ — знает. Именно потому НМТ — это всего-лишь теоретическая вычислительная модель, которая сильнее любого классического компьютера.

Я утверждаю что разумно глупостей не делать.

Это в принципе хороший совет. Но! Проблема НМТ заключается в том, что мы не владеем алгоритмом, который бы позволял нам их эффективно симулировать на обыкновенных, классических машинах. И большинство здравого народа склонно верить, что такого алгоритма и не существует. Более того, есть немалый процент людей, которые полагают, что и квантовые машины нам тут мало помогут. То есть наиболее вероятно, что модель НМТ куда сильнее классических и квантовых машин. Да, есть задачи, которые можно легко решить как на НМТ, так и на классических машинах или детерминированных машинах Тьюринга. Такие задачи мы называем P-задачами. Это те задачи, что в академических кругах называют простыми.

Но есть задачи, которые НМТ легко решает, но почему-то любая попытка их разрешить на классических или квантовых машинах приводит к экспоненциальному времени выполнения. Яркие примеры — это Travelling Salesman Problem (TSP) или Satisfiability (SAT). Поэтому, когда я Вас спросил, что Ваша машина будет делать на подобных задачах, и как Вы планируете решать вопрос об исследовании экспоненциального количества возможных путей, Вы мне ответили:

Та нет никакой беды. И нет экспоненциального взрыва. Если мозги включать, конечно. Так можно испугаться и вечного зацикливания.

Из чего я сделал вывод, будто Вы или Ваша машина «знаете» способ, как за меньшее, чем экспонента времени найти «правильный» путь. Иначе говоря, Ваша машина не просто опровергает ETH, она доказывает, что P = NP — одну из задач тысячелетия. За ее решение институт Клэя дает миллион бакинских.

Поправьте меня, если я все же что-то неправильно понял. Потому что Вы особо ничего о своей машине не рассказываете, ни о ее принципах, ничего. Приходиться додумывать из того, что Вы тут пишете.

Почему не смотрел? Я посмотрел Вашу презентацию. Если честно — ничего не понял. Пока не смотрел, еще как-то что-то мог додумать из Ваших сообщений.

У Вас какие-то концепты, которые даже не понятно, что это такое. Это структура данных, формат команд или же это абстракция? То есть физически это что? Дальше Вы там рисовали схему переходов состояний Вашей машины. Такая картинка характерна для конечных автоматов, но не для машин Тьюринга или RAM-машин. То есть для них конечно тоже можно составить подобный граф, но это будет странно и излишне. В то же время в своем описании Вы говорите, что Ваша машина делает переходы на произвольные адреса. Это уже особенность RAM-машин. Но при этом Вы говорите о машинах Тьюринга. Поэтому я и говорю, что у Вас какая-то мешанина из разных формальных моделей получается. При том, что не все они эквивалентны: машины Тьюринга и RAM-машины сильнее конечных автоматов.

Такая задача решается поиском в ширину. Но и в глубину тоже можно. То есть вы стоите на точке и смотрите на соседние точки. Если их цвет тот, что Вам нужен — добавляете их в очередь (если поиск идет в ширину) или в стек (если поиск в глубину). А дальше, пока стек/очередь не пусты, забираете оттуда первую вершину, «перемещаетесь» на нее и повторяете процесс. В конце все вершины, которые побывали в стеке/очереди — одного цвета с начальной и достижимы с нее. То есть как раз будет как бы «заливка» области.

Зачем? Это простая задача, которая решается за O(n³) детерминированной машиной Тьюринга, если у нас есть источник случайности, либо за O(n⁶), если такого источника не найдется (правда, вот тут я могу ошибаться с временной сложностью).

Нет, не нужна. Построение Эйлерового пути и цикла — это простые полиномиальные задачи. Они эффективно решаются и детерминированной машиной Тьюринга за полином. Таким образом использование НМТ для данной задачи — это все равно, что стрелять из пушки по воробьям.

Вот для Гамильтоновых циклов — вот тут да, уже потребуется НМТ. Но, к сожалению, похоже, что автор поста плохо понимает, что такое машина Тьюринга. Он путает машины Тьюринга с конечными автоматами и с RAM-машинами. Да и когда он сравнивает НМТ с нейронными сетями, или когда идет обсуждение модели распределенных вычислений и акторов в контексте машин Тьюринга — это только подчеркивает его непонимание работы формальных вычислительных моделей.

Я правильно Вас понимаю — Вы утверждаете, что придумали способ реализовать НМТ таким образом, что в ней не бывает экспоненциального количества параллельно выполняющихся «потоков»? Иначе говоря, Вы придумали способ, как опровергнуть гипотезу экспоненциального времени ETH?

А что Вы планируете делать с экспоненциальным взрывом количества параллельно выполняемых «потоков» в вашей машине? В этом же вся «беда» НМТ.

Да и в качестве демонстрации работы вашей модели НМТ как-то несолидно реализовывать калькулятор. Вычисления на калькуляторе — это все задачи из P-класса вычислительной сложности. То есть для этого дела даже не надо никакого недетерминизма. Уж лучше возьмите какую-то очень маленькую NP-полную задачу, типа, переменных на 10, и ее реализовывайте. В этом случае даже если потоки «расплодятся» на каком-то входном примере, то их будет не больше 2^10=1024. То есть вам потребуется не больше 1024 «процессоров» для обработки всех путей параллельно.

Если Вы меняете правило — Вы по факту меняете игру на другую. Это может быть всего лишь вариация оригинальной игры, но тем не менее с математической точки зрения это уже будет другая игра.

Игра о которой мы говорим — это гомоку на бесконечной доске с бесконечным количеством камушков (а иначе все игры тривиально конечны, и тут нечего доказывать).

Алексей же пытался ввести народ в обман, будто бы он знает какое-то интересное доказательство. Но он его не знает и знать не может, ведь само его утверждение

Кстати, сможешь доказать, что игра не может длиться бесконечно? Там очень интересное доказательство, разумеется с точки зрения математика.

просто неверно.