Главная

Контакты

Случайная статья

• Автоматизация
• Антропология
• Археология
• Архитектура
• Биология
• Ботаника
• Бухгалтерия
• Военная наука
• Генетика
• География
• Геология
• Демография
• Деревообработка
• Журналистика
• Зоология
• Изобретательство
• Информатика
• Искусство
• История
• Кинематография
• Компьютеризация
• Косметика
• Кулинария
• Культура
• Лексикология
• Лингвистика
• Литература
• Логика
• Маркетинг
• Математика
• Материаловедение
• Медицина
• Менеджмент
• Металлургия
• Метрология
• Механика
• Музыка
• Науковедение
• Образование
• Охрана Труда
• Педагогика
• Полиграфия
• Политология
• Право
• Предпринимательство
• Приборостроение
• Программирование
• Производство
• Промышленность
• Психология
• Радиосвязь
• Религия
• Риторика
• Социология
• Спорт
• Стандартизация
• Статистика
• Строительство
• Технологии
• Торговля
• Транспорт
• Фармакология
• Физика
• Физиология
• Философия
• Финансы
• Химия
• Хозяйство
• Черчение
• Экология
• Экономика
• Электроника
• Электротехника
• Энергетика

Частично-рекурсивные функции. Базисные функции: нулевая, следования, проекции. Операторы суперпозиции и примитивной рекурсии. Примитивно-рекурсивные функции. Оператор минимизации. Частично-рекурсивные функции. Тотально-рекурсивные функции. Примеры примити

Частично-рекурсивные функции

Базисные функции: нулевая, следования, проекции. Операторы суперпозиции и примитивной рекурсии. Примитивно-рекурсивные функции. Оператор минимизации. Частично-рекурсивные функции. Тотально-рекурсивные функции. Примеры примитивно (частично, тотально)-рекурсивных функций. Тезис Черча

Рекурсия - один из основных приемов программирования.

Рекурсивная функция (от лат. recursio – возвращение) – это числовая функция  числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения , , ….

При разработке машин Тьюринга было отмечено, что команда, которую выполняет машина в последующий момент автоматного времени зависит от содержимого ячейки и внутреннего состояния в предыдущий момент времени. Так реализуется автоматная память. В теории рекурсивных функций, которая считается исторически первой формализацией понятия алгоритма, применяется нумерация слов в произвольном алфавите натуральными числами (N), и любой алгоритм сводится к вычислению некоторой функции при целочисленных значениях аргументов.

Функция вычислима, если существует такой алгоритм, то есть пошаговая процедура «от простого к сложному», которая по входному набору переменных вычисляет значение функции, если этот входной набор принадлежит к области определения функции, или выдает сообщение, что входной набор не принадлежит к области определения функции.

Функция полувычислима,если при задании входного набора, не принадлежащего области определения функции, алгоритм не заканчивает работу («зацикливается»). Теорию вычислимости разрабатывал А. Черч. Идея теории состоит в выделении элементарных вычислимых функций (которые «интуитивно вычислимы») – то есть базиса и разработке средств получения из этих элементарных вычислимых функций более сложных функций за конечное число шагов. Полученные таким образом функции тоже будут вычислимы.