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

[epros]

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

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

Someone, хочу теперь Вас призвать рассмотреть понятие «аналитической иерархии» - литературы на сей счёт полно. Если хотя бы некоторые базовые операции являются оракулами, т.е. нерекурсивными функциями, то такой «алгоритм» выходит за рамки стандартного понятия алгоритма, т.е. сам не является рекурсивной функцией.

(Оффтоп)

Это я к тому, что в природе до сих пор не встречались такие исполнители, которые «умеют выполнять» роль оракулов. Но вообразить их нам ничто не мешает.

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

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

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

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

Что может означать рекурсивность базовых операций и алфавита, совершенно непонятно.

Рекурсивность алфавита означает, что оное множество символов является рекурсивным (см. «рекурсивное множество»). Пример счётного нерекурсивного множества я приводил: множество значений функции busy beaver. Рекурсивность базовой операции означает, что она является рекурсивной функцией. В частности, определенная на конечном множестве функция выбора символа из конечного алфавита по определению является рекурсивной.

[Someone]

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

хочу теперь Вас призвать рассмотреть понятие «аналитической иерархии» - литературы на сей счёт полно. Если хотя бы некоторые базовые операции являются оракулами

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

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

Это я к тому, что в природе до сих пор не встречались такие исполнители, которые «умеют выполнять» роль оракулов

А это совсем не к месту. Мы обсуждаем не природу, а математику.

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

Рекурсивность алфавита означает, что оное множество символов является рекурсивным

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

[epros]

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

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

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

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

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

Это я к тому, что в природе до сих пор не встречались такие исполнители, которые «умеют выполнять» роль оракулов

А это совсем не к месту. Мы обсуждаем не природу, а математику.

Это Вы мне сейчас говорите? Кажется, это не я (первый) употребил нематематическое выражение «умеют выполнять».

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

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

Рекурсивность алфавита означает, что оное множество символов является рекурсивным

Что такое рекурсивное множество (натуральных чисел), я знаю. С чего Вы взяли, что символы алфавита являются натуральными числами?

Рекурсивное множество - это не только натуральных чисел. Натуральные числа могут «кодировать» любые объекты (поэтому некоторые полагают, что арифметику можно рассматривать в качестве метатеории для математики в целом). Один из банальных примеров кодирования - это рассматривать алфавит из символов $a$, индексированных натуральными числами.

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

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

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

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

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

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

[Someone]

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

Ну так а я о чём? Что существуют "более широкие классы" понимания вычислимости - расширяющие стандартное понятие. Это и называется "аналитической иерархией". Почему это "не имеет отношения к обсуждаемому вопросу"?

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

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

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

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

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

Кажется, это не я (первый) употребил нематематическое выражение «умеют выполнять».

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

[epros]

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

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

Замечательно, теперь осталось понять, что есть «стандартное» понятие алгоритма и расширенное - вплоть до любого n-ого уровня аналитической иерархии.

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

Базовые операции для машины Тьюринга - это, например, распознавание символа, запись символа, перемещения головки, переходы конечного автомата из одного состояния в другое.

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

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

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

Кажется, это не я (первый) употребил нематематическое выражение «умеют выполнять».

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

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

-- Вт авг 07, 2012 15:55:49 --

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

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

Да, кстати о птичках: Базовая операция нормального алгоритма Маркова (поиск и замена подстроки) - рекурсивная, но не конечная функция.

[Munin]

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

epros, Вы чего-то чудите.

Вот я чувствовал, но не был уверен. К тому же, просто хотел чему-то научиться у хорошего человека. Теперь подожду воспринимать всё это за чистую монету. Жаль, интересно было. Ну, может, apriv ещё выскажется.

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

Действительное число - это не "приближение".

Действительное число - это, конечно, не приближение. Потому что приближение к чему? К нестандартному действительному? Их в природе тоже не обнаружено. (В природе, подчёркиваю. Потому что вы, видимо, регулярно путаете в этой теме природу и физику. Физика - это не природа, а наука о природе, продукт человеческой мысли и собрание человеческих представлений. В природе объекты материальны, в физике идеальны, например. Они - идеализация природных. И одновременно - абстракция. Абстракция - это отвлечение, в случае физики - отвлечение от незначимых деталей, например, абстракция материальной точки, отвлекающаяся от размеров (когда это правомерно), от цвета, вкуса и запаха.)

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

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

Такой риторический вопрос, предполагаемый ответ на который на самом деле неверен, это тот ещё приёмчик...

Просто вы предполагаемый ответ не угадали. На вопрос "какое отношение математика имеет к практике" подразумеваемый ответ не "никакого", а "непрямое". Разумеется.

Хотите - спорьте со своим "оппонентом типовым, резиновым", но я из такого спора удаляюсь.

[Someone]

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

Замечательно, теперь осталось понять, что есть «стандартное» понятие алгоритма и расширенное - вплоть до любого n-ого уровня аналитической иерархии.

Это для обсуждаемого вопроса (понятие алгоритма) не имеет никакого значения.

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

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

Нет. Это не базовая операция. Это программа. Работа которой состоит из базовых операций: распознать текущий символ, напечатать новый, переместить головку, изменить состояние конечного автомата, ...

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

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

Ну, например, машина Тьюринга умеет перемещать головку по ленте. Чего в этой операции "рекурсивного"? Машина Тьюринга просто умеет это делать.
Если хотите, вводите свои базовые операции и пишите алгоритм перемещения головки, используя свои базовые операции. Потом повторите это для своих базовых операций, и так далее до бесконечности.

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

Да, кстати о птичках: Базовая операция нормального алгоритма Маркова (поиск и замена подстроки) - рекурсивная, но не конечная функция.

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

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

-- Вт авг 07, 2012 16:52:24 --

P.S. А вообще, мы тут жутким оффтопиком занимаемся.

[epros]

(Оффтоп)

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

Вот я чувствовал, но не был уверен. К тому же, просто хотел чему-то научиться у хорошего человека. Теперь подожду воспринимать всё это за чистую монету. Жаль, интересно было. Ну, может, apriv ещё выскажется.

Ну, ну, ждите. Хочу заметить, что обсуждение с Someone почему-то оказывается на порядок конструктивнее, чем с Вами... всё-таки ... не смотря ни на что...

(Оффтоп)

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

В природе объекты материальны

Не стоит тащить сюда философию.

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

Приближением является не действительное число...

Напоминаю, что весь этот флейм разгорелся после того, как Вы не смогли внятно определить "действительное число" - так, чтобы было понятно, что конкретно означает фраза "алгоритм на n-том шаге выдаёт действительное число". И этот вопрос был не праздный, поскольку я не исключаю, что Вы ухитритесь определить "действительное число" таким образом, что их множество окажется рекурсивным. Теперь я вижу, что даже ответа на вопрос о том, что такое число $\pi$, вероятно от Вас не дождусь. Так как же всё-таки объяснить незнающему человеку что это такое, чтобы он мог посмотреть и убедиться: да, действительно, алгоритм выдал число $\pi$?

-- Вт авг 07, 2012 17:20:14 --

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

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

Замечательно, теперь осталось понять, что есть «стандартное» понятие алгоритма и расширенное - вплоть до любого n-ого уровня аналитической иерархии.

Это для обсуждаемого вопроса (понятие алгоритма) не имеет никакого значения.

Для обсуждения понятия алгоритма не имеет значения стандартное оно или расширенное?

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

Нет. Это не базовая операция. Это программа. Работа которой состоит из базовых операций: распознать текущий символ, напечатать новый, переместить головку, изменить состояние конечного автомата, ...

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

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

Ну, например, машина Тьюринга умеет перемещать головку по ленте. Чего в этой операции "рекурсивного"? Машина Тьюринга просто умеет это делать.
Если хотите, вводите свои базовые операции и пишите алгоритм перемещения головки, используя свои базовые операции. Потом повторите это для своих базовых операций, и так далее до бесконечности.

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

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

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

Да, кстати о птичках: Базовая операция нормального алгоритма Маркова (поиск и замена подстроки) - рекурсивная, но не конечная функция.

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

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

-- Вт авг 07, 2012 17:31:12 --

(Оффтоп)

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

P.S. А вообще, мы тут жутким оффтопиком занимаемся.

Есть предложение выделить ветку, начатую с вопроса Muninа, в отдельную дискуссионную тему про вычислимость.

[Munin]

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

Хочу заметить, что обсуждение с Someone почему-то оказывается на порядок конструктивнее, чем с Вами...

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

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

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

В природе объекты материальны

Не стоит тащить сюда философию.

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

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

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

Приближением является не действительное число...

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

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

[Someone]

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

Для обсуждения понятия алгоритма не имеет значения стандартное оно или расширенное?

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

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

Вообще-то согласно определению машины Тьюринга - это базовая операция.

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

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

Базовая операция нормального алгоритма Маркова (поиск и замена подстроки) - рекурсивная, но не конечная функция.

Вы называете эту (или любую другую) операцию рекурсивной не потому, что знаете алгоритм её выполнения, а просто потому, что умеете её выполнять. Хотя и не знаете, что происходит у Вас "внутри", когда Вы её выполняете. Ну Бог с Вами. Однако в таком случае Ваше требование рекурсивности алфавита и базовых операций является бессодержательным. Они "рекурсивны" просто по Вашему определению. И, разумеется, можно написать программу для этой операции (замена первого вхождения подстроки $\alpha$ подстрокой $\beta$ выполняется программой из одной команды $\alpha\to\cdot\beta$, где точка означает, что после выполнения команды надо остановиться). Но я имел в виду нечто более содержательное, а не эту тривиальность.

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

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

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

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

-- Вт авг 07, 2012 19:20:45 --

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

Есть предложение выделить ветку, начатую с вопроса Muninа, в отдельную дискуссионную тему про вычислимость.

Не возражаю.

[epros]

(Оффтоп)

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

Видимо, потому что вы его не ненавидите, и не лезете в придирки ...

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

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

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

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

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

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

Это зависит от того, в чём именно заключается определение. И тут мы неизбежно возвращаемся к разнице между стандартным и расширенным определением рекурсивности, которую Вы почему-то не захотели обсуждать.

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

Только в более абстрактном виде.

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

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

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

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

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

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

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

[Munin]

(Оффтоп)

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

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

В чём, разумеется, вы своего участия видеть не намерены...

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

Так что, ваши заявления о том, как вы ко мне относитесь, не проходят сопоставления с практикой. Возможно, вы даже в них искренне верите - факт остаётся фактом.

[Someone]

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

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

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

Насколько я знаю, А.Т.Фоменко, до того как стал крупнейшим авторитетом по альтернативной хронологии, пытался применять алгоритмический подход в топологии трёхмерных многообразий.

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

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

Извините, но заявленный Вами подход состоит в том, что Вы базовые операции сразу же объявляете рекурсивными. Согласен: соответствующий алгоритм состоит из одной команды.

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

Наверное, Вы хотели сказать "закодировать все состояния машины Тьюринга и ленты"?

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

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

А у меня нет возражений. (Удивил?)

Если помните, меня удивляли Ваши возражения, а не их отсутствие.

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

Просто стандартное определение машины Тьюринга предполагает конечный алфавит

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

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

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

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

[Xaositect]

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

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

Просто стандартное определение машины Тьюринга предполагает конечный алфавит

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

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

[Someone]

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

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

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