Cтраница 2
Теория вычислимых функций представляет интерес не только в связи с компьютерами; она является одной из центральных областей математической логики. [16]
Для любой вычислимой функции Ъ ( п) при достаточно больших п среди машин с п символами алфавита и п состояниями, останавливающихся на пустом входе, можно найти и такую, которая вычисляет nb ( n), а затем вычитает из этого числа по единице, пока не дойдет до нуля. [17]
Рассмотрим вычислимую функцию / ( ж), не имеющую всюду определенного вычислимого продолжения. [18]
Под интуитивно вычислимой функцией понимается такая функция, для которой существует точное предписание о выполнении в определенном порядке некоторой системы операций для вычисления любого значения этой функции. [19]
Общерекурсивные и регулярно вычислимые функции. [20]
Класс тыорингово вычислимых функций 101 Кодирование 179 Кодовая группа 128 Колмогоров А, Я. [21]
Поскольку графики вычислимых функций арифме-тичны, очевидно, разрешимые и перечислимые множества тоже будут арифметическими. [22]
Не существует регулярно вычислимой функции, которая для формализма ( Z00) была бы разрешающей функцией, связанной с введенной нами нумерацией этого формализма. [23]
Приведите пример тотальной вычислимой функции такой, что ( i) если Фх тотальна, то и ф / ( х) тотальна и ( п) существует неподвижной точки / г, такой, что фп тотальна. [24]
Алгоритма сложность, Вычислимая функция, Машина. [25]
Но и каждая регулярно вычислимая функция тоже является квазирекурсивной. [26]
Убедиться, что вычислимая функция упражнения 4 § 2 является нормально вычислимой. [27]
Ясно, что конкретная вычислимая функция может быть вычислима многими различными программами; например, каждую программу можно изменить, добавив команды, ни разу не применяемые. Менее очевидно то, что могут быть различные неформальные методы для вычисления конкретной функции, и после формализации они дадут различные программы для одной и той же функции. Позднее мы рассмотрим проблему, состоящую в выяснении того, вычисляют ли две программы одну и ту же функцию. [28]
Пусть f - тотальная одноместная вычислимая функция; тогда существует число / /, такое, ф / ( / 1) фл. [29]
Говоря здесь о вычислимой функции, мы имеем в виду функцию, для которой существует алгоритм ее вычисления. [30]