Обчисленна функція
З Вікіпедії, безкоштовно encyclopedia
Обчисле́нна фу́нкція (англ. computable function) — основний об'єкт вивчення теорії обчислень. Обчисленною функцією називають таку функцію, результат якої може бути отримано за допомогою деякого ефективного процесу[1]. Це поняття дозволяє при формулюванні алгоритмів не спиратися на конкретні реалізації обчислювальних машин, а зосередитися на загальних алгоритмічних принципах.
Існують різні формальні способи конкретизувати, як саме має бути реалізовано цей процес. Це може бути зроблено за допомогою наступних систем:
- машина Тьюрінга
- μ-рекурсивні функції
- Лямбда-числення
- Машина Поста
- Машина з нескінченними регістрами
Хоча всі ці моделі працюють по-різному, множина задач, які може бути розв'язано за їх допомогою — одна й та сама. Це пов'язано з тим, що будь-яку з цих машин можна змоделювати за допомогою будь-якої з інших.
Алгоритм, що обраховує значення функції, в загальному виді має такі властивості:
- Він має скінченну довжину
- Якщо
є визначеним для деякого
, то алгоритм, отримавши на вхід
, зупиниться, і видасть
- Якщо
не визначене для даного
, то алгоритм, отримавши на вхід
, ніколи не зупиниться.[2]
Часто множину обмежують її підмножиною {0, 1}. Таким чином, фактично, алгоритм працює з ланцюжком бітів.