markov_teorija_algorifmov (522344), страница 73

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 73)

В частности, если имеется единичное исчисление со свойством Р, то для всякого алфавита с числом букв, ббльшим 3, проблема распознавания свойства Р неразреишма. Подробное доказательство этой теоремы читатель найдет в монографии [2! на с. 345 — 368. В применении к наследственным свойствам теорема 7.1 может быть значительно упрощена. В самом деле, допустим, что Р— наследственное свойство ассоциативных исчислений и что имеется как исчисление Й со свойством Р, так и исчис- ление 8) без него.

Тогда единичное ассоциативное исчисление в алфавите а, определяемое системой соотношений [ а4-+, включаемо в Й [6.3! и потому в силу наследственности свой- ства Р оно обладает этим свойством. С другой стороны, исчис- ление 8), не обладающее свойством Р, не включаемо ни в ка- кое ассоциативное исчисление с этим свойством (опять-таки в силу наследственности Р). Следовательно, выполнены усло- вия третьего утверждения теоремы 7.1, и это утверждение при- менимо. Мы получаем, таким образом, следующую теорему: 7.2.

Пусть Р— наследственное свойство ассоциативных исчислений. Если имеется как исчисление со свойством Р, так и исчисление без него, то для всякого алфавита с числом букв, ббльшим 3, проблема распознавания свойства Р неразрешима. Теорема 7.2 может быть применена к наследственным свой- ствам, рассмотренным выше. Это дает следующий результат: 7.3. Для всякого алфавита, содержащего более трех букв, неразрешимы проблемы распознавания единичноспш, конеч- ности, полугрупповости, включаемости в групповое исчисление, разрешимости, абелевости. В самом деле, всякое единичное исчисление обладает пере- численными шестью наследственными свойствами.

С другой стороны, имеется неконечное исчисление (исчисление в алфа- вите а, определяемое пустой системой соотношений), которое тем самым не единично; имеется неполугрупповое исчисле- ние (нсчисление в алфавите а, определяемое системой, состоя- щей из единственного соотношения аа4-нг), которое тем самым не включаемо в групповое исчисление [6.10); имеется нераз- решимое исчисление [9 58.4.4! и, наконец, имеется неабелево исчисление (исчисление в алфавите аб, определяемое пустой системой соотношений).

К групповости ассоциативных исчислений теорема 7.2 ие применима, так как это свойство не является наследст- венным. Тем ие менее имеем 7.4. Для всякого алфавита, содержащего более трех букв, проблема распознавания групповости неразрешима. В самом деле, всякое единичное ассоциативное исчисление является, как нетрудно видеть, групповым.

С другой сто- роны, имеется исчисление, ие включаемое ни в какое группо- вое. Следовательно, к групповости применимо третье утверж- дение теоремы 7.1. 8. В заключение рассмотрим проблему изоморфии ассоциа- тивньсх исчислений, состоящую в разыскании алгорифма, Ззз ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП !ГЛ.

Уп! позволяющего распознавать изоморфию любых двух ассоциативных исчислений в данных алфавитах. Эта проблема следующим образом может быть„поставлена как нормальная массовая проблема. Пусть А и Б †произвольн алфавиты. Требуется построить нормальный алгорифм, применимый ко всякому слову вида Й"гс В"„ где Й и «1 †ассоциативн исчисления в алфавитах А и Б соответственно, н перерабатывающий такое слово в пустое тогда и только тогда, когда Й изоморфно 6.

Эту проблему мы будем называть проблемой изоморфии для алфавитов А и Б. Имеет место следующее утверждение (А. А. М а р к о в 181; подробное изложение см. в 121 на с. 369 — 370). 8.1. Если хотя бы один из алфавитов А, Б содержит более трех букв, то проблема изоморфии для этих алфавитов неразрешима. В самом деле, допустим для определенности, что Б содержит более трех букв. Построим единичное исчисление Й в А.

Согласно 6.5 ассоциативное исчисление е) в Б единично тогда и только тогда, когда Й изоморфно е). Но проблема распознавания единичности для алфавита Б неразрешима, откуда легко и выводится интересующее нас утверждение 8.1, 9. Интересуясь лишь иивариантными свойствами ассоциативных исчислений, можно наряду с изображениями ассоциативных исчислений ввести нх записи таким образом, чтобы в записи исчисления содержалась полная информация о нем самом. Теорема 5.6 показывает, что в рассматриваемом случае нам важно знать не сам алфавит исчисления, а лишь число составляющих его букв.

Изображение же ассоциативного исчисления может быть закодировано словом в двухбуквенном алфавите способом, аналогичным тому, который мы в 9 45 применяли к нормальным алгорифмам. Запись исчисления и будет состоять из этих двух компонент. Утверждение 8.1, теоретико-множественно говоря, показывает, что множество пар записей изоморфных ассоциативных исчислений неразрешимо. Возникает вопрос, что же можно сказать положительное об этом множестве. Оказывается, что это множество перечислимо.

Именно, справедлива следующая теорема (Н. М. Н а г о р н ы й 141): 9.1. Может быть построен а,ггорифм, применимый к паре записей асса|(иативных исчислений Й и 1О тогда и только тогда, когда Й изоморфно !В, и перерабатывающий $ 61! ПРОБЛЕМЪ| РАСПОЗНАВАНИЯ СВОЙСТВ ИСЧИСЛЕНИЙ 397 в этом случае эту пару записей в запись изоморфизма Й на х). Примененный для доказательства этого утверждения метод состоит в следующем.

Рассматриваются некоторого простого типа конечные списки слов. Для любых двух ассоциативных исчислений определяется понятие их Т-изоморфизма таким образом, что Т-изоморфизм исчислений Й и |В есть список указанного типа и для,любого списка этого типа можно алгорифмически проверить, является ли он Т-изоморфизмом исчислений Й и «1. При этом оказывается, что Т-изоморфизм Й и |Б существует тогда и только тогда, когда Й нзоморфно 93. Таким образом, перечисляя списки этого типа друг за другом и производя соответствующую проверку, мы найдем Т-изоморфизм Й и В, если он существует, и тогда построим |по нему изоморфизм Й на В. Если же Й не изоморфно 1Б, то процесс перебора рассматриваемых списков никогда не прекратится.

Этим же приемом можно воспользоваться в других сходных ситуациях. Так, с его помощью можно доказатьперечислимость (неразрешимых в силу приведенных выше результатов) множеств единичных, абелевых н групповых ассоциативных исчислений. Теоретико-множественная терминология, которой мы воспользовались в этом пункте, разумеется, использована здесь не по существу, а из соображений удобства.

Приведенное рассмотрение вполне укладывается в рамки конструктивных представлений. 1О. Проблематику, рассмотренную в п. 7, естественно пытаться перенести на групповые ассоциативные исчисления, которые с точки зрения алгебраиста суть способы задания некоторых специальных («конечно определенныхь) групп. Для таких исчислений результаты, аналогичные теореме 7.1, были получены С. И. А д я н о м [11, 121 и М. О. Р а б ин ам П1. ГЛАВА 1Х АЛГОРИФМЫ И МАТЕМАТИЧЕСКИЙ АНАЛИЗ » бэ) констнуктииныи числа и Функции ззэ множественным подходом читатель найдет, например, в фундаментальной статье Н.

А. Шанина [21») и в книге Б. А. Кушнера [Н. Вопрос об эффективности основных понятий и конструкций математического анализа, как известно, привлекал к себе внимание ряда крупнейших математиков практически с самого начала исследований по теоретико-множествеиному обоснованию анализа. Однако обсуждение этой проблематики в точных терминах стало по-настоящему возможным только после того, как было сформулировано точное понятие алгорифма.

Любопытно, что понятие вычислимого действительного числа фигурирует уже в названии первой, основополагающей работы А. М. Т ьюр и н га [1), в которой было произведено то уточнение общего понятия алгорифма, которое впоследствии получило название «машины Тьюринга». С тех пор средствами теории алгорифмов были прояснены многие принципиальные вопросы оснований математического анализа. Было выявлено также конструктивное содержание ряда фундаментальных результатов анализа, лежащих в основе многих методов, представляющих практическую ценность. Были проведены важные исследования по выявлению исходных данных, достаточных для фактического нахождения значений тех или иных искомых величин.

Исследовалась сложностная зависимость между значениями исходных и результирующих величин. Наконец, была разработана и осуществлена подробная программа построения математического анализа на базе теории алгорифмов и конструктивной логики (так называемый «конструктивный анализ»), не апеллирующая к концепциям теории множеств. Особое значение эти исследования приобретают в связи с потребностями общей теории вычислительных методов.

К сожалению, результаты проведенных исследований практически неизвестны вне узкого круга специалистов. Включая в данную монографию ряд фрагментов, проясняющих значение точного понятия алгорифма для математического анализа и вычислительной математики, мы хотели бы привлечь внимание читателя к описанному кругу вопросов. Подробное изложение понятий и методов конструктивного анализа, а также сопоставление их с классическим, теоретико- 5 62.

Конструктивные действительные числа и конструктивные действительные функции В этом параграфе мы покажем, как на базе понятия алгорифма (и без какого-либо обращения к представлениям теории множеств) могут быть определены основные понятия конструктивного математического анализа — понятие конструктивного (вычислнмого) действительного числа и понятие конструктивной (вычислимой) действительной функции.

1. Обозначим через Р трехбуквениый алфавит [ —,«', в котором мы в 5 1 условились строить рациональные числа. Пусть Р+ — какое-либо двухбуквенное расширение этого алфавита. В качестве „произвольных" нормальных алгорифмов над Р мы будем брать нормальные алгорифмы в этом фиксированном алфавите Р+.

Характеристики

Список файлов книги