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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

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

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

Універсальною обчислюваною функцією називається функція, що інтерпретує поданий на вхід алгоритм і дані до нього. Формально можна визначити її як функцію таку, що для будь якої обчислюваної функції знайдеться таке p, що . На практиці, будь-який компілятор, що перетворює запис алгоритму на деякій мові програмування на результат обчислень цього алгоритму, є такою функцією.[3]

Обчислювані множини[ред.ред. код]

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

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

Необчислювані функції[ред.ред. код]

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

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

Примітки[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.