Изменения
→Примеры разрешимых множества
Заметим, что программа нигде не может зависнуть.
}}
== Примеры разрешимых множества ==
{{Лемма
|statement=
Множество всех рациональных чисел, меньших числа ''e'' (основания натуральных логарифмов), разрешимо.
|proof=
Воспользуемся известной формулой для вычисления числа ''e'' <tex> = \sum \limits_{n=0}^{\infty} 1/n! </tex>, с помощью которой ''e'' может быть вычислено с произвольной точностью. Приведем программу, разрешающую данный вопрос:
<tex>p(r): </tex>
<tex>int[] \ eDigits = getDigits(e) \ // \ array \ of \ digits \ in \ e </tex>
<tex>int[] \ rDigits = getDigits(r) \ // \ array \ of \ digits \ in \ r </tex>
<tex> \mathrm{for}</tex> (i = 0 to eDigits.length())
<tex> \mathrm{if} </tex> (rDigits[i] > eDigits[i])
<tex> \mathrm{return} \ 0 </tex>
<tex> \mathrm{if} </tex> (rDigits[i] < eDigits[i])
<tex> \mathrm{return} \ 1 </tex>
Так как число ''e'' иррационально, то ответ будет найден.
}}
