Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Таранина И.В. "Гражданский процесс в схемах " (Юриспруденция)

Смоленский М.Б. "Адвокатская деятельность и адвокатура российской федерации" (Юриспруденция)
Реклама

Машина поста - Успенский В.А.

Успенский В.А. Машина поста — М.: Наука, 1988. — 96 c.
ISBN 5-02-013735-9
Скачать (прямая ссылка): mashinaposta1988.djvu
Предыдущая << 1 .. 17 18 19 20 21 22 < 23 > 24 25 26 27 28 29 .. 38 >> Следующая

двух случаев относительно разложения л имеет место в действительности.
Для каждого из этих общих способов вычисления числа ?" существует
соответствующая программа, осуществляющая вычисление ?п на машине Поста -
для первого общего способа (?" = 1) - программа
1. ?2 4. <= 5
2. =>¦ 3 5. V6
Л 6. <=7
3. / У 7. V 8
\1 8. стоп,
а для второго общего способа (?" == 0)-программа
/4
2. ?' 4. стоп.
\3
Мы можем с уверенностью утверждать, что одна из выписанных двух программ
отвечает предъявляемым требованиям, но современное состояние наших знаний
не позволяет нам сказать, какая именно.
Существование соответствующего единого способа вычисления было известным
в примерах-1, 2 и 4 и
65
оставалось неизвестным в примере 3. Построены примеры, в которых такого
способа заведомо не может существовать, но они слишком сложны, чтобы их
можно было здесь привести.
§ 3. Машина Поста и алгоритмы
Понятие единого способа вычисления, общего для целого класса возможных
исходных данных, является одним из важнейших понятий математики - как
"теоретической", так и "бытовой". Именно на нем основано, например,
обучение математике в начальной школе. Многочисленные примеры на четыре
действия с многозначными числами не преследуют ведь цель научить
складывать, вычитать, умножать и делить именно те числа, которые
встречаются в этих примерах. Цель этих упражнений- отработать способы
сложения, вычитания, умножения и деления столбиком, имея, конечно, в
виду, что эти способы применимы к любым упорядоченным парам чисел, а не
только к тем, которые встречаются в задачнике. Когда говорят, что ученик
умеет складывать, разумеют под этим не то, что он для любой пары чисел
найдет рано или поздно их сумму, а то, что он владеет общим способом
сложения.
Столь важное понятие нуждается, конечно, в специальном термине для своего
наименования: в качестве такого термина употребляется слово "алгоритм"
(другое написание: "алгорифм"). Мы можем сказать теперь, что в примерах
1, 2 и 4 существуют алгоритмы (хотя мы и не знаем, каков он для примера
4), в примере 3 алгоритм неизвестен (и неизвестно даже, существует ли
он). Как уже отмечалось, известны случаи, когда требуемого алгоритма
заведомо не существует.
Хотя понятие алгоритма часто встречается в практике и в науке, оно не
всегда замечается: само слово "алгоритм" все еще недостаточно популярно;
общеизвестным является лишь словосочетание "алгоритм Евклида", служащее
для обозначения одного из алгоритмов для нахождения наибольшего общего
делителя. Мы нередко оказываемся тем самым в положении молье-рова
мещанина во дворянстве, уже в зрелом возрасте впервые узнавшего, что он
всю жизнь говорил прозой. Как бы то ни было, теперь мы знаем, что в школе
нас учили именно алгоритмам. (Популярная экскурсия в область теории
алгоритмов предпринята в статье
66
В. А. Успенского, A. JL Семенова "Решимые и нереши-мые алгоритмические
проблемы (см. с. 90-96 настоящей книги).)
Предполагается, что для каждого алгоритма указана некоторая совокупность,
называемая областью его возможных исходных данных и состоящая из всех
объектов (например, чисел или кортежей), к которым рассматриваемый
алгоритм имеет смысл пытаться применять. В применении к какому-либо из
своих возможных исходных данных алгоритм может как давать результат (в
этом случае говорят, что алгоритм применйм к этому исходному данному и
перерабатывает его в результат), так и не давать результата (в этом
случае говорят, что алгоритм неприменим к этому исходному данному). Так,
для алгоритма вычитания столбиком исходными данными служат упорядоченные
пары чисел, а алгоритм применим только к тем из них, у которых второй
член не больше первого. Вряд ли целесообразно считать, что для этого
алгоритма класс возможных исходных данных состоит лишь из пар <а, 6>, у
которых а^- Ь. Ведь возможно пытаться произвести вычитание второго числа
из первого и для пары
(1244444445444445, 1244444454444445);
просто в этом случае мы не получим никакого результата.
Посмотрим, как понятие алгоритма связано с машиной Поста. Рассмотрим
такие программы машины Поста, которые в применении к любому числу либо
вовсе не дают результативной остановки, либо дают в качестве результата
снова число (т. е. если происходит результативная остановка, то на ленте
оказывается записанным некоторое число и только оно). Каждая такая
программ ма задает следующий алгоритм, областью возможных ис* ходных
данных которого служит совокупность всех целых неотрицательных чисел и
все результаты суть также числа: надо взять исходное число, записать его
на ленте машины Поста, поставить каретку против самой левой из отмеченных
секций, пустить машину в ход согласно рассматриваемой программе,
дождаться результативной остановки и прочесть число, которое после этой
остановки окажется записанным на ленте.
Фиксируем теперь какое-либо число k и рассмотрим такие программы, которые
в применении к любому числовому кортежу длины k либо вовсе не дают
Предыдущая << 1 .. 17 18 19 20 21 22 < 23 > 24 25 26 27 28 29 .. 38 >> Следующая