Математические Функции

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

Теорема о существовании невычислимых функций: Множество вычислимых функций является строгим подмножеством для множества функций. Иными словами, среди функций существуют невычислимые.

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

Теорема: Любую вычислительную функцию можно реализовать машиной Тьюринга.

       Для машины Тьюринга входной алфавит и множество состояний являются конечными, следовательно такая машина описывается набором команд. Если записать их подряд с разделителем, тогда каждая машина Тьюринга однозначно задается одним длинным словом. При этом любую машину Тьюринга описываемым конечным словом, множество всех машин Тьюринга – множество таких слов, которые являются счетными.

       Множество вычислимых функций, описываемых некоторой машиной Тьюринга, является счетным. Множество всех алгоритмов как множество всех функций – несчетно. Исходя из этого, имеются невычислимые функции, иными словами множество вычислимых функций является подмножеством для множества функций.

       Счетное множество называют вычислимым, если его индикатором является вычислимая функция. Дополнение вычислимого множества также вычислимо. Счетное множество является полу разрешимым, если существует автомат, который для каждого элемента множества корректно вычисляет индикатор: для принадлежащих множеству дает значение единица, для не принадлежащих – ноль или зависает.

Дополнительные избранные разделы