Рекурсивные функции

Рекурсивными функциями называют один частный класс вычислимых функций, который сейчас построим. [c.23]

Совокупность рекурсивных функций будем строить следующим образом непосредственно опишем наиболее простые из них и назовем базовыми-, сопутствующие этим функциям алгоритмы будут наиболее простыми, одношаговыми. Затем опишем три приема, называемых в теории рекурсивных функций операторами, с помощью которых, исходя из рекурсивных функций, можно получать новые, рекурсивные по определению функции. Эти операторы, по существу, будут алгоритмами соединяя их, можно получать новые алгоритмы. Итак, строим класс рекурсивных функций. [c.23]

Итак, рекурсивными называют базовые функции и любые функции, получаемые из них с помощью операторов суперпозиции, рекурсии и минимизации. При этом функции, получаемые без использования оператора минимизации, называют примитивно рекурсивными. Рекурсивные функции, определенные для любых значений аргументов, называют общерекурсивными. Если для некоторых значений аргументов рекурсивная функция не определена, ее называют частично рекурсивной. Построенная выше функция р(х) является частично рекурсивной. [c.25]

Американский математик А. Черч высказал гипотезу о том, что понятием рекурсивной функции исчерпывается понятие вычислимой функции. Эта гипотеза известна под названием тезиса Черча какова бы ни была вычислимая неотрицательная целочисленная функция от неотрицательных целочисленных аргументов, существует тождественно равная ей рекурсивная функция. [c.26]

Можно строить машины Тьюринга, вычисляющие рекурсивные функции. Для примера опишем машину, вычисляющую функцию Цх) = X + 1 — одну из базовых рекурсивных функций. Внешний алфавит будет состоять из двух символов О (пустой символ) и 1. Целое неотрицательное число х будет представляться в виде соответствующего числа следующих друг за другом символов 1. [c.27]

Может показаться, что машины Тьюринга реализуют более широкий класс функций, чем рекурсивные. Но это не так, потому что все слова, составленные из букв внешнего алфавита, можно перенумеровать, предварительно упорядочив их лексикографически, и тем самым установить соответствие между преобразованиями слов, осуществляемыми машинами Тьюринга, и неотрицательными целочисленными функциями неотрицательных целочисленных аргументов. Доказано, что множество этих функций эквивалентно множеству рекурсивных функций. Для машин Тьюринга тем самым устанавливается тезис Тьюринга, эквивалентный тезису Черча любая вычислимая функция вычислима по Тьюрингу. [c.27]

В качестве простого примера рассмотрим нормальный алгоритм вычисления рекурсивной функции 1(д )=х+ 1, кодируя, как и в примере с мащиной Тьюринга, число х соответствующим количеством единиц. Полагая алфавит А состоящим из единственного символа 1 , искомый нормальный алгоритм запишем в виде единственной формулы - .1 . [c.28]

Отметим, что теории рекурсивных функций и машин Тьюринга являются косвенными теориями алгоритмов, тогда как теория нормальных алгоритмов Маркова имеет дело с алгоритмами непосредственно. [c.28]

Лисп (LIST Pro essing — обработка списков) — алгоритмический язык, имеющий средства для обработки списков, основным назначением которого является описание рекурсивных функций символьных выражений. Подробнее об этом см. в [5, 6 ). — Прим. перев. [c.530]

Мы часто пользуемся рекурсивной функцией, называемой SUBSET, для определения, все ли атомы, указанные в списке фрагментов, имеются в молекуле. В языке лисп эта функция настолько компактна и так хорошо показывает характер рекурсии, что мы воспроизведем ее здесь [c.532]

Функции пользователя и рекурсивные функции Функции пользователя в Math ad задаются в виде [c.51]

Math ad допускает внутри тела функции пользователя задавать обращение к самой этой функции. Это означает возможность задания рекурсивных функций, порой заметно упрощающих реализацию различных алгоритмов. Функция if также позволяет создавать рекурсивные алгоритмы [c.51]

Прежде всего будем считать, что как аргументами, так и значениями рекурсивных функций являются неотрицательные целые (натуральные) числа. На самом деле это предположение не сужает класс рассматриваемых функций, поскольку доказано, что произвольные числовые данные можно арифметизировать, т. е. представить в виде комбинаций натуральных чисел. [c.23]

Теория алгоритмов оказала существенное влияние на развитие ЭВМ и практику программирования. В теории алгоритмов были предугаданы основные концепции, заложенные в аппаратуру и языки профаммирования ЭВМ. Упоминаемые выше главные алгоритмические модели математически эквивалентны но на практике они существенно различаются сложностными эффектами, возникающими при реализации алгоритмов, и породили разные направления в программировании. Так, микропрограммирование строится на идеях машин Тьюринга, структурное профаммирование заимствовало свои конструкции из теории рекурсивных функций, языки символьной обработки информации (Рефал, Пролог) берут начало от нормальных алгоритмов Маркова и систем Поста. [c.40]

Справочник химика 21

Химия и химическая технология