Изменения

Перейти к: навигация, поиск

Разрешимые (рекурсивные) языки

9 байт добавлено, 23:06, 11 января 2015
Нет описания правки
}}
Другими словами, ''универсальный язык'' {{---}} это язык всех пар "программа программ и её вход" такихих входных данных, что на которых программа на входе возвращает <tex>1</tex>. Программа {{---}} это набор строк, занумеровав которые, можем получить биекцию между строками и натуральными числами.
Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.
 
Так как программа {{---}} это набор строк, занумеровав которые, можем получить биекцию "число" <tex>\to</tex> "строка"
== Примеры разрешимых множества ==
Анонимный участник

Навигация