Изменения

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

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

382 байта убрано, 01:51, 10 января 2015
Примеры разрешимых множества
Множество всех рациональных чисел, меньших числа <tex>e</tex> (основания натуральных логарифмов) или <tex>\pi</tex>, разрешимо.
|proof=
Для чисел <tex>e, \ \pi</tex> существуют различные техники нахождения их точного представления, одна их которых описана в статье <ref>http://www.mathpropress.com/stan/bibliography/spigot.pdf</ref> [http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]. Авторами алгоритма и его нарицателями являются американские математики Стенли Рабинович (Stanley Rabinowitz) и Стен Вэгон (Stan Wagon), которые создали свой алгоритм для нахождения цифр числа таким образом, возможно получить необходимый знак чисел <tex>e, \ \pi</tex> в 1995 году. Сама же идея алгоритма вышла из-под пера некого Сейла (Sale) ещё в 1968 году, и предназначался тот алгоритм для нахождения цифр числа <tex>e</tex>за конечное время.
Десятично представление рационального числа <tex>r</tex> может быть получено с любой точностью.
Анонимный участник

Навигация