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

[apriv]

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

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

Что? За конечное число шагов она успеет поработать только с конечным подмножеством алфавита.

[epros]

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

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

Нет, не то же самое. В бесконечном алфавите нет ничего особенного. Например, можно рассматривать «индексированные символы»: $a_1, a_2, \dots$. Таких символов будет бесконечное множество, поскольку индексов - бесконечное множество. Но алгоритм, который принимает на вход строку и что-то в зависимости от этого делает за конечное количество шагов, за время своей работы будет иметь дело только с конечным подмножеством символов.

-- Сб авг 04, 2012 13:10:47 --

Да, apriv уже сказал.

[Munin]

Извините, что захватываю тему вопросами о вычислимости, но всё же:

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

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

Поясните, как это связано с вычислимостью или невычислимостью.

Пусть у нас машина Тьюринга построена так: в зависимости от первого считанного символа $R\in[0,1),$ записывает первый символ $W\in[0,1)$ так:
запись $R$ как $n$-ичной дроби интерпретируется как текст на естественном языке в $n$-буквенном алфавите;
если эта запись однозначно описывает число, вычислимое или невычислимое, из $[0,1),$ то записывается это число;
если эта запись не соответствует такому числу, записывается $0.$
Бесконечные дроби, скажем, тоже дают $0.$

Так нельзя?

[epros]

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

Пусть у нас машина Тьюринга построена так: в зависимости от первого считанного символа $R\in[0,1),$ записывает первый символ $W\in[0,1)$ так:
запись $R$ как $n$-ичной дроби интерпретируется как текст на естественном языке в $n$-буквенном алфавите;
если эта запись однозначно описывает число, вычислимое или невычислимое, из $[0,1),$ то записывается это число;
если эта запись не соответствует такому числу, записывается $0.$
Бесконечные дроби, скажем, тоже дают $0.$

Так нельзя?

Что-то я не понял. У нас уже есть какое-то число $R$ в $n$-ичной записи? Чем оно определено? И что мы с ним должны делать?

[Munin]

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

Я не очень понял, что вы обсуждали про busy beaver, но понял, что описание формулой и/или естественным текстом может однозначно задавать число, даже если оно невычислимо.

[epros]

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

за одно чтение и одну запись символа выдаёт нужное число

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

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

Я не очень понял, что вы обсуждали про busy beaver, но понял, что описание формулой и/или естественным текстом может однозначно задавать число, даже если оно невычислимо

Описание формулой некой достаточно сильной теории, которая претендует на то, что она определила предикат «вычислимости» (такова, в частности, ZFC), может претендовать на то, что оно определяет невычислимый объект. Например, ZFC претендует на то, что определила «функцию» busy beaver, коя невычислима, т.е. не может существовать проверяющий соответствующую формулу алгоритм.

Точка зрения конструктивного анализа другая: Раз соответствующий алгоритм не определён, то и функция не определена. В частности, нельзя конструктивно утверждать, что $\Sigma(5)$ существует (хотя ZFC именно это и утверждает). Насколько я знаю, на сегодняшний день известно около 40 машин Тьюринга с 5-ю состояниями - кандидатов в busy beaver. Т.е. пока не доказано, что они не останавливаются.

[Munin]

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

Может цифру?

Угу, цифру из алфавита $[0,1).$ Это уже достаточно устрашающе.

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

Потому что непонятно в каком смысле можно за один шаг выдавать действительное число.

Я спросил про обобщение машины Тьюринга на бесконечные алфавиты. Хочу понять, где вычислимость за конечность зацепляется. Один из вариантов - выполнение алгоритма за конечное число шагов - я уже уловил, теперь алфавитом интересуюсь.

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

[apriv]

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

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

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

[Munin]

Ну, вы первый, кто мне это уверенно сказал.

[epros]

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

Угу, цифру из алфавита $[0,1).$ Это уже достаточно устрашающе.
...
Я спросил про обобщение машины Тьюринга на бесконечные алфавиты.

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

Если Вы утверждаете, что алгоритм на очередном шаге выдаёт «действительное число», то Вы должны определить, что именно подразумеваете под этим объектом. Формулу ZFC, определяющую стандартное действительное число, причём - доказанно единственное? А как Вы убедитесь в том, что напечатанная формула - именно такова? А если у алгоритма, который будет это проверять, не будет точки останова?

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

При этом "определён алгоритм" или "определена машина Тьюринга" я понимаю в неконструктивном смысле

Алгоритм в неконструктивном смысле, по-моему, это оксюморон. Функция в смысле классического анализа - это одно, а алгоритм - другое.

[Munin]

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

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

Откуда я это знал? :-) Для меня "бесконечный" и значит "бесконечный", если бы надо было сказать "счётный", я бы так и сказал. И ожидал аналогично услышать. И я же с самого начала говорил про множество $2^{\mathbb{N}}$ - а это именно $[0,1).$

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

Собственно, логично, машина Тьюринга с алфавитом $[0,1)$ может просто вычислить любую функцию $[0,1)\to[0,1)$ за один шаг.

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

Если Вы утверждаете, что алгоритм на очередном шаге выдаёт «действительное число», то Вы должны определить, что именно подразумеваете под этим объектом.

Элемент алфавита, разумеется.

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

Алгоритм в неконструктивном смысле, по-моему, это оксюморон. Функция в смысле классического анализа - это одно, а алгоритм - другое.

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

[epros]

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

вы говорите, что машина Тьюринга со счётным алфавитом и конечным числом шагов порождает вычислимые функции ... ?

Во-первых, определение машины Тьюринга подразумевает двоичный алфавит и этого более чем достаточно. Хотя понятие алгоритма имеет множество эквивалентных машине Тьюринга определений: Машина Поста, нормальный алгоритм Маркова, $\lambda$-рекурсивная функция, $\mu$-рекурсивная функция… Так что в общем случае можно говорить о различных алфавитах - не только конечных, но и рекурсивных, хотя никакой «добавленной ценности» это не создаёт.

Во-вторых, требование «счётности» алфавита - недостаточно. Например, множество значений функции busy beaver - счётно, но не рекурсивно. Можно рассматривать элементы этого множества как «символы алфавита». Однако это приведёт к тому, что операция выбора символа из такого алфавита окажется алгоритмически неразрешимой.

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

Элемент алфавита, разумеется.

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

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

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

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

[Munin]

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

Во-первых, определение машины Тьюринга подразумевает двоичный алфавит

Впервые слышу.

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

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

Так с какого момента создаёт? С мощности континуума? С произвольного счётного алфавита?

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

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

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

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

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

Ого. А просто сослаться на множество нельзя?

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

Поэтому я спрашивал выше как Вы определяете действительное число - соответствующей формулой ZFC или ещё как-то.

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

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

В классическом анализе - да, определяется как «тра-ля-ля ... функция» - но отнюдь не всякая функция, а рекурсивная.

Это в машине Тьюринга функция перехода должна быть рекурсивной? Где это написано? Приведите ссылку на учебник.

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

Точнее, могут использоваться те же термины («символ», «множество», «алфавит», «операция» и т.п.), но трактоваться они могут как базовые (неопределяемые) понятия, а не как понятия классического анализа.

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

[epros]

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

Впервые слышу

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

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

Так с какого момента создаёт? С мощности континуума? С произвольного счётного алфавита?

Я сказал с какого: как только среди базовых операций алгоритма появляются нерекурсивные. Это называется «алгоритм с оракулом». Он может решать задачи более высоких уровней аналитической иерархии. В природе реализаций таких алгоритмов пока что не встречалось.

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

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

Чтобы что-то записать на ленту, нужно это что-то выбрать из множества того, что мы имеем право записывать.

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

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

Рациональный отрезок? Или, может быть, отрезок из конечного множества крошек грифеля?

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

Это в машине Тьюринга функция перехода должна быть рекурсивной? Где это написано? Приведите ссылку на учебник.

Погуглите «аналитическая иерархия».

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

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

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

[Munin]

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

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

Я понимаю, что конечный алфавит не даёт преимуществ. Просто конечность в определение входит, а двоичность - нет.

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

Я сказал с какого: как только среди базовых операций алгоритма появляются нерекурсивные.

Простите, вы вообще помните, что такое машина Тьюринга? Там только одна "базовая операция": переход из состояния $q_1$ в состояние $q_2,$ в зависимости от считанного символа, и одновременно с записью символа, а потом сдвигом. Она рекурсивная или нерекурсивная? Я, во всяком случае, от этого определения не отхожу. Такое впечатление, что вы термин "рекурсивный" используете в каком-то диком смысле.

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

Чтобы что-то записать на ленту, нужно это что-то выбрать из множества того, что мы имеем право записывать.

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

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

Рациональный отрезок? Или, может быть, отрезок из конечного множества крошек грифеля?

Вы не знаете, что такое отрезок? Или кривляетесь? Я надеялся у вас чему-то научиться, а не подыгрывать вашей клоунаде.

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

Погуглите «аналитическая иерархия».

Приведите.
Ссылку.
На учебник.

Вы не понимаете?

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

А Вы уверены, что классический анализ достаточно хорошо знаете?

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