Сomputability theory на языке рекурсивных функций (?)

[_hum_]

Сразу оговоримся, что под Computability theory здесь понимается та часть теории вычислений (theory of computation), которая занимается вопросами, связанными только с принципиальной возможностью решения тех или иных задача с помощью алгоритма. Вопросы вычислительной сложности решения этих задач в нее не входят (этим занимается Complexity theory). Генеалогия этих дисциплин представлена здесь:theoretical_computer_science.svg

Основной мой вопрос: можно ли всю эту теорию полностью перевести на языке рекурсивных функций, не привлекая машинных понятий типа инструкций и их потактового исполнения (не опираясь на понятия теории машин Тьюринга, RAM и проч.)?

То есть, можно ли на языке рекурсивных функций
1) дать определения всех понятий computability theory;
2) сформулировать все теоремы этой теории;
3) сформулировать все доказательства этих теорем.

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

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

Подтверждение этому - известные равносильные понятия:
- алгоритм $\leftrightarrow$ машина Тьюринга $\leftrightarrow$ рекурсивная функция
- универсальный алгоритм $\leftrightarrow$ универсальная машина Тьюринга $\leftrightarrow$ универсальная рекурсивная функция
- алгоритмически перечислимое множество $\leftrightarrow$ перечислимое машиной Тьюринга множество $\leftrightarrow$ множество, являющееся областью значений рекурсивной функции / множество, индикаторная функция которого рекурсивна и всюду определена на нем самом.
- алгоритмически разрешимое множество $\leftrightarrow$ разрешимое машиной Тьюринга множество $\leftrightarrow$ множество с общерекурсивной индикаторной функцией.
- алгоритм с оракулом A $\leftrightarrow$ машина Тьюринга с оракулом A $\leftrightarrow$ A - рекурсивная функция.

Аргумент $A1)$ говорит в пользу того, что все теоремы теории можно переформулировать в терминах рекурсивных функций.

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

И оно же легко доказывается на языке рекурсивных функций:
пусть $A,B \subset \mathbb{N}$ перечислимые множества. Тогда, по определению, имеются полуразрешающие их индикаторные функции $I_A, I_B$. Рассмотрим новую функцию $I(x) = \max\{I_A(x), I_B(x)\}$. Поскольку операция максимума не выводит за класс рекурсивных функций, то $I$ - также рекурсивная. Очевидно, это полуразрешающая объединение множеств функция. Ч.т.д.

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


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

[Профессор Снэйп]

Можно ли печатать на клавиатуре носом или смотреть телевизор, стоя вверх ногами? Наверное, можно... Вопрос в том, нужно ли

Надеюсь, знаете, что в теории вычислимости обычно обозначают $\varphi_x(y)$. Это функция от аргументов $x, y$, при каждом фиксированном $x$ она, как функция от $y$, совпадает с функцией, вычислимой на машине Тьюринга с номером $x$. Короче, универсальная частично рекурсивная функция для класса всех одноместных частично рекурсивных функций.

Докажите, что множество

$$ K = \{ x : \varphi_x(x) \text{ определено} \} $$

не является рекурсивным. Вперёд!

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

Если и это осилите... ну, докажите хотя бы, что если упомянутое выше $K$ $m$-сводится к множеству $A \oplus B$, то оно либо $m$-сводится к $A$, либо $m$-сводится к $B$.

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

Вы вот, если честно, сейчас пытаетесь шагнуть на столетие назад. То, что Вы проповедуете, считалось само собой разумеющися годах где-то в 1930-ых. Гёдель, Чёрч и Клини так и пытались всё оформлять, не прибегая по возможности к явным описаниям пошаговых конструкций и оставаясь внутри привычной на начало XX века чисто дескриптивной математики. Вот только никто этой хернёй уже давно не мается. Разве что авторы устаревших на несколько десятилетий учебников! Читайте Роджерса, потом Соара и вся эта дурь у Вас из головы быстро вылетит!!

-- Сб авг 25, 2012 19:03:10 --

Если уж действительно никак не можете жить с машинным подходом, скачайте и прочитайте вот такую книжку. Там основы теории вычислимости излагаются через определимость $\Sigma$-формулами: чисто логический подход, никаких явных алгоритмов, никаких вычислений по шагам. Причём подход этот довольно неплохо востребован в том смысле, что многие вполне серьёзные дядьки только этим и занимаются. Говорят: "Не любим мы, дескать, классику, от приоритетов моск кипит и взрывается, а тут всё чисто на формулах..." К тому же этот подход весьма востребован для обобщения вычислимости на произвольные объекты. Например, функции на действительных числах: какие из них следует считать вычислимыми? Есть определённый резон в том, чтобы считать таковыми функции, $\Sigma$-определимые в $\mathbb{HF}(\mathbb{R})$. Ну или в $\mathbb{HYP}$, если хочется побольше инструментов для нормального анализа.

Но вот по мне, так во всех этих лямбда-исчислениях и допустимых множествах сам чёрт ногу сломит! Короче, не моё. Это как все математики глобально делятся на непрерывных и дискретных, также и в теории вычислимости специалисты делятся на специалистов по приоритетным конструкциям и специалистов по допустимым множествам. У нас половина отдела в институте на допустимых множествах сидит. Причём одни не понимают других, а те первых. Страшно далеки они друг от друга

-- Сб авг 25, 2012 19:14:14 --

_hum_ в сообщении #610071 писал(а):

И оно же легко доказывается на языке рекурсивных функций:
пусть $A,B \subset \mathbb{N}$ перечислимые множества. Тогда, по определению, имеются полуразрешающие их индикаторные функции $I_A, I_B$. Рассмотрим новую функцию $I(x) = \max\{I_A(x), I_B(x)\}$. Поскольку операция максимума не выводит за класс рекурсивных функций, то $I$ - также рекурсивная. Очевидно, это полуразрешающая объединение множеств функция. Ч.т.д.

Ваша $I(x)$ будет "полуразрешать" не объединение, а пересечение!!!

[Профессор Снэйп]

Вот, кстати, тоже хорошее упражнение: придумайте пару частично рекурсивных функций $f(x), g(x)$ такую, что функция $h(x) = \mathrm{strongmax} \{ f(x), g(x) \}$ не является частично рекурсивной

Здесь $\mathrm{strongmax}$ - "сильный максимум", который вводится следующим образом: если оба значения $f(x), g(x)$ определены, то под ним понимается обычный максимум, если оба не определены, то он не определён, а если определено ровно одно из двух значений, то сильный максимум считается равным этому самому значению. Короче, тот самый максимум, который Вам был нужен для работы с объединением

[Munin]

(Оффтоп)

_hum_ в сообщении #610071 писал(а):

Генеалогия этих дисциплин представлена здесь:theoretical_computer_science.svg

Завлекательная картинка. У меня сразу офтопные вопросы: а являются ли человеческие языки контекстно-зависимыми, рекурсивно-перечислимыми, или даже рекурсивно-неперечислимыми. Где бы их задать, а может быть, и обсудить на наивном уровне?

[Профессор Снэйп]

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

Завлекательная картинка. У меня сразу офтопные вопросы: а являются ли человеческие языки контекстно-зависимыми, рекурсивно-перечислимыми, или даже рекурсивно-неперечислимыми. Где бы их задать, а может быть, и обсудить на наивном уровне?

Ну, либо перечислимыми, либо не перечислимыми они уж всяко являются. У нас всё-таки бинарная логика

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

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

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

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

-- Сб авг 25, 2012 20:32:32 --

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

[Munin]

(Оффтоп)

Профессор Снэйп в сообщении #610445 писал(а):

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

Простите, речь, вроде о синтаксических конструкциях из слов, а не просто о том, что написано в словаре.

Профессор Снэйп в сообщении #610445 писал(а):

Вообще, иерархия Хомского - это, на мой взгляд, какая-то дурь.

Учитывайте, что Хомский прежде всего лингвист, а не математик, и вычислительные аспекты его волновали мало.

[Профессор Снэйп]

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

-- Сб авг 25, 2012 20:53:26 --

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

Простите, речь, вроде о синтаксических конструкциях из слов, а не просто о том, что написано в словаре.

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

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

Франсуа Рабле писал(а):

...хитроумнейший вопрос о том, может ли химера, в пустом пространстве жужжащая, поглотить вторичные интенции.

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

Я на вводной лекции в первом семестре как честный преподаватель всегда это проговариваю. И толкаю что-то типа: "Ну вот, теория вычислимости как раздел математики и практика программирования... Как-то они связаны? Ну, как-то, наверное, да... Вот представьте себе ситуацию, где-нибудь в Макларене или Феррари собрались конструкторы гоночных болидов и обсуждают: а вот если мы новую резину поставим, и форму машины тщательно просчитаем, и мотор супермощный, то Шумахер у нас 350 км./ч. по трассе поедет! Нет, даже 400 км./ч. поедет! И тут приходит к ним физик-теоретик и заявляет: "Сколько не старайтесь, всё равно быстрее скорости света двигаться не будет!" Прав этот физик? Абсолютно прав! Сказал он что-нибудь ценное для автоконструкторов? Это вряд ли... Ну так вот мы тут с вами будем в основном заниматься теорией."

[_hum_]

Профессор Снэйп в сообщении #610408 писал(а):

Можно ли печатать на клавиатуре носом или смотреть телевизор, стоя вверх ногами? Наверное, можно... Вопрос в том, нужно ли

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

Профессор Снэйп в сообщении #610408 писал(а):

Ваша $I(x)$ будет "полуразрешать" не объединение, а пересечение!!!

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

Munin

(Оффтоп)

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

У меня сразу офтопные вопросы: а являются ли человеческие языки контекстно-зависимыми, рекурсивно-перечислимыми, или даже рекурсивно-неперечислимыми. Где бы их задать, а может быть, и обсудить на наивном уровне?

Где-то ж здесь была тема про задание естественного языка. А если нет, можно завести.

[Профессор Снэйп]

_hum_ в сообщении #610489 писал(а):

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

Да ну теоретически-то конечно всё можно. Примерно как любую прикладную прогу на ассемблере написать. Если Вам не жалко собственного времени - разбирайтесь

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

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

Опять же чисто в теории... Способности человеческого мозга ограничены. Безусловно, любое корректное доказательство из теории вычислимости можно трансформировать в конечный текст, в котором будут фигурировать лишь примитивная рекурсия, суперпозиция, минимизация и базисные функции. Если это какая-то простенькая теоремка из начального курса, проблем нет: пацан сказал, пацан ответил. Ну а если это статья Лемппа в JSL, где он на 60 страниц с чудовищным приоритетом доказывает какую-нибудь хитровыдуманную хрень про расщепления дохрена-низких множеств? Там на нормальную-то конструкцию, человеческим "языком высокого уровня" описанную, можно полгода потратить

_hum_ в сообщении #610489 писал(а):

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

С пересечением всё нормально.

Я не знаю, что там за "полуразрешимость" такая, очередной школярский термин. А так-то всё просто. Множество является рекурсивно перечислимым тогда и только тогда, оно является областью определения частично рекурсивной функции. Иногда требуют, чтобы функция кроме определённости была ещё и чему-то конкретному равна на элементах из множества, например, $1$. Но это всё от лукавого, достаточно просто определённости, а потом уже, если есть непреодолимое желание сделать лишнюю работу, можете брать её композицимю с одноместной функцией, равной константе $1$. Ну или, если в другую сторону, композицию с функцией, равной $1$ в единице и не определённой на других аргументах. Короче, рекурсивно перечислимые множества - это, в точности, области определения частично рекурсивных функций. Ну вот теперь если область определения $f$ равна $A$, а область определения $g$ равна $B$, то $A \cap B$ будет областью определения функции $h(x) = h'(f(x), g(x))$, где $h'$ - любая всюду определённая вычислимая функция. Максимум, не максимум - пофиг какая, лишь бы рекурсивной была!

А с объединением никакой подобный номер в принципе не проходит! Чтобы доказывать перечислимость объединения перечислимых множеств, надо вспоминать критерий: множество рекурсивно перечислимо тогда и только тогда тогда, когда оно является областью значений частично рекурсивной функции. И по двум данным функциям строить третью, область значений которой будет объединением областей значений двух исходных функций.

-- Вс авг 26, 2012 00:27:54 --

Кстати, сам термин рекурсивно перечислимое множество впервые появился в такой формулировке: множество называем рекурсивно перечислимым, если оно либо пусто, любо является областью значений всюду определённой рекурсивной функции. Оно и по звучанию термина даже логично: когда функция берёт все подряд натуральные значения в качестве аргумента, то своими значениями она это множество перечисляет (пустое множество - исключительный случай, примерно как $\sin x / x = 1$ при $x = 0$ в матане). Люди, которые вводили такую формализацию (кажется, Клини или Пост, не помню точно), делали это для придания точного значения вполне конкретной вещи: эффективной перечислимости. Типа, множество перечислимо, если мы можем запрограммировать машину и запустить её, она будет работать бесконечно долго и время от времени на ленте будут появляться числа, принадлежащие перечисляемому множеству. А вот то, что рекурсивно перечислимые множества суть области определения чрф - это уже специальная теорема, критерий, не имеющий прямой мотивации, хотя и удобный, который надо доказывать, беря в качестве базового определения именно область значений).

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

[_hum_]

Профессор Снэйп в сообщении #610503 писал(а):

Да ну теоретически-то конечно всё можно. Примерно как любую прикладную прогу на ассемблере написать. Если Вам не жалко собственного времени - разбирайтесь

Профессор Снэйп, это очень важно для дальнейшего (чтобы я потом мог ссылаться в своих рассуждениях на этот факт) - так каков ответ на мой вопрос,

_hum_ в сообщении #610071 писал(а):

можно ли всю эту теорию полностью перевести на языке рекурсивных функций, не привлекая машинных понятий типа инструкций и их потактового исполнения (не опираясь на понятия теории машин Тьюринга, RAM и проч.)?

То есть, можно ли на языке рекурсивных функций
1) дать определения всех понятий computability theory;
2) сформулировать все теоремы этой теории;
3) сформулировать все доказательства этих теорем.

можно или нельзя?

Профессор Снэйп в сообщении #610503 писал(а):

С пересечением всё нормально.

Я имел в виду ваше изначальное замечание:

Профессор Снэйп в сообщении #610408 писал(а):

Ваша $I(x)$ будет "полуразрешать" не объединение, а пересечение!!!

При этом

_hum_ в сообщении #610071 писал(а):

$I(x) = \max\{I_A(x), I_B(x)\}$

Так разве ж $I(x)$ будет полуразрешать $A\cap B$ (являться индикаторной функций этого множества, которая рекурсивна и определена на нем самом)?
Для пересечения полуразрешающей функцией будет $I'(x) = \min\{I_A(x), I_B(x)\}$.

Профессор Снэйп в сообщении #610503 писал(а):

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

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

[Профессор Снэйп]

_hum_ в сообщении #610514 писал(а):

можно или нельзя?

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

Вот здесь читайте, стр. 101 - 110. Там очень подробно всё разжёвано, для первокурсников старался.

-- Вс авг 26, 2012 00:46:21 --

_hum_ в сообщении #610514 писал(а):

Так разве ж $I(x)$ будет полуразрешать $A\cap B$ (являться индикаторной функций этого множества, которая рекурсивна и определена на нем самом)?

Чёт Вы опять куда-то в пампасы гусей погнали. Я всё очень ясно Вам расписал.

Если хотите плотно, досконально и в суперразжёванном виде, дайте определение того, что значит "полуразрешать". То, с которым Вы желаете работать. Это, ещё раз повторюсь, школярский термин, не пользующийся популярностью у солидных людей. Как в школе: нельзя писать "область определения", учительница двойку поставит, надо писать три волшебных буквы "О. Д. З.", согласно строгим требованиям районо "Индикаторная функция" - ф ту же топку!

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

-- Вс авг 26, 2012 00:50:48 --

_hum_ в сообщении #610514 писал(а):

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

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

Давайте я дам такое определение: натуральное число $n$ называется чётным, если число $2n$ без остатка делится на $4$. Критерий? Критерий! Давайте возмём его за базовое определение, в чём проблема?

Вы вот сейчас всей этой темой демонстрируете свою неправоту. У Вас отсутствует понимание сути понятий, и Вы из-за этого спотыкаетесь на совершеннейшей ерунде! Даже в математике у понятий бывает "физический смысл", они ведь не из пустого места берутся! Функция непрерывна, если при приближении $x$ к $x_0$ значение $f(x)$ приближается к $f(x_0)$. Множество эффективно перечислимо, если компьютер можно запрограммировать так, чтобы он по ходу работы выдавал список элементов этого множества. Прежде всего эти вещи надо чувствовать, а уже потом переходить на эпсилон-дельта язык или говорить про индикаторные функции!

[Munin]

(Оффтоп)

Профессор Снэйп в сообщении #610448 писал(а):

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

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

[_hum_]

Профессор Снэйп в сообщении #610519 писал(а):

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

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

Профессор Снэйп в сообщении #610519 писал(а):

Вот здесь читайте, стр. 101 - 110. Там очень подробно всё разжёвано, для первокурсников старался.

Сложнова-то читать - я привык к другим определениям (больше похожих на те, что даются в Верещагиние, Шене).

Профессор Снэйп в сообщении #610519 писал(а):

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

Итак, в приводимом мною ранее примере с объединением перечислимых множеств использовалось следующее определение:
множество называется перечислимым, если существует такая рекурсивная функция, которая на этом множестве всюду принимает значение 1, а в остальных точках она либо не определена, либо принимает значение 0.

Профессор Снэйп в сообщении #610519 писал(а):

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

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

-- Сб авг 25, 2012 23:50:17 --

Munin

(Оффтоп)

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

Я просто намекаю на то, что ни в бытовом, ни в лингвистическом смысле, это не слова, а тексты, и ни в каких конечных словарях они не перечислены.

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

[Профессор Снэйп]

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

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

В бытовом и в лингвистическом смысле не говорят про перечислимость или контекстную свободность

[Munin]

(Оффтоп)

Профессор Снэйп в сообщении #610542 писал(а):

В бытовом и в лингвистическом смысле не говорят про перечислимость или контекстную свободность

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