2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11  След.
 
 Re: Возможности математики без математической индукции
Сообщение13.04.2012, 09:15 


06/07/11
192
epros в сообщении #559531 писал(а):
Универсальная машина тут ни при чём. Функция $\Sigma(n)$ определена не через универсальную машину, а через машины с изначально пустой лентой.

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

Зачем ставить изначально безнадежные задачи ? Нужно всего лишь доказать существование или предъявить явно универсальную машину с $n$ состояниями работающую на изначально пустой ленте.
epros в сообщении #559531 писал(а):
Lukin в сообщении #559428 писал(а):
Достаточно найти при каком минимальном $n$ Тьюринг-машина может быть универсальной.
Так вроде при $n =5$?

А черт его знает. Это отдельный вопрос, как доказать, что машина является универсальной ?
epros в сообщении #559531 писал(а):
Lukin в сообщении #559428 писал(а):
Если одного из значений нет - нет и функции
Очевидно. И что из этого следует ?

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение13.04.2012, 10:11 
Заслуженный участник
Аватара пользователя


28/09/06
10413
Lukin в сообщении #559533 писал(а):
Значит нужно показать, что среди машин с $n$ состояниями, работающими на изначально пустой ленте, существует хотя бы одна машина, являющаяся универсальной.
Зачем?

Lukin в сообщении #559533 писал(а):
Нужно всего лишь доказать существование или предъявить явно универсальную машину с $n$ состояниями работающую на изначально пустой ленте.
Вы уверены в правильности своего понимания того, что такое универсальная машина Тьюринга?

Lukin в сообщении #559533 писал(а):
Очевидно, из предположения о том, что "стол - это не стол", следует все что угодно.
Это Вы к чему?

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение13.04.2012, 11:26 


06/07/11
192
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)$ не функция. В противном случае мы имеем дело с объектом, который не тождественен самому себе "стол, который не стол", "функция, которая не функция".

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение13.04.2012, 13:10 
Заблокирован
Аватара пользователя


24/06/11

237
С планеты Земля
epros в сообщении #559531 писал(а):
LaTeXScience, с верующим человеком, разумеется, спорить практически бесполезно.

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

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

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

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение13.04.2012, 14:37 
Заслуженный участник
Аватара пользователя


28/09/06
10413
LaTeXScience в сообщении #559590 писал(а):
И не передергивайте, обсуждаем мы сейчас (я и Вы) вопрос ``можно ли создать теорию не пользуясь математической индукцией''.
Чтобы "создать" арифметику Робинсона, нужно всего лишь выписать семь её аксиом. И не надо мне говорить, что нужно писать процедуру распознавания формулы арифметики - ибо эта процедура уже есть в мозге, а то, что в процессе её "создания и записи в мозг" использовалась мат. индукция, - недоказуемо.

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение13.04.2012, 16:45 
Заблокирован
Аватара пользователя


24/06/11

237
С планеты Земля
epros в сообщении #559606 писал(а):
Чтобы "создать" арифметику Робинсона, нужно всего лишь выписать семь её аксиом.

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

Вам не кажется, что Вы игнорируете необходимость какого-то background'a?
epros в сообщении #559606 писал(а):
И не надо мне говорить, что нужно писать процедуру распознавания формулы арифметики - ибо эта процедура уже есть в мозге

У нашего дикаря ее нет.
epros в сообщении #559606 писал(а):
Что именно я не понял?

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение14.04.2012, 03:45 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Someone в сообщении #559256 писал(а):
Сама постановка вопроса о вере в аксиомы формальной теории выглядит идиотской.

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение14.04.2012, 08:08 
Заслуженный участник
Аватара пользователя


28/09/06
10413
LaTeXScience в сообщении #559652 писал(а):
Он доказал, что математическая индукция -- это не просто условное соглашение.
А что же? Абсолютная истина, высеченная Господом золотыми буквами на обратной стороне небесной сферы?

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение14.04.2012, 15:38 
Заслуженный участник
Аватара пользователя


28/09/06
10413
LaTeXScience в сообщении #559652 писал(а):
epros в сообщении #559606 писал(а):
Чтобы "создать" арифметику Робинсона, нужно всего лишь выписать семь её аксиом.

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

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

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение14.04.2012, 19:54 


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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение15.04.2012, 00:01 
Заблокирован
Аватара пользователя


24/06/11

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

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

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение15.04.2012, 08:46 
Заслуженный участник
Аватара пользователя


28/09/06
10413
LaTeXScience в сообщении #560128 писал(а):
Например, нам ему придется объяснить, что такое слово, а потом и что такое формула. А после этого он у нас спросит: ``а с чего вы ребята взяли, что каждая формула является словом, а может какая-то формула не будет словом?''

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

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

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение15.04.2012, 10:51 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
epros в сообщении #560173 писал(а):
Допустим, мне придётся объяснять что такое слово. Я скажу: Слово состоит из букв.
Что значит - "состоит из"?

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение15.04.2012, 11:34 
Заслуженный участник
Аватара пользователя


28/09/06
10413
Someone в сообщении #560212 писал(а):
Что значит - "состоит из"?
Да уж без упоминания множеств обойдусь, не сомневайтесь. Просто нужно стереть первое, что мы распознаем как букву, и всё. Повторив эту операцию несколько раз, убедимся, что всё стёрто. Вот это и значит, что оно «состоит из». Кстати, это я сейчас практически буквально повторяю описание работы «нормального алгоритма», распознающего слово в заданном алфавите.

 Профиль  
                  
 
 Re: Возможности математики без математической индукции
Сообщение15.04.2012, 12:18 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
epros в сообщении #560225 писал(а):
Да уж без упоминания множеств обойдусь, не сомневайтесь.
Причём тут множества?

epros в сообщении #560225 писал(а):
Просто нужно стереть первое, что мы распознаем как букву, и всё.
Что такое "первое"? И как его "стереть"?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 161 ]  На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: tolstopuz


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group