1. Поняття та терміни

1.1. Задачі. Ми розглядатимемо функції вигляду , де А і В — деякі алфавіти. Саме цей клас функцій виникає, коли ми ці­кавимось функціями, які можна ефективно обчислювати. Наприклад, функцію піднесення до квадрату у множині невід'ємних цілих чисел з обчислювальної точки зору природньо трактувати як функцію із мно­жини {0,1,..., 9}^* в себе. Слід лише домовитись, як бути з десятковими словами, що починаються цифрою 0. їх можна утотожнити з невід'є­мними цілими десятковими числами, що отримуються після відкидання перших нулів. А можна вважати, що функція відображає слова, які не є десятковим записом натурального числа, у 0. Якщо функція двомісна, на зразок додавання натуральних чисел, то для розділення аргументів зручно ввести в алфавіт новий спеціальний символ, як от #.

Задача обчислення функції  полягає у знаходженні для вказаного слова  значення функції . Ми будемо описувати задачі обчислення наступним чином:

Задано:         . 

Обчислити: .

Втім, коли нам не буде настільки важливо, в якому алфавіті і як саме кодуються аргументи та значення функції, ми допускатимемо і менш формальні описи задач на кшталт

Задано:      .

          Обчислити:   .

Іноді задачу у вищеозначеному сенсі ми будемо називати масовою. Конкретне задане  називатимемо індивідуальною задачею. Зна­чення  будемо називати розв'язком індивідуальної задачі . Масо­ву задачу можна вважати нескінченним набором індивідуальних задач.

Нехай — множина слів у алфавіті А^*. Часто L називають мовою. Задача розпізнавання мови L полягає у визначенні, належить задане слово  цій мові, чи ні:

Задано:              .

Розпізнати:      ?

Наприклад,

Задано:           .

Розпізнати: чи є  повним квадратом ?

Індивідуальною задачею є будь-яке задання слова w. Розв'язком ін­дивідуальної задачі є відповідь "так" чи "ні", яку прийнято кодувати символами 1 та 0 відповідно.

Ще один різновид задачі, який нам буде траплятися, називається задачею пошуку елемента із заданою властивістю. Нехай алфавіт А не містить символу # і {#})^*. Для кожного заданого  задача полягає або у знаходженні хоча б одного  такого, що #, або у констатації, що елемента  з такою властивістю немає:

Задано:         .

Знайти:           таке, що #.

Індивідуальною задачею є довільно задане слово , а її розв'язком е або відповідне , або відповідь "не існує", яку зручно кодувати сим­волом #. Наприклад,

Задано:         .

Знайти:           таке, що .

Ми ввели три типи задач — обчислення, розпізнавання та пошуку. Насправді, в обчислювальному відношенні всі вони рівносильні між собою — кожну задачу одного типу можна переформулювати як задачу будь-якого з двох інших типів.

Так, задача розпізнавання мови  є ні чим іншим, як зада­чею обчислення її характеристичної функції , що набуває значення 1 на аргументах з  і лише на них. Задачу обчи­слення функції  легко подати як задачу пошуку, взявши #, де  — множина слів у алфавіті #. Нарешті, кожну задачу пошуку можна звести до деякої задачі розпізна­вання .