Привіт!
Цей проект створений з метою продемонструвати роботу таких алгоритмів як Машина Тьюрінга, нормальні алгоритми Маркова та системи Поста.
Дізнатися більшеМашина Тьюрінга
Основна ідея, що лежить в основі машини Тьюрінга, дуже проста. Машина Тьюрінга — це абстрактна машина (автомат), що працює зі стрічкою, що складається із окремих комірок, в яких записано символи.
Приклад 1: МТ, яка обчислює функцію x + y
Приклад 2: МТ, яка обчислює функцію x - y
Приклад 3: МТ, яка обчислює функцію x ∙ y
Приклад 4: МТ, яка обчислює функцію sg(x)
Приклад 5: МТ, яка слово x переводить у слово x#x
Приклад 6: МТ, яка обчислює функцію x2
Нормальні алгоритми Маркова
Основна ідея алгоритму — це система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.
Приклад 1: НА для функції x + y
Приклад 2: НА для функції x - y
Приклад 3: НА для функції x / 2
Приклад 4: НА для функції x ∙ y
Приклад 5: НА для функції x2
Приклад 6: НА, який слово x переводить у слово xx
Системи Поста
Це абстрактна, але дуже проста обчислювальна машина. Машина Поста може здійснювати різні обчислення, для чого потрібно задати початковий стан каретки і програму, яка виконає ці обчислення.
Приклад 1: СП для функції x + y
Приклад 2: СП для функції x - y
Приклад 3: СП, яка обчислює предикат
"х парне"
Приклад 4: СП для функції x / 2
Приклад 5: СП для функції |x - y|
Приклад 6: СП для функції x mod 3