|
Homyachok
|
|
old hand
|
|
|
|
|
|
|
Рег.: 27.09.2004
|
|
Сообщений: 782
|
|
|
|
Рейтинг: -122
|
|
Re: определение понятия алгоритм
[re: Homyachok]
16.03.2007 22:27
|
|
|
Практическое применение бесконечности.
На практике бесконечность может использоваться для доказательства свойств алгоритмов (в том числе конечных). К примеру, есть некий алгоритм (в виде конечного автомата), обрабатывающий входные данные размером до 10^12 (вполне реально). Мы хотим узнать, правильно он это делает или нет. Может быть, что "чисто конечное" доказательство занимает объем что-то типа 2^(10^12) символов, а доказательство с использованием каких-нибудь "бесконечных" теорем в виде конечных частных случаев занимает 10^20 символов (что уже реально проверить).
P.S. Еще говорят, что ответить на вопрос P?=NP без привлечения "чисто бесконечной математики" скорее всего нельзя. Поговаривают даже, что это утверждение независимо с ZFC.
|
Нам Крыш! |
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
Re: определение понятия алгоритм
[re: Homyachok]
16.03.2007 22:39
|
|
|
DarkGray щас скажет, что некорректно формулировать задачу "для любых N, K ...", так как имеем бесконечный перебор.
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
Re: определение понятия алгоритм
[re: Homyachok]
16.03.2007 22:41
|
|
|
В ответ на:
Поговаривают даже, что это утверждение независимо с ZFC
А вот это жесть, но такое хрен вот так докажешь, надо строить еще что-то более общее, чем ZFC 
А вообще есть такие системы, кстати ?
|
|
DarkGray
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 31415
|
|
|
|
Рейтинг: 8953
|
|
Re: определение понятия алгоритм
[re: Homyachok]
16.03.2007 22:48
|
|
|
Quote:
Задачу можно сформулировать в терминах конечных последовательностей, но решить - нельзя.
ответ - элементарный.
для конечных последовательностей - утверждение
Quote:
Доказать, что при любых начальных K>=2 и N последовательность сойдется к 0
неверно.
контрпример
конечная последовательно длиной 30.
N=11, K=2
|
|
|
Homyachok
|
|
old hand
|
|
|
|
|
|
|
Рег.: 27.09.2004
|
|
Сообщений: 782
|
|
|
|
Рейтинг: -122
|
|
Re: определение понятия алгоритм
[re: FMX]
16.03.2007 22:51
|
|
|
Quote:
А вообще есть такие системы, кстати ?
Вообще, есть. Например, ZFC + непротиворечивость ZFC или ZFC + корректность ZFC относительно множества натуральных чисел. Еще иногда добавляют к ZFC существование очень больших кардиналов (типа сверхдох*я  ) или универсума ZFC. Правда чем шире аксиоматика, тем меньше верится в ее непротиворечивость. Знаю, есть учОные, активно с пеной у рта доказывающие противоречивость формальной арифметики Пеано, я уж не говорю о расширениях ZFC.
|
Нам Крыш! |
|
|
Homyachok
|
|
old hand
|
|
|
|
|
|
|
Рег.: 27.09.2004
|
|
Сообщений: 782
|
|
|
|
Рейтинг: -122
|
|
Re: определение понятия алгоритм
[re: DarkGray]
16.03.2007 22:53
|
|
|
Quote:
контрпример
конечная последовательно длиной 30. N=11, K=2
Дык она всегда конечная.
Но доказать это для любых N и K без привлечения "бесконечностей" не получится.
|
Нам Крыш! |
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
Re: определение понятия алгоритм
[re: Homyachok]
16.03.2007 22:55
|
|
|
Ну непротиворечивость это хрен с ней, но можно вполне доказывать сводимость к PRA подсистем (а значит, в частности. - конкретных теорем) в арифметике Пеано или в Z2.
|
|
|
Homyachok
|
|
old hand
|
|
|
|
|
|
|
Рег.: 27.09.2004
|
|
Сообщений: 782
|
|
|
|
Рейтинг: -122
|
|
Re: определение понятия алгоритм
[re: FMX]
16.03.2007 23:11
|
|
|
а может PRA тоже противоречива?
|
Нам Крыш! |
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
Re: определение понятия алгоритм
[re: Homyachok]
16.03.2007 23:29
|
|
|
гы-гы-гы
Гильберт все ж таки авторитетный товарищ, будем ему верить
|
|
|
DarkGray
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 31415
|
|
|
|
Рейтинг: 8953
|
|
Re: определение понятия алгоритм
[re: Homyachok]
16.03.2007 23:40
|
|
|
> Дык она всегда конечная.
ты не понял.
в определение задачи, опять же используется, что числовая последовательность бесконечная.
соответственно я утверждаю, что если брать числовую последовательность конечную (например, длиной 30), то утверждение задачи сразу становится неверной.
|
|
|
Homyachok
|
|
old hand
|
|
|
|
|
|
|
Рег.: 27.09.2004
|
|
Сообщений: 782
|
|
|
|
Рейтинг: -122
|
|
Re: определение понятия алгоритм
[re: DarkGray]
16.03.2007 23:57
|
|
|
Quote:
соответственно я утверждаю, что если брать числовую последовательность конечную (например, длиной 30), то утверждение задачи сразу становится неверной.
А какой смысл другую задачу рассматривать?
Задача была: есть бесконечная последовательность; доказать, что в ней есть 0.
Или в конечном виде: существует натуральное m такое, что если построить конечную последовательность длины m, то у нее будет на конце 0.
|
Нам Крыш! |
|
|
Hero
|
|
|
|
|
|
|
|
|
Рег.: 20.02.2004
|
|
Сообщений: 3172
|
|
|
|
Рейтинг: 0
|
|
Re: определение понятия алгоритм
[re: Homyachok]
17.03.2007 00:30
|
|
|
>Задача была: есть бесконечная последовательность
точно. теорема гудстейна - задача о бесконечных последовательностях, и то, что для ее доказательства не хватает обычной индукции, а нужна трансфинитная - расплата за бесконечность в условии.
|
Последняя иллюзия состоит в том, что можно обойтись без иллюзий |
|
|
DarkGray
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 31415
|
|
|
|
Рейтинг: 8953
|
|
Re: определение понятия алгоритм
[re: Homyachok]
17.03.2007 00:42
|
|
|
> А какой смысл другую задачу рассматривать?
ты о чем, вообще, хочешь поговорить?
утверждалось, что реальный мир конечен, соответственно на практических задачах удобнее работать с "конечностями", а не c бесконечностями.
далее приходишь ты, и говоришь, но ведь если мы возьмем задачу в которой в условиях присутствует бесконечная числовая прямая, то мы ее не сможем решить с помощью "конечной" математики...
внимание, вопрос: какое отношение твой пример имеет к моему утверждению?
могу спросить более медленно:
какое отношение имеет задача, которая в условии требует наличие бесконечной прямой, к моему утверждению, что на конечных задачах нужна, в первую очередь, "конечная" математика?
|
|
gadfather
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 05.11.2003
|
|
Сообщений: 47302
|
|
Из: пл. Гагарина
|
|
Рейтинг: 16961
|
|
Re: определение понятия алгоритм
[re: DarkGray]
17.03.2007 01:12
|
|
|
бля
ну сколько можно?
реальный мир, может, и конечен, но границу заранее не выставишь
например, реальная программа, работающая на реальном компьютере, занимающем лишь ничтожную долю всего вещества вселенной, полностью протестировать за время жизни этой вселенной нереально
потому что экспонента
а задача тестирования программ - вполне практична и актуальна
ты хуже контровского студента, тому всего три раза надо повторять
|
You can't always get what you want |
|
|
DarkGray
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 31415
|
|
|
|
Рейтинг: 8953
|
|
Re: определение понятия алгоритм
[re: gadfather]
17.03.2007 01:28
|
|
|
> например, реальная программа, работающая на реальном компьютере, занимающем лишь ничтожную долю всего вещества вселенной, полностью протестировать за время жизни этой вселенной нереально
а бесконечность где?
|
|
|
Homyachok
|
|
old hand
|
|
|
|
|
|
|
Рег.: 27.09.2004
|
|
Сообщений: 782
|
|
|
|
Рейтинг: -122
|
|
Re: определение понятия алгоритм
[re: DarkGray]
17.03.2007 01:35
|
|
|
Quote:
какое отношение имеет задача, которая в условии требует наличие бесконечной прямой, к моему утверждению, что на конечных задачах нужна, в первую очередь, "конечная" математика?
Короче, я наверно неправильно понял твою фразу
Quote:
и утверждаю, что все тоже самое дерево математики можно построить и на конечных последовательностях (а не только бесконечных)
Но польза от бесконечности все-таки есть: с помощью бесконечной математики бывает возможно существенно уменьшать размер доказательств свойств конечных объектов (типа полином вместо экспоненты где-нибудь) и, следовательно, возможно проще проверять свойства конечных объектов.
|
Нам Крыш! |
|
|
Homyachok
|
|
old hand
|
|
|
|
|
|
|
Рег.: 27.09.2004
|
|
Сообщений: 782
|
|
|
|
Рейтинг: -122
|
|
Re: определение понятия алгоритм
[re: Hero]
17.03.2007 01:39
|
|
|
Quote:
точно. теорема гудстейна - задача о бесконечных последовательностях, и то, что для ее доказательства не хватает обычной индукции, а нужна трансфинитная - расплата за бесконечность в условии.
НЕТ!
Эту задачу можно переформулировать в конечном виде (доказать, что для любых N, K существует m такое, что конечная последовательность из m членов, построенная по правилам, заканчивается нулем).
Кроме того, можно взять аналогичную задачу (тоже о якобы бесконечных последовательностях):
Дано натуральное N. За 1 шаг оно уменьшается на 1. Доказать, что рано или поздно появится 0.
Вот эта задача очень хорошо решается конечными методами.
|
Нам Крыш! |
|
|
Hero
|
|
|
|
|
|
|
|
|
Рег.: 20.02.2004
|
|
Сообщений: 3172
|
|
|
|
Рейтинг: 0
|
|
Re: определение понятия алгоритм
[re: Homyachok]
17.03.2007 02:03
|
|
|
Quote:
Эту задачу можно переформулировать в конечном виде (доказать, что для любых N, K существует m такое, что конечная последовательность из m членов, построенная по правилам, заканчивается нулем).
это не в конечном виде, это ты просто слово "бесконечный" в формулировке "спрятал".
в конечном виде было бы так: конечная последовательность из не более (подставить _число_ по вкусу) членов.
|
Последняя иллюзия состоит в том, что можно обойтись без иллюзий |
|
|
gadfather
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 05.11.2003
|
|
Сообщений: 47302
|
|
Из: пл. Гагарина
|
|
Рейтинг: 16961
|
|
Re: определение понятия алгоритм
[re: DarkGray]
17.03.2007 02:40
|
|
|
ну если за время жизи вселенной что-то нельзя сделать, то на практике получается бесконечность, так?
уже четвертый раз, контра отдыхает
|
You can't always get what you want |
|
|
Fj_
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 12.09.2004
|
|
Сообщений: 8795
|
|
|
|
Рейтинг: 3287
|
|
Re: определение понятия алгоритм
[re: Homyachok]
17.03.2007 03:12
|
|
|
Quote:
P.S. Еще говорят, что ответить на вопрос P?=NP без привлечения "чисто бесконечной математики" скорее всего нельзя. Поговаривают даже, что это утверждение независимо с ZFC.
Вот тут: http://www.scottaaronson.com/papers/npcomplete.pdf умный дядька Scott Aaronson рассуждает на тему того, что P!=NP является чем-то вроде физического закона. Типа, что если бы P было равно NP, то можно было бы делать разные штуки, которые, с точки зрения физики нашей вселенной, являются слегка невозможными.
С математической точки зрения, кстати, P=NP приводит к тому, что можно достаточно быстро получить ответ на вопрос "есть ли у данной теоремы доказательство короче N символов", а это как-то непривычно очень.
|
The data is the error (c)IIS FTP Server. |
|
Список
Плоский
Дерево
