ПОНЯТТЯ АЛГОРИТМУ ТА МОЖЛИВОСТІ РОЗВ'ЯЗАННЯ ТЕОРІЇ

Використання поняття алгоритму в математиці засноване на інтуїтивному уявленні про алгоритм і тезі Черча.

Інтуїтивне визначення алгоритму.

Алгоритм (алгорифм) - це тонне припис, яке задає обчислювальний чи інший процес, що починається з довільного вихідного даного {з деякої сукупності можливих для даного алгоритму вихідних даних) і спрямований на отримання повністю визначається цим вихідним даним результату.

Алгоритмами є, наприклад, відомі з початкової школи правила додавання, віднімання, множення і ділення стовпчиком.

Можливі уточнення поняття алгоритму практично виявляються звуженням інтуїтивного поняття алгоритму. До таких уточненими поняттями відноситься поняття алгоритму, засноване на понятті машини Тьюринга, або нормальні алгоритми Маркова. Ці два поняття мають точні визначення і, як з'ясувалося, є еквівалентними між собою. Теза Черча постулює еквівалентність інтуїтивного і точного визначень алгоритму.

Теза Черча. Інтуїтивне поняття алгоритму еквівалентно точному поняттю алгоритму.

Теза Черча не може бути строго доведений, тому що в його формулюванні бере участь неточне поняття інтуїтивне поняття алгоритму. Ця теза є природно-науковим фактом, що підтверджується досвідом, накопиченим в математиці за всю її історію. Всі відомі в математиці приклади алгоритмів задовольняють йому. На понятті алгоритму засноване поняття можливості розв'язання формальної теорії.

Визначення. Формальна теорія називається вирішуваною, якщо існує алгоритм, який для будь-якої формули даної теорії визначає, чи є вона теоремою або НЕ-теоремою.

Прикладом можливо розв'язати теорії є формальна система ( JP). Для неї дозволяє алгоритм був наведений вище. Прикладом нерозв'язною теорії є логіка предикатів першого порядку. Для логіки висловлювань справедлива теорема Е. Посту.

Теорема Е. Посту. Формула логіки висловлювань доказова тоді і тільки тоді, коли вона є тотожно-істинною формулою.

Це означає, що логіка висловлювань, яка входить складовою частиною в логіку предикатів, є вирішуваною теорією.

 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >