Міністерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра комп’ютерних наук
Контрольна робота 7
з дисципліни “Теорія алгоритмів”

Довести алгоритмічну розв'язність лінійного диференціяльного рівняння з постійними коефіцієнтами.
Традиційний метод доведення існування алгоритму – використання машини Тюрінга і “методу доведення від супротивного”, щоб показати існування рекурсивності (рекурсивної функції). Оскільки для простого диференціального рівняння числовий алгоритм можна побудувати за рекурсивною формулою:
,
тому таким чином можна довести алгоритмічну розв’язність лінійних диференціальних рівнянь. При цьому вважається, що складніший процесор можна побудувати на базі машини Тюрінга, що дозволяє використати даний факт для доведення.
Довести алгоритмічну розв'язність задачі знаходження найбільшого спільного дільника цілих чисел.
Використовуючи машину Тюрінга та “метод доведення від супротивного” можна показати існування рекурсивності, тобто рекурсивної функції. Оскільки для розв’язку задачі знаходження найбільшого спільного дільника алгоритм використовує попередньо обчислені значення, тобто є рекурсивним, то таким чином можна довести алгоритмічну розв’язність задачі знаходження найбільшого спільного дільника (НСД).