множество всех алгоритмов перечислимо

[cscscs]

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

[Someone]

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

[nikvic]

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

[cscscs]

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

Поскольку запись алгоритма — это слово определённой синтаксической структуры

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

-- 04.02.2014, 18:34 --

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

[Sonic86]

cscscs в сообщении #822709 писал(а):

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

А он нужен?

cscscs в сообщении #822709 писал(а):

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

А такая грамматика существует? Просто так непонятно. Если есть конструктивное доказательство ее существования, то можно посмотреть способ ее построения в общем случае.

Насколько я понимаю, Вы не можете по строке сказать, является ли она программой или нет. Т.е. когда мы говорим, что Вам задано множество программ, мы неявно подразумеваем, что нам задана и формальная грамматика их построения + еще и способ их исполнения. (и тогда вопрос тривиален)
Что такое программа? $abc$ - это программа? Брейнфаковские тексты - это ведь программы...
Тексты программ - это слова в заданном КС-языке. Нетрудно придумать разрешимый КЗ-язык, построить явную биекцию между этим КЗ-языком и КС-языком и вуаля - тексты КЗ языка можно исполнять как программы, но они не могу быть порождены формальной КС-грамматикой.
А вот как обстоит дело с соотношением КЗ-языков и рекурсивных множеств - я не знаю

[patzer2097]

cscscs в сообщении #822654 писал(а):

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

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

[cscscs]

Sonic86 в сообщении #822731 писал(а):

А он нужен?

Чтобы осуществить доказательство как сказал Someone - да.

Sonic86 в сообщении #822731 писал(а):

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

Неа. Мне не очевидно другое. Что есть программа, которая печатает (в произвольном порядке и с произвольными промежутками времени) вообще все программы и только их.

Sonic86 в сообщении #822731 писал(а):

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

Мне не очевидно как ее задать и что это вообще можно сделать сразу для всех алгоритмов.

Sonic86 в сообщении #822731 писал(а):

А она существует?

Это я спрашиваю . Если да, то теорема доказана, если я правильно понял Someone.

-- 04.02.2014, 19:13 --

Sonic86 в сообщении #822731 писал(а):

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

Так оно есть?

-- 04.02.2014, 19:20 --

patzer2097 в сообщении #822741 писал(а):

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

Не обязательно. Функции частичные. Из натуральных чисел в натуральные.

[Sonic86]

cscscs в сообщении #822743 писал(а):

Так оно есть?

Да не знаю я.

cscscs в сообщении #822743 писал(а):

Неа. Мне не очевидно другое. Что есть программа, которая печатает (в произвольном порядке и с произвольными промежутками времени) вообще все программы и только их.

Если КС-грамматика языка фиксирована, то тогда мы сможем проверить, является ли строка программой (тут понятно, да?).
Если же КС-грамматика языка произвольна, то все слова являются программами в некотором подходящем КС-языке (и тогда существует программа, которая печатает все программы). Действительно, пусть задан алфавит $A$. Я могу перенумеровать все строки в $A$ натуральными числами, и пронумеровать все программы C++ в порядке возрастания. После чего я могу поставить в соответствие строке с номером $n$ из $A$ программу на C++ с тем же номером и написать компилятор, который по строке $w\in A^*$ вычисляет ее номер, по номеру - вычисляет программу на C++ и исполняет последнюю. Если угодно, можно здесь рассматривать только одноместные функции.
Нравится?
Это все к тому, что такое "программа"?

[cscscs]

Да, я забыл сказать в самом начале, что функции вычислимые имеются в виду конечно же.

[patzer2097]

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

[cscscs]

Sonic86 в сообщении #822747 писал(а):

Если КС-грамматика языка фиксирована, то тогда мы сможем проверить, является ли строка программой (тут понятно, да?).

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

-- 04.02.2014, 19:38 --

patzer2097 в сообщении #822752 писал(а):

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

Нет. Если значение функции от данного аргумента не определено, то либо алгоритм не останавливается, либо останавливается, но ничего не печатает.

-- 04.02.2014, 19:42 --

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

[svv]

nikvic в сообщении #822694 писал(а):

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

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

[nikvic]

svv в сообщении #822758 писал(а):

Из них многие и многие зацикливаются. Такие Вы тоже считаете «программами, вычисляющими функции одного аргумента»?

Разумеется.

[Sonic86]

cscscs в сообщении #822753 писал(а):

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

А можно на машинах Тьюринга?

(Если да то)

"Программная часть" машины Тьюринга - это тройка $(A, Q, \delta)$, где $A$ - алфавит ленты (конечен), $Q$ - множество состояний МТ, $\delta$ - конечное отображение вида $a_iq_j\to a_kq_lT$, $T\in\{Left,Right,Stop\}, a_i, a_k\in A, q_j,q_l\in Q$. В силу конечности $A,Q, \{Left,Right,Stop\}$, $\delta$ тоже конечно. Ну и как перебирать все программы, очевидно. Перекодировать их тоже можно

Нормальные алгоритмы Маркова можно также перебрать.

-- Вт фев 04, 2014 15:54:45 --

svv в сообщении #822758 писал(а):

Из них многие и многие зацикливаются. Такие Вы тоже считаете «программами, вычисляющими функции одного аргумента»?

$\varnothing \in A^B$ не бойтесь
...блин, ну вот, что-то я засомневался

-- Вт фев 04, 2014 16:04:53 --

cscscs в сообщении #822768 писал(а):

Оно основано там на том, что неявно подразумевается, что множество ${p_0,p_1,...}$ перечислимо? Мне не понятно почему оно перечислимо. Поэтому я и создал этот тред.

Ааа, так там явно задан способ записи функций - запись вида $f(x_1,...,x_n)$, и конечное множество базовых функций. Ну и перебираем их все и все.
Т.е. "грамматика" языка задана явно сразу.
Ну вот, ТС удалил свой пост

[patzer2097]

Sonic86 в сообщении #822766 писал(а):

$\varnothing \in A^B$ не бойтесь

только если $A$ пусто но у ТС - свои определения