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

[Инт]

Немного порассуждаю. Если фиксирован язык теории, то фиксировано множество «эффективных функций», которые можно построить в теории. Используя перечисление символов языка, всегда явно можно предъявить функцию, определение которой находится вне языка теории, находящуюся вне «множества эффективных функций теории», но которая эффективна по существу. Отсюда, можно доказать, что явных эффективных методов арифметики, не привязанных к языку, в частности, методов доказательств, либо несчётное множество, либо множество настолько большое, что оно оказывается «неперечислимым». Можно предположить поэтому, что каждый эффективный метод достижим, вполне познаваем, но все вместе эффективные методы, доказательства арифметики не могут быть описаны одной эффективной функцией. Символы теории могут порождаться в алгоритмах, и поэтому, не могут быть упорядочены тем простым способом, каким их упорядочил Гёдель. Соответственно, в предполагаемой полной теории, невозможно построить функцию, перечисляющую доказательства через упорядочение символов. Гёдель лишний раз подтвердил отсутствие функций, перечисляющих все реальные доказательства, не более того, и никак не исключил, что каждое такое доказательство будет вполне достижимо в теории. Это подобно тому, как не перечислимы алгоритмы, но каждый из них достижим в теории, т.е может быть найден.

Впрочем, вопрос, что называется, вечный. В арифметике всегда что-то не известно, и незнание всегда может быть предметом спекуляций для формалистов. Однако, если даже гёделев тезис гипотетически истинен, то он не доказан. В итоге, «Теорема Гёделя» не является даже правдоподобной гипотезой, не говоря уже о том, чтобы быть теоремой. Причина, по которой подобные факты – по существу обмана – преподносятся как математические достижения, находится вне математики.

[epros]

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

Символы теории могут порождаться в алгоритмах

Что это за новое понятие об алгоритмах, которые порождают ... символы?

[Инт]

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

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

Символы теории могут порождаться в алгоритмах

Что это за новое понятие об алгоритмах, которые порождают ... символы?

Пересчитаем все символы фиксированной теории. На этой основе, пересчитаем, перечислим все эффективные функции, порождённые в теории. Определим эффективную функцию вне указанных алгоритмов, не равную ни какой эффективной функции теории. Добавим для новой функции символ.

[Xaositect]

Что такое "эффективная функция"?

[Инт]

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

Что такое "эффективная функция"?

Конечный или бесконечный алгоритм. Понятие чётко не определено, но достаточно ясно осознаваемо.

[Xaositect]

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

Конечный или бесконечный алгоритм. Понятие чётко не определено, но достаточно ясно осознаваемо.

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

[Инт]

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

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

Возможно и дам определения. Но пока лень. Лучше я в общем пофилосовствую.

[epros]

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

Лучше я в общем пофилосовствую.

Это разговор ни о чём. По моим понятиям, алгоритм определяется кодом в заданном алфавите и работает со словами тоже в заданном алфавите. Что это такое за "эффективная функция" я не понимаю.

[Инт]

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

По моим понятиям, алгоритм определяется кодом в заданном алфавите и работает со словами тоже в заданном алфавите. Что это такое за "эффективная функция" я не понимаю.

Ладно, постараюсь ответить более развёрнуто.

[Инт]

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$ не эффективная функция?

[Xaositect]

Стоп.
Ваша функция $F$ эффективна может быть описана в теории, она совпадает с одной из тех функций $f_n$, для которых $f_n(n)$ не определено. И теорема Геделя тут совершенно не при чем.

Давайте пока оставим бесконечные алгоритмы и будем довольствоваться конечными (строгого определения бесконечного Вы так и не дали).
1. Любой алгоритм может быть представлен в виде программы для некоторой формализованной модели вычислений, например, машины Тьюринга.
2. Существует алгоритм $L$, перечисляющий все программы для машины Тьюринга (т.е получив на вход число $n$ выдает программу для машины $M_n$. Машина $M_n$ вычисляет функцию $f_n$. $f_n$ - это все рекурсивные функции).
3. Существует универсальный алгоритм $U$, который по программе и входному слову возвращает результат действия машины с этой программой с этим словом на входе.
4. Существует алгоритм $S$, прибавляющий к числу единицу.
5. Тогда алгоритм $S(U(L(n),n))$ вычисляет функцию $F$: $F(n) = f_n(n)+1$, если $f_n(n)$ определено, и не определено, если $f_n(n)$ не определено.
6. Значит, $F$ - рекурсивная функция, $F \equiv f_r$. Если $f_r(r)$ определено, то $f_r(r) = f_r(r)+1$, чего быть не может. Если же $f_r(r)$ не определено, то противоречия нет.

[Инт]

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

Стоп.
Ваша функция $F$ эффективна может быть описана в теории, она совпадает с одной из тех функций $f_n$, для которых $f_n(n)$ не определено. И теорема Геделя тут совершенно не при чем.

Ну теорема Гёделя в каком-то смыле, при обсуждении, что является алгоритмом, действительно не причём. Что же касается Вашего возражения (в приведённых предложениях), согласен, что сделал ляп. $F$ должна быть равна $1$, для тех $n$, где будет неопределённость. Это, чтобы не совпадать с соответствующими функциями.

-- Пт июн 12, 2009 15:29:58 --

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

Давайте пока оставим бесконечные алгоритмы и будем довольствоваться конечными (строгого определения бесконечного Вы так и не дали).

Ну строгого определения конечного алгоритма никто не дал.
Что касается остальной части вашего ответа, то я должен её медленно почитать.

-- Пт июн 12, 2009 15:34:08 --

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

[Xaositect]

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

Что же касается Вашего возражения (в приведённых предложениях), согласен, что сделал ляп. $F$ должна быть равна $1$, для тех $n$, где будет неопределённость. Это, чтобы не совпадать с соответствующими функциями.

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

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

Ну строгого определения конечного алгоритма никто не дал.

Формальное определение алгоритма дается тезисом Тьюринга ("Любой алгоритм может быть представлен в форме программы для машины Тьюринга")

[Инт]

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

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

Я подумаю над этим Ваши тезисом. Думаю, что отвечу не сразу.

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

Формальное определение алгоритма дается тезисом Тьюринга ("Любой алгоритм может быть представлен в форме программы для машины Тьюринга")

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

-- Пт июн 12, 2009 16:12:27 --

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

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

Тогда это не эффективные функции. Если не знаем закончится ли вычисление или нет, то нет основания считать, что такой "алгоритм" эффективный.

[Инт]

Ещё раз про

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

Формальное определение алгоритма дается тезисом Тьюринга ("Любой алгоритм может быть представлен в форме программы для машины Тьюринга")

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