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

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

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

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

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

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

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

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

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

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

Обчисленні множини

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

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

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

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

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

Формальні мови

У теорії обчисленності в інформатиці, поширине поняття формальної мови. Абетка це довільна множина. Слово на цій абетці це скінченна послідовність символів з абетки; один і той самий символ можна використовувати більше ніж один раз. Наприклад, двійкові рядки це слова на абетці {0, 1} . Мова це підмножина з множини всіх слів на затвердженій абетці. Наприклад, множина всіх двійкових рядків, що містять рівно 3 одиниці це мова над двійковою абеткою.

Ключова властивість формальної мови це рівень складності потрібний, щоб вирішити чи певне слово належить цій мові. Потрібно мати деяку систему кодування, що обчесленна функція могла прийняти довільне слово на вхід. Мову називають обчисленною (синоніми: рекурсивною, розв'язною), якщо існує обчисленна функція f така, що для кожного слова w над абеткою, f(w) = 1 якщо слово належить цій мові і f(w) = 0 якщо слово не належить цій мові. Отже мова обчисленна, якщо існує процедура, яка здатна правильно сказати чи належать мові довільні слова.

Мова обчисленно переліченна (синоніми: рекурсивно переліченна, напіврозв'язна), якщо існує обчисленна функція f така, що f(w) визначене тоді і лише тоді, коли слово w присутнє в мові.