Обзорный практикум по содержанию ФГОС к двенадцатой паре 11 класса
«Понятная последовательность шагов» годится, пока алгоритм нужно написать. Чтобы доказать, что для задачи алгоритма нет вовсе, нужно точно знать, что такое алгоритм. Такие уточнения появились в 1930-х: машина Тьюринга (1936), машина Поста, рекурсивные функции, позже — нормальные алгорифмы Маркова. Все они оказались равносильны.
Строка — состояние, столбец — символ под головкой, в клетке — команда: что записать, куда сдвинуть, в какое состояние перейти.
| 0 | 1 | λ | |
|---|---|---|---|
| q1 | 1 R q1 | 0 R q1 | λ N q0 |
Эта машина идёт вправо, меняя 0 на 1 и 1 на 0, и останавливается на
первой пустой клетке: 1011 → 0100. Что делать на
такте, решают только состояние и символ под головкой.
Пиши столбиком по такту: состояние, номер клетки, что видим, команда. Такт — одна выполненная команда, последняя, переводящая в q0, тоже считается. Останавливает машину только q0, а не пустая клетка.
Длинное слово по тактам не пройти. Прогони машину на 1, 2 и 3 символах: если каждый новый символ добавляет одно и то же число тактов a, то тактов a·n + b. Обычно a — это число проходов по слову.
По одной команде в строке: состояние, что видим, что пишем, сдвиг, новое состояние. Стрелка и комментарий после # — по желанию.
q1 1 -> 1 R q1 q1 λ -> 1 N q0
Эта программа дописывает единицу к ряду единиц. Пустая клетка — λ или _. Частые приёмы: «дойти до конца слова» — команда, которая переписывает символ сам в себя со сдвигом R в том же состоянии; «запомнить символ» — перейти в своё состояние для каждого символа.
Универсальная машина Тьюринга получает на ленте описание другой машины и её входное слово и делает то же, что та, — прообраз компьютера, где программа хранится в памяти рядом с данными. Тезис Чёрча—Тьюринга: всё, что вычислимо по алгоритму в интуитивном смысле, вычислимо на машине Тьюринга. Это не теорема: «интуитивный алгоритм» строго не определён, поэтому тезис нельзя доказать — его можно только опровергнуть, а этого не случилось.
Обзорный практикум по содержанию ФГОС к двенадцатой паре 11 класса
«Понятная последовательность шагов» годится, пока алгоритм нужно написать. Чтобы доказать, что для задачи алгоритма нет вовсе, нужно точно знать, что такое алгоритм. Такие уточнения появились в 1930-х: машина Тьюринга (1936), машина Поста, рекурсивные функции, позже — нормальные алгорифмы Маркова. Все они оказались равносильны.
Строка — состояние, столбец — символ под головкой, в клетке — команда: что записать, куда сдвинуть, в какое состояние перейти.
| 0 | 1 | λ | |
|---|---|---|---|
| q1 | 1 R q1 | 0 R q1 | λ N q0 |
Эта машина идёт вправо, меняя 0 на 1 и 1 на 0, и останавливается на
первой пустой клетке: 1011 → 0100. Что делать на
такте, решают только состояние и символ под головкой.
Пиши столбиком по такту: состояние, номер клетки, что видим, команда. Такт — одна выполненная команда, последняя, переводящая в q0, тоже считается. Останавливает машину только q0, а не пустая клетка.
Длинное слово по тактам не пройти. Прогони машину на 1, 2 и 3 символах: если каждый новый символ добавляет одно и то же число тактов a, то тактов a·n + b. Обычно a — это число проходов по слову.
По одной команде в строке: состояние, что видим, что пишем, сдвиг, новое состояние. Стрелка и комментарий после # — по желанию.
q1 1 -> 1 R q1 q1 λ -> 1 N q0
Эта программа дописывает единицу к ряду единиц. Пустая клетка — λ или _. Частые приёмы: «дойти до конца слова» — команда, которая переписывает символ сам в себя со сдвигом R в том же состоянии; «запомнить символ» — перейти в своё состояние для каждого символа.
Универсальная машина Тьюринга получает на ленте описание другой машины и её входное слово и делает то же, что та, — прообраз компьютера, где программа хранится в памяти рядом с данными. Тезис Чёрча—Тьюринга: всё, что вычислимо по алгоритму в интуитивном смысле, вычислимо на машине Тьюринга. Это не теорема: «интуитивный алгоритм» строго не определён, поэтому тезис нельзя доказать — его можно только опровергнуть, а этого не случилось.