Возможности математики без математической индукции

[Lukin]

epros в сообщении #559531 писал(а):

Универсальная машина тут ни при чём. Функция $\Sigma(n)$ определена не через универсальную машину, а через машины с изначально пустой лентой.

Значит нужно показать, что среди машин с $n$ состояниями, работающими на изначально пустой ленте, существует хотя бы одна машина, являющаяся универсальной.

epros в сообщении #559531 писал(а):

Lukin в сообщении #559428 писал(а):

Я не думаю, что в данном случае, дело в проблеме остановки.

Именно в ней, поскольку функция $\Sigma(n)$ определена так, что для нахождения её значения нужно проверить все соответствующие машины Тьюринга на остановку.

Зачем ставить изначально безнадежные задачи ? Нужно всего лишь доказать существование или предъявить явно универсальную машину с $n$ состояниями работающую на изначально пустой ленте.

epros в сообщении #559531 писал(а):

Lukin в сообщении #559428 писал(а):

Достаточно найти при каком минимальном $n$ Тьюринг-машина может быть универсальной.

Так вроде при $n =5$?

А черт его знает. Это отдельный вопрос, как доказать, что машина является универсальной ?

epros в сообщении #559531 писал(а):

Lukin в сообщении #559428 писал(а):

Если одного из значений нет - нет и функции

Очевидно. И что из этого следует ?

Очевидно, из предположения о том, что "стол - это не стол", следует все что угодно.

[epros]

Lukin в сообщении #559533 писал(а):

Значит нужно показать, что среди машин с $n$ состояниями, работающими на изначально пустой ленте, существует хотя бы одна машина, являющаяся универсальной.

Зачем?

Lukin в сообщении #559533 писал(а):

Нужно всего лишь доказать существование или предъявить явно универсальную машину с $n$ состояниями работающую на изначально пустой ленте.

Вы уверены в правильности своего понимания того, что такое универсальная машина Тьюринга?

Lukin в сообщении #559533 писал(а):

Очевидно, из предположения о том, что "стол - это не стол", следует все что угодно.

Это Вы к чему?

[Lukin]

epros в сообщении #559546 писал(а):

Lukin в сообщении #559533 писал(а):

Значит нужно показать, что среди машин с $n$ состояниями, работающими на изначально пустой ленте, существует хотя бы одна машина, являющаяся универсальной.

Зачем?

Чтобы сделать вывод о том, что не существует останавливающейся Тьюринг машины с $n$ состояниями, выписывающей самое большое конечное число единиц $\Sigma(n)$.

epros в сообщении #559546 писал(а):

Вы уверены в правильности своего понимания того, что такое универсальная машина Тьюринга?

Надеюсь, что так. В моем понимании, ничего не мешает машине с $n$ состояниями выписать на изначально пустую ленту собственную таблицу состояний и преступить к ее выполнению на изначально пустой ленте. На обычном высокоуровневом языке программирования это называется "вирусом".
Более того, я не вижу принципиальных ограничений на существование машины с $n$ состояниями, которая выписывает на изначально пустую ленту таблицу машины с $n+1$ состояниями (и ее начальные данные), которая способна выписать на пустую ленту таблицу и начальные данные машины с $n+2$ состояниями (и ее начальные данные), и так далее. Выписав первую таблицу (и начальные данные) машина преступает к ее исполнению, дальнейшее происходит само собой.

epros в сообщении #559546 писал(а):

Lukin в сообщении #559533 писал(а):

Очевидно, из предположения о том, что "стол - это не стол", следует все что угодно.

Это Вы к чему?

?
Вы писали:

epros в сообщении #559309 писал(а):

Я склонен интерпретировать такую ситуацию как принципиальное отсутствие ответа на вопрос об остановке, а значит, как отсутствие значения функции $\Sigma(n)$ для соответствующего аргумента.

Функция - это двухместное отношение с ограничением $\forall a ((a,b) \in f, (a,c) \in f) \rightarrow b=c$. Если одного из значений нет - нет и функции, если $b \neq c$, то функции тоже нет. Из Вашего утверждения я делаю вывод, что $\Sigma (n)$ не функция. В противном случае мы имеем дело с объектом, который не тождественен самому себе "стол, который не стол", "функция, которая не функция".

[LaTeXScience]

epros в сообщении #559531 писал(а):

LaTeXScience, с верующим человеком, разумеется, спорить практически бесполезно.

Я уже давно сказал, что не верю.

epros в сообщении #559531 писал(а):

Факт заключается в том, что арифметика Робинсона (т.е. математическая теория без мат. индукции) существует.

Она существует, в частности, благодаря использованию матиндукции ее создателем.

epros в сообщении #559531 писал(а):

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

А я Вам говорю (уже второй раз, но Вы не замечаете), что Вы ничего не сможете иметь. И не передергивайте, обсуждаем мы сейчас (я и Вы) вопрос ``можно ли создать теорию не пользуясь математической индукцией''. А с тем, что можно создать теории без матиндукции, я (уже третий раз повторяю) не спорил и не спорю.

epros в сообщении #559531 писал(а):

Те философические соображения из Пуанкаре, которые вы привели, разумеется, интересны, но они не совсем о том.

Да Вы просто в очередной раз ничего не поняли.

[epros]

LaTeXScience в сообщении #559590 писал(а):

И не передергивайте, обсуждаем мы сейчас (я и Вы) вопрос ``можно ли создать теорию не пользуясь математической индукцией''.

Чтобы "создать" арифметику Робинсона, нужно всего лишь выписать семь её аксиом. И не надо мне говорить, что нужно писать процедуру распознавания формулы арифметики - ибо эта процедура уже есть в мозге, а то, что в процессе её "создания и записи в мозг" использовалась мат. индукция, - недоказуемо.

LaTeXScience в сообщении #559590 писал(а):

Да Вы просто в очередной раз ничего не поняли.

Что именно я не понял? Мне кажется, что это Вы не поняли кое-что из того, что я ранее говорил: Что мат. индукция - это всего лишь один из возможных способов обобщения утверждений про натуральные числа. Т.е. есть такие формулы арифметики $\varphi(n)$, которые при подстановке любого конкретного числа $n$ доказуемы, но при этом обобщающая формула $\forall n ~ \varphi(n)$ - недоказуема, и никакая индукция не может помочь.

[LaTeXScience]

epros в сообщении #559606 писал(а):

Чтобы "создать" арифметику Робинсона, нужно всего лишь выписать семь её аксиом.

Давайте возьмем дикаря из какого-нибудь африканского племени и передадим ему листик с выписанными аксиомами. По Вашему он ``создал'' теорию. Хотя он ни фига не понимает, что эти каракули означают.

Вам не кажется, что Вы игнорируете необходимость какого-то background'a?

epros в сообщении #559606 писал(а):

И не надо мне говорить, что нужно писать процедуру распознавания формулы арифметики - ибо эта процедура уже есть в мозге

У нашего дикаря ее нет.

epros в сообщении #559606 писал(а):

Что именно я не понял?

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

[Профессор Снэйп]

Someone в сообщении #559256 писал(а):

Сама постановка вопроса о вере в аксиомы формальной теории выглядит идиотской.

Ну да, математика - одна большая импликация. Математика не устанавливает истину, она всего лишь утверждает, что если верно что-то, то верно и другое...

[epros]

LaTeXScience в сообщении #559652 писал(а):

Он доказал, что математическая индукция -- это не просто условное соглашение.

А что же? Абсолютная истина, высеченная Господом золотыми буквами на обратной стороне небесной сферы?

Профессор Снэйп в сообщении #559800 писал(а):

Ну да, математика - одна большая импликация.

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

[epros]

LaTeXScience в сообщении #559652 писал(а):

epros в сообщении #559606 писал(а):

Чтобы "создать" арифметику Робинсона, нужно всего лишь выписать семь её аксиом.

Давайте возьмем дикаря из какого-нибудь африканского племени и передадим ему листик с выписанными аксиомами. По Вашему он ``создал'' теорию. Хотя он ни фига не понимает, что эти каракули означают.

Вам не кажется, что Вы игнорируете необходимость какого-то background'a?

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

Я утверждаю, что без мат. индукции можно обойтись. Она нужна только для обобщающих выводов типа: «Любая формула может быть распознана». А вот этого как раз нам и не нужно: Мы можем для любой конкретной формулы доказать, что она может быть распознана, применив N раз правило modus ponens.

[Doil-byle]

Я вот уже писал это на форуме (здесь, например). Напишу ещё раз, что аксиома индукции эквивалентна утверждению о том, что в любом непустом мн-ве натуральных чисел $N$ есть такое натуральное число $a$, которое не следует ни за каким другим натуральным числом из мн-ва $N$. Ясно, что такое утверждение для натуральных чисел будет выполняться в любой системе аксиом, которую мы выберем, потому что иначе мы получим что-то непохожее на мн-во натуральных чисел, а это мн-во нам нужно. Так что же переживать из-за аксиомы индукции? Не нравится, - уберите её и замените данным выше эквивалентным утверждением.

[LaTeXScience]

epros в сообщении #559941 писал(а):

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

Например, нам ему придется объяснить, что такое слово, а потом и что такое формула. А после этого он у нас спросит: ``а с чего вы ребята взяли, что каждая формула является словом, а может какая-то формула не будет словом?''

Мне дальше продолжать или понятно?

[epros]

LaTeXScience в сообщении #560128 писал(а):

Например, нам ему придется объяснить, что такое слово, а потом и что такое формула. А после этого он у нас спросит: ``а с чего вы ребята взяли, что каждая формула является словом, а может какая-то формула не будет словом?''

Мне дальше продолжать или понятно?

Нет, непонятно. Причём тут мат. индукция? Допустим, мне придётся объяснять что такое слово. Я скажу: Слово состоит из букв. Проверь, $0 = 1$ - это слово? Он начнёт проверять: $0$ - буква, $=$ - буква, $1$ - буква. Всё, состоит из букв, значит слово. Где использование индукции? Аналогично с проверкой формул, только чуть посложнее.

Ещё раз повторю: Индукция нужна для ОБОБЩАЮЩИХ выводов типа: «Любая формула является словом». Зачем при распознавании слова (или формулы) $0 = 1$ нам нужны обобщающие выводы?

[Someone]

epros в сообщении #560173 писал(а):

Допустим, мне придётся объяснять что такое слово. Я скажу: Слово состоит из букв.

Что значит - "состоит из"?

[epros]

Someone в сообщении #560212 писал(а):

Что значит - "состоит из"?

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

[Someone]

epros в сообщении #560225 писал(а):

Да уж без упоминания множеств обойдусь, не сомневайтесь.

Причём тут множества?

epros в сообщении #560225 писал(а):

Просто нужно стереть первое, что мы распознаем как букву, и всё.

Что такое "первое"? И как его "стереть"?