Обчислювана функція

Обч́ислювана фу́нкція (англ. computable function) — основний об'єкт вивчення теорії обчислень. Обчислюваною функцією $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ називають таку функцію, результат якої може бути отримано за допомогою деякого ефективного процесу[1]. Це поняття дозволяє при формулюванні алгоритмів не спиратися на конкретні реалізації обчислювальних машин, а зосередитися на загальних алгоритмічних принципах.

Існують різні формальні способи конкретизувати, як саме має бути реалізовано цей процес. Це може бути зроблено за допомогою наступних систем:

машина Тьюрінга
μ-рекурсивні функції
Лямбда-числення
Машина Поста
Машина з нескінченними регістрами

Хоча всі ці моделі працюють по-різному, множина задач, які може бути розв'язано за їх допомогою — одна й та сама. Це пов'язано з тим, що будь-яку з цих машин можна змоделювати за допомогою будь-якої з інших.

Алгоритм, що обраховує значення функції, в загальному виді має такі властивості:

Він має скінченну довжину
Якщо $f(n)$ є визначеним для деякого $n$ , то алгоритм, отримавши на вхід $n$ , зупиниться, і видасть $f(n)$
Якщо $f(n)$ не визначене для даного $n$ , то алгоритм, отримавши на вхід $n$ , ніколи не зупиниться.[2]

Часто множину $\mathbb {N}$ обмежують її підмножиною {0, 1}. Таким чином, фактично, алгоритм працює з ланцюжком бітів.

Універсальні обчислювані функції

Універсальною обчислюваною функцією називається функція, що інтерпретує поданий на вхід алгоритм і дані до нього. Формально можна визначити її як функцію $U:\mathbb {N} *\mathbb {N} \rightarrow \mathbb {N} ,$ таку, що для будь-якої обчислюваної функції $f:\mathbb {N} \rightarrow \mathbb {N}$ знайдеться таке p, що $U(p,x)=f(x)$ . На практиці, будь-який компілятор, що перетворює запис алгоритму на деякій мові програмування на результат обчислень цього алгоритму, є такою функцією.[3]

Обчислювані множини

Обчислювана множина, це така множина, для якої існує обчислювана функція, що за скінченне число кроків може визначити, чи входить число, що подане їй на вхід до цієї множини, чи ні. Ця функція називається характеристичною функцією множини.[2]

Наприклад, множина парних чисел є обчислюваною. Для будь-якого натурального числа у двійковому вигляді, якщо його останній розряд дорівнює нулю, це число парне.

Необчислювані функції

Множина програм, які можна записати у вигляді алгоритмів скінченної довжини за допомогою деякого фіксованого алфавіту — зліченна, в той час, як множина функцій $f:\mathbb {N} *\mathbb {N} \rightarrow \mathbb {N}$ — незліченна. Через це, існує множина функцій, що є необчислюваними, і потужність множини таких функцій більша, ніж потужність множини обчислюваних функцій.[4]

Як приклад такої функції можна навести проблему зупинки — неможливо побудувати програму, що приймала б на вхід будь-який алгоритм і вхідні дані до нього, і визначала б, чи зупиниться колись його виконання, чи ні.

Примітки

Математическая логика. Вычислимые функции (рос.)
Н. К. Верещагин, А. Шень ВЫЧИСЛИМЫЕ ФУНКЦИИ (рос.)
Вычислимые функции. Перечислимые и разрешимые множества(рос.)
Математическая логика и теория алгоритмов Архівовано 13 жовтня 2017 у Wayback Machine. (рос.)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Математическая логика. Вычислимые функции (рос.)

[book1-2] Н. К. Верещагин, А. Шень ВЫЧИСЛИМЫЕ ФУНКЦИИ (рос.)

[3] Вычислимые функции. Перечислимые и разрешимые множества(рос.)

[4] Математическая логика и теория алгоритмов Архівовано 13 жовтня 2017 у Wayback Machine. (рос.)