1. Въведение
2. Теория
2.1. Изчислимост на реални числа
2.2. Примитивно рекурсивна изчислимост
2.3. Изчислимост на функции върху реални числа
2.4. Представяне (на число и грешка)
2.5. Пресмятане на елементарните функции (число и грешка)
2.5.1. Грешка при събиране
2.5.2. Грешка при умножение
2.5.3. Реципрочно
2.5.4. Квадратен корен
2.5.5. Логаритъм
2.5.6. Експонента
2.5.7. Константата π.
2.5.8. Тригонометрични функции
2.6. Извеждане на резултат
3. Реализация.
3.1. Плаваща запетая с произволна точност (class LongFloat)
3.2. Грешката (class ErrorEst)
3.3. Представяне на термове (class RealObject)
3.3.1. Видове обекти
3.3.2. Множествено обръщение към обект
3.3.3. Кеширане на пресмятанията
3.3.4. Ефективност на представянето
3.4. Потребителската страна (class Real)
3.4.1. Инициализация и приключване
3.4.2. Типът Real
3.4.2.1. Конструктори, деструктори, присвояване
3.4.2.2. Константи
3.4.2.3. Операции
3.4.2.4. Изискване на резултат
3.4.3. Пример на потребителска програма
3.5. Други избрани моменти в реализацията
3.5.1. Управление на блоковете с данни
3.5.2. Умножение чрез конволюция
3.5.3. Регулиране на дълбочината на спускане в рекурсия
3.5.4. Скриване на детайлите на реализацията
3.5.5. Преносимост на кода
4. Резултати
4.1. Пресмятане на константи и елементарни функции
4.2. Възможност за справяне с по-сложни задачи
4.2.1. Безпроблемно използване на шаблони
4.2.2. Конволюция на реални числа
5. Какво може да бъде добавено
Библиография
Резюме:
Математическото понятие “реално число” не е представимо с изчислима функция в която и да е от множеството еквивалентни дефиниции за изчислимост. Няма как едно неизброимо поле да се представи в рамките на изброимо множество, каквото са изчислимите функции. В литературата съществуват и примери на реални числа, които не са представими с изчислима функция.
Въпреки това, множеството от изчислимите реални числа изглежда достатъчно за решаване на практическите проблеми. В повечето случай те се свеждат до някаква последователност от прилагане на елементарни функции върху рационални числа. И тъй като рационалните числа са лесно представими в света на изчислимите функции, а елементарните функции върху реални числа имат своето представяне в т. нар. Тип 2 Теория на Изчислимостта (Type-2 Theory of Effectivity, TTE, [15]), е разумно да се помисли за система за представяне на изчислими реални числа чрез термове, описващи начина за получаване на числото.
Реализации на подобни системи съществуват, въпреки че обикновено задачата, която те решават, е поставена по друг начин, като например “точно пресмятане на реални числа” [9] — като в тези случаи реалното число, което се пресмята, всъщност е представено с програмата, която използва въпросната система. Системата няма контрол върху числата, тя просто ги преобразува в смисъла на машините в TTE. За съжаление обикновено тя е ограничена конструктивно да използва за основа рационални числа и няма пълния потенциал на TTE машини, които биха могли да работят и върху неизчислими реални числа.
Въпросното ограничение изглежда разумно, защото за да се подаде едно реално число на системата, то трябва да бъде получено, а вътрешно за компютъра няма как да се получат неизчислими числа.
И все пак реалните числа биха могли да идват и отвън, например от интерфейса с човек, или от връзка с друга машина от различен тип. Както възможностите на една изчислима функция, работеща релативно някакво множество, не са еднакви с тези на изчислимата спрямо празно множество, така и една TTE машина с произволен вход е по-добра от ограничената до рационална основа.
Системата, представена в този текст, представя реалните числа чрез термове, манипулира ги като такива, и позволява произволен брой оракули, представящи външни реални числа.
Тя има и още едно съществено различие — всички операции в нея са примитивно рекурсивни, което гарантира приключване на всяка операция и демонстрира достатъчността на примитивната рекурсия за преработване на реални числа.
Ще разгледаме теорията, която позволява това; ефективен начин за представяне на термовете, описващи едно изчисление; а също и алгоритмите, реализиращи самите елементарни функции при най-ниска известна сложност. Ще се спрем и на едно разумно примитивно рекурсивно ограничение на въпроса за извеждане на търсено от потребителя свойство.
