Вычисления с бесконечным алфавитом

[epros]

(Оффтоп)

Munin в сообщении #604117 писал(а):

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

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

Очень будет жаль, если Вы и это расцениваете как "порчу нервов и оскорбления".

[Munin]

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

Someone в сообщении #603931 писал(а):

Да, конечно, предполагалось стандартное ограничение: программа машины содержит лишь конечное число символов.

Да, я тоже споткнулся на этом заявлении, но не стал комментировать.

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

Программа - это не функция. Программа - это слово в некотором алфавите. Функция возникает только в описании работы машины.

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

Если уж говорить о выражении программы каким-то текстом, то выше я выразил программу текстом на естественном языке, и затратил на это конечное число символов.

-- 08.08.2012 17:20:59 --

(Оффтоп)

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

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

Но доказать не сподобились.

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

[epros]

Someone в сообщении #603929 писал(а):

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

Приведу пример:
1) Область действия "алгоритма": натуральные числа.
2) Базовые операции: Любые функции $\mathbb{N} \to \mathbb{N}$, определимые в ZFC.
3) Язык для записи алгоритмов: Каждый "оператор" должен описываться формулой ZFC, определяющей функцию $\mathbb{N} \to \mathbb{N}$. "Программа" (код алгоритма) состоит из конечной последовательности "операторов", результат выполнения предыдущего "оператора" подаётся на вход следующего. Выполнение последнего оператора означает остановку алгоритма.

Вот это указанное Вами условие:

Someone в сообщении #603931 писал(а):

конечно, предполагалось стандартное ограничение: программа машины содержит лишь конечное число символов

очевидным образом выполнено для любой "программы".

В каком смысле этот "алгоритм" можно считать реализующим "вычислимую функцию"? Например, он без труда реализует функцию busy beaver, которая доказанно невычислима.

Надеюсь, я сейчас ничего Вам не "приписал"? Я мог что-то не понять из сказанного Вами, ну этого уж никак исключить невозможно...

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

[Xaositect]

Munin в сообщении #604148 писал(а):

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

Математически, есть такое понятие, как "модель вычислений". Задать модель вычислений - значит задать множество программ и правила, по которым эти программы реализуют функции или определяют множества.

Я просмотрел несколько учебников, где упоминается машина Тьюринга. В некоторых говорится, что программа - это набор правил определенного вида, в некоторых - что это функция. У самого Тьюринга это таблица. Для случая конечного алфавита эти определения эквивалентны. Для случая же бесконечного алфавита их можно расширять различным образом и прежде, чем об этом говорить, надо определение фиксировать. Мне, например, кажется, что Someone имеет в виду не такую же модель машины с бесконечным алфавитом, как Вы.

[Munin]

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

Мне, например, кажется, что Someone имеет в виду не такую же модель машины с бесконечным алфавитом, как Вы.

Да, мне тоже так кажется, но я в его разговор не лезу. epros пожелал продолжать с ним, а не со мной - и ладно.

[Toucan]

Отделено от темы «Достоверное событие, невозможное событие»

[epros]

Munin в сообщении #604159 писал(а):

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

Мне, например, кажется, что Someone имеет в виду не такую же модель машины с бесконечным алфавитом, как Вы.

Да, мне тоже так кажется, но я в его разговор не лезу. epros пожелал продолжать с ним, а не со мной - и ладно.

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

[Munin]

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

1) Определить "действительные числа" так, чтобы они составляли рекурсивное множество.

У меня сложилось впечатление, что вы считаете это невозможным - даже натуральные числа у вас не вписывались.

Впрочем, если фокус состоит в отказе от ZFC, то наверное, не интересно.

[epros]

Munin в сообщении #604477 писал(а):

У меня сложилось впечатление, что вы считаете это невозможным - даже натуральные числа у вас не вписывались.

Почему же, впишутся, если в качестве допустимых базовых операций закладывать не любые функции $\mathbb{N} \to \mathbb{N}$, а только заведомо рекурсивные.

Munin в сообщении #604477 писал(а):

Впрочем, если фокус состоит в отказе от ZFC, то наверное, не интересно.

Вы так любите ZFC?

Фокус заключается в том, чтобы использовать не "стандартное $\mathbb{R}$", определяемое ZFC, а другое определение "множества действительных чисел": как real closed field, о котором я ранее говорил. Не знаю уж, "отказ" ли это от ZFC или нет...

[Munin]

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

Вы так любите ZFC?

Разумеется, а кто её не любит?

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

[epros]

Munin в сообщении #604608 писал(а):

Вы всё пляшете вокруг понятий "рекурсивности", которые считаете уже введёнными

А как по-Вашему вводятся теоретические понятия? Аксиомами. Это не значит, что они "считаются уже введёнными". Например, как определяется сложение в арифметике? Рекурсивно двумя аксиомами:
$x+0=x$ и
$x+(y+1)=(x+y)+1$

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

1) Любая функция, отображающая конечное множество в конечное множество, рекурсивна.
2) Любая программа, состоящая из конечного количества любых операторов, реализующих рекурсивные функции, реализует рекурсивную функцию.

Здесь следует отметить ещё раз (ибо раньше это говорилось), что:
- Обе части формулировки существенны, т.е. (2) без (1) не приводит ни к какому содержательному понятию "алгоритма". Точно так же, как без $x+0=x$ мы не получим никакого содержательного понятия сложения в арифметике.
- Из этого определения никоим образом не следует конечность алфавита, к которому применимы произвольные рекурсивные функции. (Someone ранее именовал его "областью определения" алгоритма).
- Равно как из него никоим образом не следует и конечность алфавита, в котором должны записываться коды программ. Объединение двух последних алфавитов я предлагаю именовать "универсом". Т.е. универс - это множество символов, которыми могут именоваться рекурсивные функции (включая базовые операторы), а также которые могут составлять их области определения.

Однако, посмотрев конструктивным взглядом на это определение, я вижу его недостаточность. Об этом свидетельствует пример Someone, приведённый им в сообщении #604038, где он пытался ограничить класс базовых операций машины Тьюринга функциями с конечной областью определения. Под аксиому (1) подходит? Да. Но если алфавит, на конечных подмножествах которого определены базовые операции МТ, не является рекурсивным множеством, то базовые операции могут получиться алгоритмически неразрешимыми!

Поясняю на примере (если будут вопросы, то потом уточню): Возьмём в качестве алфавита множество действительных чисел (в стандартном смысле: как множества всех подмножеств стандартных натуральных чисел). Для определённости считаем, что если на вход любой базовой операции попадает символ, не входящий в её область определения, то выходом является $0$. Рассмотрим базовую операцию $f$, областью определения которой является множество из одного элемента: $\{0\}$. Таблица значений функции состоит из одного элемента: $f(0) = 1$. Известно, что равенство действительных чисел - алгоритмически неразрешимо. Мало того, существуют примеры определений таких $x$, для которых истинность утверждения $x=0$ неизвестна (и не очевидно, что когда-либо станет известной). Это означает, что базовая операция $f$ над данным алфавитом - нерекурсивна. Т.е. принимая аксиому (1) по отношению к ней, мы поступаем неадекватно.

Как же быть? А очень просто. Надо всего лишь не забыть принять аксиому номер ноль:
0) Универс является рекурсивным множеством.

Как свидетельствует вышеприведённый пример, эта аксиома - тоже существенна для содержательного определения алгоритма (рекурсивной функции).

[Munin]

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

А как по-Вашему вводятся теоретические понятия?

Я полагаю, что они вводятся в каком-то порядке. Например, сначала векторы, потом тензоры. Сначала планиметрический угол, потом стереометрические: двугранный, телесный. Сначала группа, потом подгруппа. И так далее.

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

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

Дальше, я считал, что сначала вводится понятие вычислений, а потом - вычислимости, в том числе и рекурсивной вычислимости.

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

[epros]

Munin в сообщении #604714 писал(а):

я считал, что сначала вводится понятие вычислений, а потом - вычислимости, в том числе и рекурсивной вычислимости.

Понятия вычислений, вычислимости и рекурсивности - это всё синонимы. Разумеется, понятия "вводятся в каком-то порядке", но не в том, как Вы сейчас описали: Сначала вводится понятие о том, что конечная функция - вычислима (аксиома 1), а потом отсюда выводится (используя аксиому 2), что существуют и другие вычислимые функции.

Munin в сообщении #604714 писал(а):

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

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

[Munin]

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

Понятия вычислений, вычислимости и рекурсивности - это всё синонимы.

И чё, спрашивается, люди морочатся, ведь всё на свете синонимы...

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

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

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

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

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

Про это я в курсе. И лечится это легко: явным указанием стандартной модели, и оговорением, что все остальные нестандартные.

[epros]

Munin в сообщении #604751 писал(а):

И чё, спрашивается, люди морочатся, ведь всё на свете синонимы...

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

Munin в сообщении #604751 писал(а):

К сожалению, вы на настойчивые просьбы так и не привели ни одного учебника, который бы ваш подход демонстрировал.

Дык Боже ж мой, какие проблемы? Могу потратить (поверьте, зря) время и указать учебники и даже какие-то конкретные места из них. А можете и сами по ключевым словам "теория вычислимости" или "computability theory" кучу всего найти на колхозе или в других местах. Давайте лучше, чем читать ВСЁ подряд, подойдём поконструктивнее: если не согласны с чем-то конкретным из сказанного, то приводите возражение, а?

(Оффтоп)

Дело-то в том, что это никакой вовсе не "мой подход", а вполне себе общепринятый.

Munin в сообщении #604751 писал(а):

Про это я в курсе. И лечится это легко: явным указанием стандартной модели, и оговорением, что все остальные нестандартные.

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