Ошибки в теории вычислимости

[Xaositect]

Андрей АK в сообщении #286846 писал(а):

Т.е. для непротиворечивой ,с точки зрения математики, функции.

Функции не бывают противоречивыми и непротиворечивыми.
Противоречивыми или непротиворечивыми быват теории, утверждения и т.п.
Поясните, что Вы имеете в виду.

[vek88]

Анекдот

Студент: Профессор, а зачем в фамилии Иванов буква "Ж"?
Профессор: Но там же нет буквы же.
Студент: Да, но если поставить?

Где-то я уже приводил этот анекдот, но не смог найти - проще повторить.

А теперь по теме. Здесь можно до бесконечности вставлять разные буквы и словосочетания (счетное количество) в фамилию Иванов.

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

Разумеется, здесь идет речь о математических определениях алгоритма, а не по принципу кому что нравится. Иначе мы придем к "женской" логике. Знаете такую? Напомню.

Колмогорова однажды спросили, а есть ли женская логика? Конечно есть, ответил он: если это мне нравится, то это истинно.

[AlexDem]

Хорошо, определение:
Алгоритм - это преобразование.

Возражения?
Теперь хотелось бы обоснования, что:
а) любое преобразование может быть разбито на "шаги"
б) любое такое разбиение конечно

[vek88]

AlexDem в сообщении #286867 писал(а):

Хорошо, определение:
Алгоритм - это преобразование.

Возражения?
Теперь хотелось бы обоснования, что:
а) любое преобразование может быть разбито на "шаги"
б) любое такое разбиение конечно

Пипец! Приехали!

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

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

И еще одно замечание - об адекватности участников дискуссии. Смоделируем реальную ситуацию на примере. Я кричу, что арифметика полна. А уважаемый Xaositect, прикрываясь Геделем, утверждает неполноту арифметики. Но мы оба адекватные люди и поэтому быстро найдем причину разногласий - я имел в виду нефинитную формализацию арифметики в полных К-системах, а Xaositect - традиционную финитную формализацию.

А когда, хотя бы один участник дискуссии не адекватен, выяснить причину разногласий практически невозможно. Так в случае с алгоритмами одна сторона использует традиционные определения алгоритма, а другая - какие ей нравятся! И если эта другая сторона не адекватна, то это уже не математическая дискуссия.

Я сказал,
vek88

[AlexDem]

vek88 в сообщении #286880 писал(а):

Пипец! Приехали!

vek88 в сообщении #286865 писал(а):

Кто-нибудь может аккуратно для чайников написать фамилию ИВАНОВ!?

Вы вроде просили определения? Я написал Вам это фамилиё, вроде близко к тому, что хотел автор . Что ж Вы теперь недовольны? По-моему, так очевидно, что топикстартер не имел в виду алгоритм в обычном его понимании, раз называл его "конечным алгоритмом".

-- Ср фев 10, 2010 11:12:14 --

Кстати, речь здесь идёт о физическом тезисе Чёрча. Именно он здесь поставлен под сомнение. Этот тезис недоказуем формально, поэтому Ваш наезд не обоснован.

[vek88]

Я просил какое-нибудь традиционное определение алгоритма, понятное чайнику и/или ежу. А если этот топикстартер дает определение в нетрадиционном смысле, то зачем он пишет об Ошибках в теории вычислимости.

[AlexDem]

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

[AD]

(Оффтоп)

AlexDem в сообщении #286887 писал(а):

Насчёт занятости определения - вопрос спорный, иначе и комплексные числа нельзя было числами называть по причине занятости термина.

Ну отрицательные числа достаточно долго числами не называли вроде ... Да и $i$ до сих пор называют мнимой ...

[vek88]

AD в сообщении #286888 писал(а):

(Оффтоп)

AlexDem в сообщении #286887 писал(а):

Насчёт занятости определения - вопрос спорный, иначе и комплексные числа нельзя было числами называть по причине занятости термина.

Ну отрицательные числа достаточно долго числами не называли вроде ... Да и $i$ до сих пор называют мнимой ...

(Оффтоп)

Термин комплексные числа отличен от термина числа. Это формально. А если по жизни, то выходя на публику с чем-то новым, обычно принято в преамбуле сообщать, что предлагается нечто иное. Например, формулировка изобретения начинается со слов

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

Здесь следовало бы написать что-то типа

Предлагается новая концепция алгоритма, отличающаяся от традиционной тем, что ... .

И, разумеется, следовало бы промолчать про ошибки в теории вычислимости.

А тезис Поста, Черча, Тьюринга здесь вообще ни причем (это ответ для AlexDem). Речь идет об элементарной аккуратности изложения.

О личном наезде - согласен - слишком эмоционально среагировал - убрал и/или смягчил, пока поезд не ушел.

-- Ср фев 10, 2010 12:13:17 --

Согласен, что и входить то в эту тему было незачем. Уважаемый Xaositect и без меня бы справился - правда жалко его стало сердешного. Надеюсь, он смог отдохнуть от участия в этой теме.

[Chifu]

Я предлагаю такую теорему - количество глюков бесконечно .

[Андрей АK]

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

Андрей АK в сообщении #286846 писал(а):

Т.е. для непротиворечивой ,с точки зрения математики, функции.

Функции не бывают противоречивыми и непротиворечивыми.
Противоречивыми или непротиворечивыми быват теории, утверждения и т.п.
Поясните, что Вы имеете в виду.

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

-- Ср фев 10, 2010 15:02:23 --

vek88 в сообщении #286880 писал(а):

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

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

Из неверной посылки - будут неверные следствия.

[Xaositect]

Андрей АK в сообщении #286911 писал(а):

Есть определение алгоритма, но ,как показал анализ, это определение некорректно, поскольку ведёт к ошибкам в рассуждении.

Не ведет.

Андрей АK в сообщении #286911 писал(а):

В теории же алгоритмов, почему-то задекларировали перечислимость всех алгоритмов, а потом эту "аксиому" начали использовать в доказательствах теорем.

Не задекларировали. Это доказывается.

-- Ср фев 10, 2010 14:45:20 --

Так.

В теории вычислений рассматриваются функции на множестве натуральных чисел и подмножества множества натуральных чисел. Одифредди в книге "Classical Recursion Theory" пишет: "Classical Recursion Theory is the study of real numbers or, equivalently, functions over the natural numbers."

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

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

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

-- Ср фев 10, 2010 14:49:59 --

Андрей АK в сообщении #286911 писал(а):

Тот же пример с действительными числами.

Действительных чисел несчетное число. Словами вы можете описать лишь счетное число действительных чисел. Т.о. не все действительные числа описуемы.

[Андрей АK]

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

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

С каких это пор, в математике исследуются объекты, которые можно "потрогать руками" , т.е. "вычислить"? (в наивном понимании)
Определение алгоритмов как счетного множества закрывает многие возможности:
Различные представления конечных алгоритмов бесконечными разбиениями по бесконечно-конечным базисам.
Невозможность отображения пространства алгоритмов на числовую ось и т.о. пути к решению многих задач (применения результатов многих числовых теорем к алгоритмам).
Ну и т.д.
Возможно доказательство P<>NP лежит как раз в этом направлении...

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

Что можно сделать с "невычислимым" алгоритмом - совершенно непонятно.

[Xaositect]

Андрей АK в сообщении #286930 писал(а):

С каких это пор, в математике исследуются объекты, которые можно "потрогать руками" , т.е. "вычислить"? (в наивном понимании)

Вот их и не рассматривают в математике.
Компьютер - это не машина Тьюринга, он слабее, у него конечная память.

Андрей АK в сообщении #286930 писал(а):

Возможно доказательство P<>NP лежит как раз в этом направлении...

Вряд ли, ибо в постановке проблемы речь идет о завершающихся алгоритмах. Сейчас больше склоняются к алгебраическим моделям, в которых можно сформулировать утверждения, эквивалентные $\mathbf{P}\neq \mathbf{NP}$ или более сильные, например, о сложности вычисления факториала. Хотя чем черт не шутит, вдруг, например, вложат решетку полиномиальной сводимости в решетку степеней неразрешимости...

Андрей АK в сообщении #286930 писал(а):

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

Есть, скажем, такая теорема

Цитата:

Proposition IV.1.19 (Shoenfield [1959]) For $n > 1$, $A$ is $\Delta^0_{n+1}$ if and only
if there is an $n + 1$-ary recursive function $g$ such that

$$c_A(x) = \lim_{s_1\to\infty}\dots\lim_{s_n\to\infty} g(x,s_1,... ,s_n).$$

Это выражение с пределами вполне можно считать одной из возможых формализаций "бесконечного алгоритма"

Андрей АK в сообщении #286930 писал(а):

Что можно сделать с "невычислимым" алгоритмом - совершенно непонятно.

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

И еще раз хочу отметить ошибку у Вас в терминологии. Не бывает невычислимых алгоритмов. Бывают вычислимые и невычислимые функции, в зависимости от того, существует ли алгоритм их вычисления.

[Андрей АK]

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

И еще раз хочу отметить ошибку у Вас в терминологии. Не бывает невычислимых алгоритмов. Бывают вычислимые и невычислимые функции, в зависимости от того, существует ли алгоритм их вычисления.

Ну тогда, скажите мне пожалуйста.
Функция, заданная бесконечным степенным рядом, вычислима или нет?