что следует из теоремы Геделя

[Xaositect]

Инт в сообщении #221776 писал(а):

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

Если Вы про другие модели вычислений (нормальные алгоритмы, $\lambda$-исчисление и др.), то все эти определения эквивалентны.
Если нет, то что Вы имеете в виду?

[Инт]

Xaositect в сообщении #221782 писал(а):

Инт в сообщении #221776 писал(а):

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

Если Вы про другие модели вычислений (нормальные алгоритмы, $\lambda$-исчисление и др.), то все эти определения эквивалентны.
Если нет, то что Вы имеете в виду?

То и имею ввиду, что однозначного определения понятия "алгоритм" в математике нет, не смотря на то, что какие-то частные определения эквивалентны. Т.е. математики не решаются объявить "эффективным" только обозначенные Вами. Причины этого - очевидны.

[Xaositect]

Тезис Тьюринга -- скорее утверждение из области философии математики, чем формальное.
В книгах же по теории алгоритмов и теории рекурсии тезис Тьюринга используется для того, чтобы сказать "все алгоритмически вычислимые функции рекурсивны" и далее работать не с нечетким понятием алгоритма, а с формально определенным понятием (частично-рекурсивной функции, машины Тьюринга, нормального алгоритма, $\lambda$-терма...) Для математики тезис по сути дает определение понятию "алгоритм".

[Инт]

Xaositect в сообщении #221802 писал(а):

Для математики тезис по сути дает определение понятию "алгоритм".

Можно дать любое другое, скажем, заведомо неадекватное, примитивное, но строгое определение алгоритма. И сказать, что это определение даётся по сути для математики.

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

[Xaositect]

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

Изучались и более широкие модели. Как пример:

Цитата:

The limit lemma. $A$ is $\Delta_2^0$-set if and only if its characteristic function is the limit of a recursive function $g$, i.e.

$c_A(x) = \lim\limits_{s\to\infty} g(x,s)$

$\Delta_2^0$-множества --- это множества, которые можно перечислить с использованием "оракула", который может решать проблему останова.
Т.е. способность переходить к пределу рекурсивной функции на бесконечности в некотором смысле эквивалентна способности решать проблему останова.
Есть также модели конструктивных функций на произвольной алгебре.
За подробностями отсылаю к двухтомнику P.Odifreddi "Classical recursion theory", откуда и взята цитата, приведенная выше. Там, кстати, есть и обзор по философии тезиса Тьюринга.

[Инт]

Xaositect в сообщении #221812 писал(а):

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

Вот и отлично, что изучались. Надо ещё поизучать. Во всяком случае, лучше иметь взвешенную позицию, а не ту позицию, что всё уже давно однозначно решено. Если же нет гарантии, то тезис - не доказан. Вопрос о "покрытии" спорный.

[Xaositect]

Инт в сообщении #221818 писал(а):

Вот и отлично, что изучались. Надо ещё поизучать. Во всяком случае, лучше иметь взвешенную позицию, а не ту позицию, что всё уже давно однозначно решено. Если же нет гарантии, то тезис - не доказан. Вопрос о "покрытии" спорный.

Да это все замечательно.
Только вот я думаю, это надо преподносить не как "Теорема Геделя неверна!" а как "При таком обобщении понятия эффективного вычисления аналог теоремы Геделя не имеет места".

[Инт]

Xaositect в сообщении #221851 писал(а):

Да это все замечательно.
Только вот я думаю, это надо преподносить не как "Теорема Геделя неверна!" а как "При таком обобщении понятия эффективного вычисления аналог теоремы Геделя не имеет места".

При таком обобщении понятия эффективности, какое сделал Гёдель и его последователи, "теорема Гёделя" так же не имеет смысла, так как не имеет смысла такого рода обобщение.

[epros]

Инт в сообщении #221555 писал(а):

Xaositect в сообщении #221064 писал(а):

Не бывает бесконечных алгоритмов.
Давайте формальное определение.

Чтобы ответить полно, надо по существу развить некоторую теорию. Поэтому, дам лишь самые общие определения. Конечный алгоритм есть всего лишь выражение некоторого математического опыта. Вычисление или вывод задаётся чётким правилом, разбивающим вывод на конечное число шагов. На каждом шаге вполне ясно, какие действия предпринять, чтобы сделать этот шаг. В этом и «эффективность». Но можно получать объект и «в эффективном процессе»: к примеру, вычисление числа $\pi$ можно получить в процессе, который интуитивно есть бесконечный алгоритм. У нас есть геометрическое основание существования числа $\pi$, есть основание к тому, чтобы ввести число $\pi$ так сказать синтетически. Затем, синтетическое число перерабатывается явно эффективным правилом в десятичную числовую последовательность. Чем не бесконечный алгоритм? Он и не может быть другим для бесконечных последовательностей. Ограничивать алгоритм переработкой заранее данных символов – необоснованный приём. Впрочем, даже символы, как непрерывные фигуры по существу – бесконечные объекты. Каждый шаг в конечном алгоритме это некоторое, вообще говоря, непрерывное действие. В том числе, и для вычислительных машин. Так что такой шаг можно разбить на другие и т.д. Т.е. каждый конечный алгоритм можно свести к бесконечному. К примеру, на каком-то шаге даётся задание подсчитать число $\pi$, а затем, в зависимости от результата, перейти к следующему шагу.

Это, что касается конечности алгоритмов.

«Эффективная функция» задаётся конкретными примерами (на сей раз можно последовать Гёделю). Т.е. предъявляется конкретная функция, и эффективность её оспаривать бессмысленно. Затем, композициями и некоторыми другими операциями получаем другие эффективные функции. Рекурсивные функции, конечно же – эффективные.

Для теории с фиксированным алфавитом строим эффективную функцию следующим алгоритмом: 1) упорядочи все символы алфавита теории; 2) лексикографически упорядочи слова цепочки символов, в частности слова и правильные выражения; 3) найди способ выделения эффективных функций теории (а других функций там нет), и пересчитай их, пользуясь лексикографическим порядком как функции $f_{n}$; 4) введи новый символ F, соответствующий новой функции (описываемой вне языка теории); 5) $F(n) = f_{n}(n) + 1$, если $f_{n}$ определена; $F$ - не определена, если $f_{n}$ - не определена. Почему $F$ не эффективная функция?

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

Определения алгоритмов существуют (другое дело, что нельзя утверждать, что они исчерпывающие). Пример - определение "нормального алгоритма", которое дал Марков.

Число $\pi$ определяется конечным алгоритмом, обрабатывающим конечные строки в конечном алфавите (это числа, например, в десятичной записи). Это значит, что с любой точностью его можно приблизить рациональным числом за конечное количество вычислительных операций.

[Инт]

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

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

Я и не стремился дать полные определения. Только обозначить. Поскольку,

Инт в сообщении #221555 писал(а):

Чтобы ответить полно, надо по существу развить некоторую теорию. Поэтому, дам лишь самые общие определения...

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

В частности, филосовский тезис "об эффективности", которого, как видно, придерживаетесь Вы, объявляется "математическим определением описывающим весь объём понятия алгоритм", и из него делается однозначный вывод и исключаются умышленно другие подходы. Ложь заключается не в тезисе, а в устранении других подходов без достаточного обоснования и не математическими методами. Логически же это означает лишь простое и умышленное не рассмотрение случаев при доказательстве. Набор же других гёделевых ляпов, нелепостей и ничем не обоснованных условностей ещё более очевиден.

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

[epros]

Инт в сообщении #222152 писал(а):

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

Это всё ничего не даёт: Как было непонятно, что это за "эффективная функция", так и осталось непонятно. Одни бессмысленные слова заменяют другие, только и всего.

Я вот выскажу Вам тезис Чёрча: "Всякая интуитивно вычислимая функция является рекурсивно вычислимой". Как я понимаю, первая - аналог Вашей "эффективно вычислимой функции". Вторая - фактически синоним понятия алгоритма. Получается, что никаких "эффективно" вычислимых функций, помимо записываемых алгоритмами, в природе не существует. Попробуйте опровергните.

Инт в сообщении #222152 писал(а):

К тому же, в обосновании тезиса Гёделя допускается прямая ложь, умышленная подмена понятий, которая не перестаёт быть ложью и подменой понятий, дам я определения или нет.

А мне почему-то кажется, что Ваша интерпретация первой теоремы Гёделя о неполноте - это "прямая ложь и умышленная подмена понятий".

Инт в сообщении #222152 писал(а):

Поскольку определения Маркова и др., упомянутые Вами, не являются исчерпывающими, то и однозначных выводов делать из них не имеете право. А Вы, как я думаю, делаете.

Выводы, которые я делаю, это моя проблема. Я осознаю их ограниченность в той мере, в которой ... осознаю. Определение Маркова "не исчерпывающе" в том смысле, что его "нормальный алгоритм" работает только с ограниченными видами объектов - со строками символов. Более общее понятие алгоритма предполагает возможность работы и с другими объектами. Но никто пока ещё не продемонстрировал более общего формального определения (в том смысле, что описание манипуляций с любыми объектами предположительно может быть сведено к манипуляциям над описывающими их строками символов).

[Инт]

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

А мне почему-то кажется, что Ваша интерпретация первой теоремы Гёделя о неполноте - это "прямая ложь и умышленная подмена понятий".

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

[epros]

Инт в сообщении #222194 писал(а):

Подмены понятий так же нет, так как именно понятие "классическая доказуемость" я отстаиваю, т.е. отстаиваю прямое понимание доказуемости, а не то ущербное, которое навязывают сторонники Гёделя.

"Классическое" понимание доказательства - это конечная последовательность высказываний, каждое из которых либо аксиома, либо получено из предыдущих с помощью правила вывода. Его и использовал Гёдель.

На самом деле, есть "живой пример" недоказуемого в арифметике Пеано истинного утверждения, и он здесь ранее обсуждался: это теорема Гудстейна. Она представляет собой утверждение о конечности всех "последовательностей Гудстейна". В арифметике Пеано (формализацию см. здесь) можно доказать конечность каждой из последовательностей Гудстейна (начинающейся с любого числа), но не существует общего доказательства для всех последовательностей.

[Инт]

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

есть "живой пример" недоказуемого в арифметике Пеано истинного утверждения, и он здесь ранее обсуждался: это теорема Гудстейна.

Я не утверждал, что не может быть или нет неразрешимых известными на сегодня средствами проблем. Так что по теореме Густейна не возражаю Вам. "Живой пример" не может оправдывать ошибку в выводе "теоремы", претендующей на весьма сильное обобщение. Насчёт использования Гёделем классической доказуемости Вы не правы. Указанное Вами относительно цепочки вывода - не единственное требование, которое должно предъявляться к доказуемости в тех условиях, в которых применено рассуждение Гёделя. Мне повторять аргументы не хочется. Так что кратко: если некоторое утверждение тривиально доказуемо по существу, но формально не доказуемо, то мы не можем приписывать теории полноценность, и делать из такой ущербной доказуемости далекоидущие выводы насчёт всех достаточно богатых теорий.

[epros]

Инт в сообщении #222341 писал(а):

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

Вы не поняли. Теорема Гудстейна - это не "неразрешимая известными на сегодня средствами проблема". Это - истинное высказывание (почему - см. выше). Но в арифметике Пеано она недоказуема. "Недоказуема" - это значит буквально: доказательства в рамках арифметики Пеано не существует.

Инт в сообщении #222341 писал(а):

Указанное Вами относительно цепочки вывода - не единственное требование, которое должно предъявляться к доказуемости в тех условиях, в которых применено рассуждение Гёделя.

В любых "условиях", у Гёделя или не у Гёделя, а доказуемость - это существование доказательства, т.е. той самой цепочки вывода. И ничего более.

Инт в сообщении #222341 писал(а):

если некоторое утверждение тривиально доказуемо по существу, но формально не доказуемо,

Нет понятия "доказуемость по существу". Вы это словосочетание придумали, и за ним не стоит никакой математики. Доказательство в формальной теории может быть только формальным.

Инт в сообщении #222341 писал(а):

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

Ущербная или нет, а другой не определено.