Please enable JavaScript.
Coggle requires JavaScript to display documents.
Алгоритм §31,32 - Coggle Diagram
Алгоритм
§31,32
Нормальные алгоритмы Маркова
Преобразует слово в другое
Задается алфавитом, системой подстановок
Не связан с аппаратным обеспечением
Равносилен с машинами Поста и Тьюринга
Машина Тьюринга
Каретка
ввод/вывод данных
Бесконечная лента
внешняя память
в двоичной си
разбита на ячейки
Программируемый автомат
посылает команды каретке
работает по программе
без человека
имеет 3 состояния
Универсальный исполнитель
Модель вычислений
Память
Язык
Процессор
Ввод данных
Вывод данных
Моделирует работу другого исполнителя
Свойства
Обрабатывает дискретный объект, строя промежуточные
Объект на последнем шаге-результат работы
Получает дискретный объект
Если выполнение не заканчивается, то результата нет
Машина Поста
Лента
разбита на ячейки
бесконечна
может содержать/не содержать метку
Каретка
Программируемый аппарат
Алфавит из 2 цифр
НЕ таблица
6 каманд
Строки нумеруются
Функции
Невычисляемые
Алгоритмически неразрешаемая задача
Проблема эквивалентности
Вычисляемые
Любым универсальным исполнителем
Алгоритмически разрешаемая задача
Разными алгоритмами