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

, где

- алфавит ленты (конечен),

- множество состояний МТ,

- конечное отображение вида

,

. В силу конечности

,

тоже конечно. Ну и как перебирать все программы, очевидно. Перекодировать их тоже можно
Нормальные алгоритмы Маркова можно также перебрать.
-- Вт фев 04, 2014 15:54:45 --Из них многие и многие зацикливаются. Такие Вы тоже считаете «программами, вычисляющими функции одного аргумента»?
не бойтесь...блин, ну вот, что-то я засомневался
-- Вт фев 04, 2014 16:04:53 --Оно основано там на том, что неявно подразумевается, что множество

перечислимо? Мне не понятно почему оно перечислимо. Поэтому я и создал этот тред.
Ааа, так там явно задан способ записи функций - запись вида

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