Теорема о параметризации., Универсальные функции - Рекурсивные функции

Любую часть x1,x2,...,xn входных значений можно породить программно, более того - существует алгоритм, который генерирует по x1,x2,...,xn текст соответствующей программы. Более формально, существует тотальная вычислимая функция s такая, что

e N x NNY YM (S(e, x)(y)=E(x, y) )

Замечание.

Выше, при доказательстве теоремы, мы полагали n=1 и m=1; общий случай получается тривиальным обощением приведенного построения.

Для перехода к формулировке теоремы в терминах нумераций, упомянутой ранее, положите F(x, y)= E(x, y) для универсальной функции класса и некоторого e; по определению F вычислима - следовательно, такой геделевский номер найдется.

Универсальные функции

Сколько функций вычисляет компьютер? С одной стороны, как и любое другое автоматическое устройство, компьютер исполняет Единственную функцию, преобразуя некоторый условный вход в некоторый условный выход. С другой - и в этом отличительная особенность компьютера как универсального преобразователя - он вычисляет Все возможные вычислимые функции. Ответ этого нехитрого парадокса - в программируемости компьютера. Единственная его функция - в интерпретации части поступающих данных как программ и исполнении их на значениях, которые уже и мы считаем данными для наших программ (но, для компьютера являющихся просто еще одной частью входных данных).

Назовем Универсальной, для одноместных вычислимых функций, двухместную функцию u, u(e, x)=E(x); аналогично вводиться понятие функции u(n), универсальной для n-местных вычислимых функций. Теоретическое обоснование понятию компьютера как универсального интерпретатора дает

Похожие статьи

• Теорема Клини о нормальной форме - Рекурсивные функции

  Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e, x ( E(x)=p ( k [T(e, x,k)])). В частности, e, x ( E(x) k T(e,...

• Теория алгоритмов. Основные результаты, Программы как данные - Рекурсивные функции

  Вместо предисловия . Сверх-идеей любой научной теории можно считать перевод знания из сферы подсознательного, интуитивногов осознанную, точную и...

• Теорема об универсальной функции - Рекурсивные функции

  Для любого n, nN, универсальная функция u(n) вычислима. Доказательство. При доказательстве мы можем ограничиться случаем N=1. Действительно, программу,...

• Теорема о параметризации - Рекурсивные функции

  Одно и то же выражение может порождать несколько разных функций, от разного числа аргументов. Так, обычное арифметическое выражение xK можно считать...

• Синтаксис и семантика. Теорема Райса - Рекурсивные функции

  Попробуем теперь проанализировать круг проблем, неразрешимость которых доказана в предыдущем пункте. Общим для них является то, что по кодам, т. е....

• Принцип сходимости, Предел функции. Теорема Гейне - Свойства функций

  Рассмотрим вопрос о существовании пределов последовательностей концевых точек бесконечной системы промежутков, вложенных друг в друга. Лемма Кантора ....

• Перечислимость. - Рекурсивные функции

  В предыдущем упражнении мы показали, что операции алгебры логики не выводят за пределы разрешимых предикатов. Но полный язык математической логики, как...

• Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции

  Если А - эффективное множество, то Для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn...

• Неразрешимость - Рекурсивные функции

  Сейчас же займемся более важной задачей - определением принципиальных границ вычислимости. Если теоремы о параметризации, универсальнойфункциии...

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

  Еще одним подходом к проблеме формализации алгоритма являются, так называемые, рекурсивные функции. Исторически этот подход возник первым, поэтому в...

• Сжатие графика вдоль оси ох, Отражение графика от оси ох, Отражение графика от оси оу, Построение графика функции, содержащий знак модуля, Обратная функция, теорема об обратной функции - Математика в современном мире

  Ответ: y=f(kx) получается из Графика функции f(x) сжатием его вдоль оси ох в k раз, если k>1 и растяжением в 1 деленную на k раз, если k>0 но меньше 1....

• ФУНКЦИИ, Основные понятия - Свойства функций

  Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...

• Кодирование программ - Рекурсивные функции

  (Эффективной) Нумерацией , или Перечислением множества А назовем Произвольное эффективное отображение f :N A, f(N)=A; таким образом, мы допускаем, что в...

• Теоремы о пределах, По &;nbsp;теореме&;nbsp; о связи &;nbsp;предела&;nbsp; и бесконечно малой функции: - Действительные числа. Тригонометрические функции числового аргумента. Логарифмы. Частные случаи решения тригонометрических уравнений

  Теорема 1. Предел постоянной равен самой постоянной. . Доказательство. f(x)=с, докажем, что . Возьмем произвольное e>0. В качестве d можно взять любое...

• Неразрешимость - методы доказательства, Диагонализация - Рекурсивные функции

  Основными методами при доказательстве теорем о не существовании алгоритмовявляются - прямой метод Диагонализации, восходящий к "диагональному"...

• Действия над комплексными числами в алгебраической форме, Четность и нечетность функции, Монотонность и периодичность функции, Предел функции в точке - Действительные числа. Тригонометрические функции числового аргумента. Логарифмы. Частные случаи решения тригонометрических уравнений

  Сложение, вычитание, умножение комплексных чисел в алгебраической форме производят по правилам соответствующих действий над многочленами. Четность и...

• 7. ПРЕДЕЛ ФУНКЦИИ, ПОНЯТИЕ ФУНКЦИИ, ЧИСЛОВАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ. ПРЕДЕЛ ЧИСЛОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. ПРЕДЕЛ ФУНКЦИИ - Скалярные и векторные величины, матрицы и функции

  ПОНЯТИЕ ФУНКЦИИ Если некоторому множеству значений поставлено по определенному правилу F во взаимнооднозначное соответствие некоторое множество, то тогда...

• Теорема Пенлеве - Условия Фукса и теорема Пенлеве

  Все приведенные выше исследования велись в предположении, что мы изучаем поведение интеграла в области изменения z, при котором w(z) принимает вполне...

• Необходимое и достаточное условие интегрируемости, Равномерно непрерывные функции - Определенные интегралы

  Теорема: Для того, чтобы ограниченная на сегменте функция была интегрируемой на этом сегменте, необходимо и достаточно, чтобы для любого нашлось такое...

• Дискретные случайные величины. Распределение случайных величин. Примеры, Функция распределения случайной величины. Свойства. Примеры - Теория вероятности

  Опытом называется всякое осуществление определенных условий и действий, при которых наблюдается изучаемое случайное явление. Опыты можно характеризовать...

• Следствия теоремы, Послесловие к доказательству - Об одной теореме теории чисел

  Не существует ЦЕЛЫХ чисел, для которых выполняется равенство (1). При четных значениях показателя степени уравнение вида (1) идентично как для...

• Сводимость - Рекурсивные функции

  Помимо построения контрпримеров, в математических доказательствах часто используют метод сведения, который на практике мы часто формулируем в виде...

• Нейросетевая аппроксимация функции ценности - Использование нейродинамики для моделирования производственных процессов предприятия

  Табличное представление цен действий и состояний задачи имеет естественные ограничения по масштабируемости задачи на большую размерность. В дискретных...

• Тригонометрические функции половинного аргумента, Обратные тригонометрические функции и их свойства, Частные случаи решения тригонометрических уравнений - Действительные числа. Тригонометрические функции числового аргумента. Логарифмы. Частные случаи решения тригонометрических уравнений

  Логарифм алгебраический угол число Формулы двойного аргумента Sin 2x=2sin xЧcos x Cos 2x=cosІx-sinІx Cos 2x=1-2sinІx Cos 2x=2cosІx-1 Обратные...

• Теоремы Ферма, Ролля, Лагранжа и Коши

  Введение В данном реферате рассматриваются теоремы Ферма, Ролля, Лагранжа и Коши. "Теорема - высказывание, нравственность которого установлена при помощи...

• Функции нескольких переменных. Предел и непрерывность. Частные производные. - Методы решения системы линейных уравнений

  Пусть u = f(x, y) - функция, определенная в области w. Рассмотрим точку М(х, у) О w и некоторое направление l, определяемое направляющими косинусами Cosa...

• Функции и ее свойства - Методы решения системы линейных уравнений

  В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую...

• Свойства числовой функции (четность, нечетность, периодичность), График функции, построение, Смещение графиков вдоль осей ординат, Растяжение графика вдоль оси оу - Математика в современном мире

  Ответ: Функция f называется четной если для любого х из ее области определения f(-x)=f(x) График четной функции симметричен относительно оси ординат....

• Непрерывность композиции, Точки разрыва - Свойства функций

  Пусть задана функция, со значениями в, и на множестве определена функция со значениями в. Тогда для любого можно вычислить, на можно определить функцию...

• Рождение проблемы - Великая теорема Ферма

  Жизненно важным, поворотным пунктом в развитии западной математики стал 1453 год, когда турки разграбили Константинополь. За прежние годы рукописи,...

• Методы построения функций принадлежности нечетких множеств - Нечеткая логика

  В приведенных выше примерах использованы прямые методы, когда эксперт или просто задает для любого x?E значение ?A(x), или определяет функцию...

• Особенности нейросетевой аппроксимации функции предпочтения ЛПР, Особенности аппроксимации функции предпочтений ЛПР с помощью аппарата нечеткой логики - Многокритериальная оптимизация на основе нейросетевой, нечеткой и нейро-нечеткой аппроксимации функции предпочтений лица, принимающего решения

  Аппроксимация функции предпочтения ЛПР нейронными сетями имеет в работе ту особенность, что процесс обучения нейронных сетей происходит в условиях малой...

• Уход в абстракцию - Великая теорема Ферма

  После работ Эрнста Куммера надежды найти доказательство ослабли, как никогда прежде. Кроме того, в математике начали развиваться различные новые области....

• Запечатанные конверты - Великая теорема Ферма

  После прогресса, достигнутого благодаря работам Софи Жермен, Французская Академия Наук установила серию премий, включая золотую медаль и 3000 франков,...

• Месье Леблан - Великая теорема Ферма

  К началу XIX века за Великой теоремой Ферма установилась устойчивая репутация самой трудной проблемы в теории чисел. После прорыва, осуществленного...

• Математик-циклоп - Великая теорема Ферма

  Создание математики -- занятие мучительное и таинственное. Объект доказательства часто бывает ясен, но путь к доказательству теряется в тумане, и...

• Позор математики - Великая теорема Ферма

  С тех пор, как я еще мальчиком впервые столкнулся с Великой теоремой Ферма, она стала моим увлечением на всю жизнь, -- вспоминает Эндрю Уайлс, и его...

• Функции распределения вероятностей для параметров, описываемых обобщенными интервальными оценками - Метод представления знаний в интеллектуальных системах поддержки экспертных решений

  Пусть Dl, r() соответственно левые (правые) границы интервалов I, отвечающих на криволинейной трапеции ОИО значениям 0< < 1. Тогда интересующая нас...

• Создатель Великой проблемы - Великая теорема Ферма

  Пьер де Ферма родился 20 августа 1601 года в городе Бомон-де-Ломань на юго-западе Франции. Его отец, Доминик Ферма, был состоятельным торговцем кожей,...

• Введение, История теоремы - Великая теорема Ферма

  Она заинтересовала меня тем, что на вид очень простая и казалось бы, решить ее может каждый школьник, но найти ее решение на протяжении 358 лет пытались...

Теорема о параметризации., Универсальные функции - Рекурсивные функции

Предыдущая | Следующая