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
10414
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
10414
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
10414
LaTeXScience в сообщении #559652 писал(а):
Он доказал, что математическая индукция -- это не просто условное соглашение.
А что же? Абсолютная истина, высеченная Господом золотыми буквами на обратной стороне небесной сферы?

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

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


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

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


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

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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