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

[Munin]

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

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

А что такое "программа машины"? В смысле машины Тьюринга, разумеется.

[epros]

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

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

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

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

заявленный Вами подход состоит в том, что Вы базовые операции сразу же объявляете рекурсивными

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

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

счётный алфавит вычислительных возможностей не добавляет

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

[Someone]

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

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

На какой попадём, на такой и попадём. Для понимания того, что такое алгоритм, это не имеет значения.

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

А выше Вы говорили, что "несущественно" каким способом выполняется базовая операция.

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

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

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

Если мы все функции объявим базовыми операциями, то так и будет. Но кто же заставляет нас так поступать?

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

Конечно. Но я сначала определяю конкретную базовую операцию.

А я "сначала" что делаю? Напомню:

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

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

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

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

Э-э-э... Что значит - "конечной"? И зачем нам определять именно стандартное понятие рекурсивности?

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

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

Это непонятно. Возьмём, например, нормальные алгорифмы Маркова. Программа состоит из конечного числа подстановок. Каждая подстановка записывается конечным числом символов. Какая разница, сколь велик алфавит? Он должен содержать все символы, упомянутые в программе (кроме метасимволов, конечно), а что сверх этого, то на работу алгоритма не влияет.
С машиной Тьюринга сложнее, но можно договориться, что машина, встретив символ, не упомянутый в программе, останавливается. Или для каждого состояния конечного автомата добавить команду, общую для всех символов, "кроме перечисленных". Я не утверждаю, что эти варианты эквивалентны. Но первый вариант выглядит самым безобидным.
Я согласен, что область действия алгоритма формально расширяется. Но это расширение какое-то тривиальное. Расширяется ли, например, множество частично рекурсивных функций типа $\mathbb N\to\mathbb N$? Или каких-то других с заранее заданной областью действия?

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

А что такое "программа машины"? В смысле машины Тьюринга, разумеется.

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

[epros]

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

возможно определение рекурсивной функции (т.е. соответствующей стандартному определению рекурсивности), работающей с рекурсивным алфавитом

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

Это непонятно.

Чтобы не быть голословным, приведу пример. Вот есть определение нормального алгоритма Маркова. Как видите, алфавит предполагается конечным. К тому же алфавит, в котором записывается сам код алгоритма, содержит дополнительно два служебных символа. А мы сделаем вот что: определим "ненормальный алгоритм Маркова", расширив алфавит до счётного. Для этого мы определим алфавит как множество символов $a$, индексированных натуральными числами (индексы предполагаются в десятичной записи), т.е.: $\{a_0, a_1, a_2, \dots \}$. Символы $a_0$ и $a_1$ будем считать служебными - они могут использоваться только при записи кода алгоритма. Да, ещё будем считать символ $a_2$ за перевод строки - это чтобы код алгоритма можно было записать одной строкой. Строка, подаваемая на вход алгоритма, эти три символа содержать не может. Базовой операцией по-прежнему будем считать поиск первого вхождения подстроки в данной строке и замену её на другую подстроку.

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

Как видите, бесконечность алфавита сама по себе не создаёт никаких проблем для алгоритмической разрешимости, о чём я и писал ранее:

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

В бесконечном алфавите нет ничего особенного.

[Someone]

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

...

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

[epros]

Someone, извиняюсь, что не успеваю прочитать, поэтому отвечаю с задержкой.

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

Если мы все функции объявим базовыми операциями, то так и будет. Но кто же заставляет нас так поступать?

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

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

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

Э-э-э... Что значит - "конечной"?

Таблица значений - конечное множество. Пример - таблица значений логического И в булевой алгебре, коя состоит из четырёх клеток.

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

И зачем нам определять именно стандартное понятие рекурсивности?

Чтобы одинаково понимать о чём речь. Ибо в некотором смысле любая функция $\mathbb{R} \to \mathbb{R}$ может считаться "вычислимой", но это не тот смысл, о котором мы здесь говорим.

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

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

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

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

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

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

[Someone]

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

[epros]

(Оффтоп)

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

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

Ну, извиняюсь, если что не так. Вообще-то я стараюсь никому ничего не приписывать, помимо прямо сказанного.

[Xaositect]

Вы, кажется, спорите о чем-то странном.

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

[epros]

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

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

Вы сейчас про моё определение «ненормального алгоритма Маркова»? Тогда непонятно - зачем это доопределять, если это видно из определения алгоритма: если будет найдена подстрока, равная левой части оператора, то она будет заменена, а если не будет найдена, то алгоритм перейдет к следующему оператору. Наличие в алфавите символа, которого нет в коде, вообще никакой «нештатной ситуацией» не является.

Или Вы сейчас про МТ со счётным алфавитом? Так я не говорю, что такая МТ может разумным образом определять «вычислимость».

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

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

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

[Munin]

Xaositect
Машина может понимать все символы алфавита, но "не делать ничего нетривиального" в вашем смысле.
Например, пусть программа для МТ с алфавитом $[0,1)$ состоит из состояний $q_1$ (одно состояние) и $q_2\times[0,1)$ - отрезок состояний, причём состояние $q_1$ начальное, а все состояния $q_2$ конечные. И из следующих правил:
- в состоянии $q_1$ при чтении символа $a$ записать символ $1-e^{-a},$ остаться на месте, и перейти в состояние $q_2\times a.$
- в состоянии $q_2\times x$ ничего не делать - оно конечное.
Такая машина не останавливается (на первом шаге), и понимает все символы из алфавита. И заодно вычисляет функцию $[0,1)\to [0,1).$ Могла бы решать трансцендентное уравнение, скажем.

[Xaositect]

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

[epros]

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

И заодно вычисляет функцию $[0,1)\to [0,1).$

Угу. И могла бы вычислять вообще любую функцию. Достаточно в определении базовой операции записать что-то другое вместо $1-e^{-a}$.

[Munin]

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

Это у Вас бесконечная программа.

В каком смысле "бесконечная"? Я нигде не встречал требования, чтобы текст программы МТ требовалось записать последовательно на листочке. В этом смысле программа МТ - это другая сущность, чем программа на языке программирования.

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

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

Что значит "отдельно"? Программа - это просто функция. Разумеется, для тех примеров МТ, которые излагаются в учебных курсах, эту функцию просто описывают текстом, и получается "отдельное" описание. Но на саму функцию это не влияет. Кроме того, никто не мешает придумать МТ с конечным алфавитом, скажем, и с правилами перехода, которые указывают при считывании числа $a$ записать число $(a+1)\mod N.$

-- 08.08.2012 16:17:14 --

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

Угу. И могла бы вычислять вообще любую функцию.

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

[Xaositect]

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

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

Это у Вас бесконечная программа.

В каком смысле "бесконечная"? Я нигде не встречал требования, чтобы текст программы МТ требовалось записать последовательно на листочке. В этом смысле программа МТ - это другая сущность, чем программа на языке программирования.

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

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

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

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

Цитата:

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

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

Что значит "отдельно"? Программа - это просто функция. Разумеется, для тех примеров МТ, которые излагаются в учебных курсах, эту функцию просто описывают текстом, и получается "отдельное" описание. Но на саму функцию это не влияет. Кроме того, никто не мешает придумать МТ с конечным алфавитом, скажем, и с правилами перехода, которые указывают при считывании числа $a$ записать число $(a+1)\mod N.$

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