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

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

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

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

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

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

Успенский В.А. Машина поста — М.: Наука, 1988. — 96 c.
ISBN 5-02-013735-9
Скачать (прямая ссылка): mashinaposta1988.djvu
Предыдущая << 1 .. 30 31 32 33 34 35 < 36 > 37 .. 38 >> Следующая

году. Сам он доказал существование ал^ горитма в ряде частных случаев.
Туэ особо выделил случаи, когда во всякой разрешенной замене один из
членов - пустое слово, и, таким образом, всякая раз* решенная замена
состоит в том, что можно в любое место имеющегося слова вставить
указанное в замене слово или вычеркнуть его*
93
Например, вставляя и вычеркивая слова АБ и БА, можно из слова АБББА
получить БАБАБ. Попытайтесь построить требуемый алгоритм для вставок и
вычеркиваний АБ и Б А, то есть для такого списка разрешенных замен:
(Уже этот простейший пример важен для раздела алгебры, называемого
"теория групп".)
Для любого набора разрешенных вставок-вычеркиваний алгоритм,
устанавливающий, можно ли переделать одно слово в другое, существует.
Показал это советский математик С. И. Адян в 1966 году.
Элементарная геометрия. Мы не имеем здесь возможности дать детальное
определение, что такое элементарная геометрия в строгом смысле,
уточняемом с помощью математической логики. Постараемся, однако, дать
приблизительное описание. Исходными понятиями элементарной геометрии
служат точки, прямые, плоскости, отрезки, окружности, сферы, отношения
"лежать на", "лежать между", "быть конгруэнтными" и т. п. Допускается
образование новых понятий - но без использования многоточий и оборота "и
так далее" (в этом пункте строгое математико-логическое представление
об элементарной геометрии расходится с расплывчатым традиционным).
Например, понятие треугольника принадлежит элементарной геометрии: ведь
треугольник можно определить как такие три отрезка AiA2, Л3Л4, А5А6, что
А2 - A3, At, - Л5, А6 - Ai. А вот общее понятие ломаной не принадлежит
элементарной геометрии, потому что в его определении участвуют многоточие
и слова "и так далее": ломаная - это набор отрезков А^А2, Л3Л4, ...
(здесь многоточие!), Ап-и Ап, таких, что А2 - Аз, Л4 = Л5 и т. д.
Проблема. Дано: утверждение элементарной геометрии. Т р е -
б у е т с я: проверить, истинно ли оно.
Искомый алгоритм: существует.
Существование алгоритма было, по существу, установлено Тарским в 40-е
годы нашего века. Оно достаточно просто вытекает из существования того
алгоритма Тарского, о котором говорилось ранее. Связь проблем алгебры и
геометрии была открыта уже давно (аналитическая геометрия), естественно,
что она распространилась и на алгоритмические проблемы.
Результат Тарского выглядит, и действительно является, крайне сильным и
даже парадоксальным. Оказывается, существует весьма обширная область
классической математики (именно - элементарная геометрия), о которой
традиционно считается, что она требует тонкого интеллекта и уж никак не
сводится к тупым подсчетам, и в то же время имеется алгоритм, который
может проверять истинность теорем этой области (а если нужно, то и искать
их доказательства). Утешиться можно лишь тем, что алгоритм Тарского не
является реальным: он требует неслыханно большого времени для Своего
осуществления.
Полезно представить себе: насколько "близко" начинаются те геометрические
утверждения, для которых, несмотря на существование общего алгоритма,
сейчас неизвестна их истинность или ложность,
АБ
4-
БА
пустое слово
пустое слово
04
Вот один наглядный пример. Возьмем двенадцать круглых банок одинакового
диаметра (равного, скажем, 10 см). Мы хотим упаковать их, поставив
стоймя, в круглую коробку. Это можно сделать, например, так, как показано
на рисунке 1). Однако можно расположить банки и более тесно - так, чтобы
понадобилась коробка меньших размеров. Например так, как показано на
рисунке 2-Наконец, упаковка, показанная на рисунке 3, позволяет
использовать еще меньшую коробку. Спрашивается, можно ли найти круглую
коробку еще меньшего диаметра, в которую бы влезли все наши банки? Ответа
на этот вопрос никто не знает, хотя этот ответ
и может быть получен с помощью алгоритма Тарского: надо применить этот
алгоритм к утверждению, что третья упаковка - наилучшая, и посмотреть,
что получится в результате. ДА или НЕТ. Однако этот способ нереален,
поскольку для получения результата работы алгоритма требуется
астрономически большое время.
Распознавание свойств программ. Предположим, что мы ра* ботаем в
Вычислительном Центре. В этом центре имеется замечательная Вычислительная
Машина. Она может производить вычисления по любой программе р, написанной
на неком Языке Программирования, то есть по входному данному т находить
результат р(т) программы р (если, конечно, он определен).
Программы можно перенумеровать (например, в алфавитном порядке, ведь
каждую программу можно считать словом в символах Языка Программирования),
составив Библиотеку всех программ:
Р1" Р2" Рз> * • • у Рп, • • ¦
Лучше всего иметь дело с такими программами р, которые при любом входном
данном /л дают результат р(т). Такова, например, стандартная программа
для вычисления функции у = = т2 -f- 5т - 6. К сожалению, встречаются и
такие программы, которые при некоторых значениях входного данного никогда
Предыдущая << 1 .. 30 31 32 33 34 35 < 36 > 37 .. 38 >> Следующая