Машины Тьюринга

Машины Тьюринга являются одними из первых аппаратов в исследованиях по теории алгоритмов. Понятие «машин Тьюринга» было введено английским математиком и логиком Аланом Тьюрингом

Про машину Тьюринга, пожалуй, должен знать любой школьник, мечтающий стать программистом. Ведь именно её считают основой основ теории алгоритмов. Несмотря на её довольно сложное формальное определение, идея в принципе проста. Чтобы понять её, будет достаточно пройти курс «Машины Тьюринга».

Курс «Машины Тьюринга» включает в себя вводную часть, которая познакомит вас с основными разновидностями Машин Тьюринга, их практическим применением и их особенностями. Основная часть курса содержит в себе больше практической работы, связанной с программированием машин Тьюринга различными способами, а также с работой на симуляторах машин Тьюринга.

После прохождения курса вы будете знать основные термины и понятиями, которые могут встретиться в работе с машинами Тьюринга, а также получите навыки программирования таких машин.

Так как курс «Машины Тьюринга» не только теоретический, но и практический: лекции сопровождаются большим количеством наглядных примеров, упрощающих восприятие материала. Курс состоит из следующий основных тем:

• Машина Тьюринга

• Зоопарк машин Тьюринга

• Универсальная машина Тьюринга

• Устройство универсальной машины Тьюринга

• Недетерминированная машина Тьюринга

• Машина Тьюринга с несколькими лентами

• Машина Тьюринга с несколькими дорожками

• Квантовая машина Тьюринга

• Нейронная машина Тьюринга

• Вероятностная машина Тьюринга

• Машина Поста-Тьюринга

• Только читающая машина Тьюринга

• Только читающая машина Тьюринга с только правым сдвигом

• Симметричная машина Тьюринга

• Машина Тьюринга, которая всегда останавливается

• Однозначная машина Тьюринга

• Предельный ординал Омега

• Машина Зенона

• Формальные системы

• Теоремы Гёделя о неполноте

• Диагонализация Кантора

• Проблема останова машины Тьюринга

• Тьюринг-полнота

• Тезис Чёрча-Тьюринга

• Унарное и бинарное кодирование информации для машины Тьюринга

• Языки программирования для машин Тьюринга

• Общие принципы программирования машин Тьюринга

• Программирование машин Тьюринга: инкремент

• Программирование машин Тьюринга: сложение

• Программирование машин Тьюринга: вычитание

• Программирование машины Поста

• Симуляторы машин Тьюринга

В целом, ничего кроме желания учиться, не требуется — вся необходимая информация есть в видео курса, а главными целями курса являются:

1. Изучение понятия вычислений

2. Понимание суть машин Тьюринга

3. Получение информации о вариантах машин Тьюринга

4. Получение навыка программирования машин Тьюринга

Обучение на курсе будет особенно полезно действующим и будущим программистам, системным архитекторам; студентам и аспирантам технических вузов, а также всем интересующимся информатикой, кибернетикой и цифровыми технологиями