Запитання для самоперевірки:
- Що називається машиною Тюрінга?
- Що називається нормальним алгоритмом Маркова?
- Яка функція називається обчислювальною за Тюрінгом?
- Сформулюйте гіпотезу Тюрінга.
- Яка функція називається нормально обчислювальною?
- Сформулюйте принцип нормалізації Маркова.
- Сформулюйте теорему про зв’язки між собою всіх формальних уточнень поняття алгоритму.