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

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

Сам факт существовании невычислимых функций тривиален из теоретико-множественных соображений - класс всех функций NN равномощен множеству вещественных чисел и, следовательно, несчетен, класс же вычислимых функций, как мы убедились выше - счетен. Однако, в реальной жизни программист средней квалификации, однако, не часто задумывается о том, существует в действительности ли алгоритм решения поставленных перед ним задач, особенно - нетривиальных, нестандартных. Такое пренебрежение математической стороной дела можно было бы понять, если бы, как в некоторых областях математики, примеры неразрешимых задач были бы специально выращенными контрпримерами-"монстрами", не имеющих отношения к реальной вычислительной практике.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• О разложении в ряд Фурье непериодической функции - Приложение интегрального и дифференциального исчисления к решению прикладных задач

  Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f(x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде...

• ПРАВИЛО ЛОПИТАЛЯ - Скалярные и векторные величины, матрицы и функции

  Теорема Коши. Если при соблюдении предположений относительно функций и отношение стремится к некоторому числу при, то тогда к такому же числу будет...

• Элементарные функции - Конформное отображение

  Теория конформных отображений подчинена решению двух основных задач: 1) найти образ области при заданном отображении; 2) найти конформное отображение...

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

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

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

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

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

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

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

  Рассмотрим функцию, определенную на промежутке Пусть. Функция называется непрерывной в точке, если Функция называется Непрерывной слева (справа) в точке,...

• Бесконечные пределы - Свойства функций

  Функция называется Бесконечно малой при (или, или ) если для сколь угодно малого положительного числа найдется такое положительное число (), что для всех...

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

  Используется адаптивная нейро-нечеткая система вывода ANFIS, функционально эквивалентная системе нечеткого вывода Сугено. Вывод осуществляется за два...

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

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

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

  Q(x) - соответствует площади боковой поверхности данного тела от точки А до точки х. Q(x)>х€[a, x]. Q (x+?x)>х€[a, x+?x], тогда ?Q=Q...

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

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

• Целевая функция потребления и моделирование поведения потребителей. Понятие бюджетного множества - Бюджетное множество

  На уровне общества для описания поведения потребителей вводится целевая функция потребления. Целевая функция потребления - функция, выражающая уровень...

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

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

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

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

• Способ усреднения подынтегральной функции - Применение метода Монте-Карло в эконометрическом анализе

  В качестве оценки определенного интеграла принимают , Где n - число испытаний; - возможные значения случайной величины X, распределенной равномерно в...

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

  Выделим случай, когда входной сигнал X ( T ) является элементарной функцией 1( T ). Реакцию системы на воздействие 1( T ) можно компактно: [1] Где...

• Проверка: Исследование функции на экстремум - Методика решения двойственных задач линейного программирования

  Исследуем на экстремум функцию: 1. С помощью необходимого существования экстремума, т. е. из системы Найдем координаты стационарных (критических) точек:...

• ЭКСТРЕМУМ ФУНКЦИИ, ВОЗРАСТАНИЕ (УБЫВАНИЕ) ФУНКЦИЙ - Скалярные и векторные величины, матрицы и функции

  ВОЗРАСТАНИЕ (УБЫВАНИЕ) ФУНКЦИЙ Функция называется Возрастающей на некотором Промежутке , если на этом промежутке большему значению независимой переменной...

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

  ПРОИЗВОДНАЯ, ЕЕ СВОЙСТВА И ГЕОМЕТРИЧЕСКИЙ СМЫСЛ. ДИФФЕРЕНЦИАЛ. ПРОИЗВОДНАЯ ВЫСШИХ ПОРЯДКОВ Если отношение имеет предел при этот предел называют...

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

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

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

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

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

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

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

  Теорема: Непрерывная на сегменте функция интегрируема на этом сегменте. Теорема: Если функция определена и ограничена на сегменте, и если для любого...

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

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

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

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

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

  Современные инженерные задачи оптимизации многокритериальные. Выделяют класс задач многоцелевой или многокритериальной оптимизации (класс МКО-задач). В...

• Выводы, Список литературы - Многокритериальная оптимизация на основе нейросетевой, нечеткой и нейро-нечеткой аппроксимации функции предпочтений лица, принимающего решения

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

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

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