Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Статья: Структура рекурсивных m-степеней в полях

Название: Структура рекурсивных m-степеней в полях
Раздел: Рефераты по математике
Тип: статья Добавлен 18:40:07 24 марта 2007 Похожие работы
Просмотров: 32 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

И.В. Ашаев, Омский государственный университет, кафедра математической логики

Обычная теория алгоритмов изучает вычислимость над конструктивными объектами, которые допускают эффективное кодирование натуральными числами. При этом многие процессы в математике, имеющие интуитивно алгоритмическую природу, но работающие в неконструктивных областях (например, в вещественных числах), не являются алгоритмами с формальной точки зрения. Новый подход, именуемый далее - обобщенная вычислимость, трактует алгоритм как конечный, дискретный, целенаправленный и детерминированный процесс, но работающий с элементами некоторой фиксированной алгебраической системы сигнатуры . При этом элементарными шагами обобщенного алгоритма являются вычисления значений констант, функций и предикатов системы (см. [1,2,5,6]).

В качестве формализации обобщенной вычислимости будем использовать машину над списочной надстройкой из [1]. Эта машина представляет из себя конечный связный ориентированный граф с узлами четырех типов: входной узел, выходные, вычислительные и ветвления. Узел ветвления имеет две выходные дуги, с ним ассоциирована атомарная формула сигнатуры , от истинности которой зависит выбор одной из этих дуг в процессе вычислений. Узлы остальных типов (кроме выходных) имеют одну выходную дугу, с такими узлами ассоциированы термы сигнатуры . На входной узел машины подается набор элементов системы , который передается от узла к узлу по дугам графа; в узлах элементы изменяются под действием ассоциированных термов. При достижении выходного узла работа машины прекращается, полученные элементы системы выдаются как результат. Подробности см. в [1].

Имея машину, можно определить понятие функции, вычислимой в системе . Однако при этом полученный класс вычислимых функций будет достаточно мал (обоснование см. в [1,2]), поэтому предложенная формализация нуждается в улучшении. Один из возможных способов решения данной проблемы - усилить определение машины, разрешив машины со счетчиками, стеками и массивами (см. обзор [2]). Другой подход состоит в использовании списочной надстройки, введенной в [3]. Пусть A - множество, определим множество , состоящее из всевозможных списков (конечных последовательностей) элементов A, включая пустой список . Положим по индукции L0 = A, , . Множество HL(A) называется cписочным расширением множества A. Списочная надстройка системы есть система , где . Константа интерпретируется как пустой список, операции и есть взятие первого элемента списка x и удаление из списка x первого элемента соответственно, .

Функция называется вычислимой в системе , если f вычисляется некоторой машиной, примененной к списочной надстройке . Множество назовем рекурсивным в , если его характеристическая функция вычислима в . Множество рекурсивно перечислимо (р.п.) в , если оно является областью определения вычислимой функции, X - выходное в системе , если оно есть множество значений некоторой вычислимой функции. В общем случае классы р.п. и выходных множеств различны (примеры см. в [1]).В дальнейшем, если ясно, о какой системе идет речь, слова "в системе ", будем опускать.

Справедлив аналог теоремы Поста: множество рекурсивно X и его дополнение рекурсивно перечислимы. Доказательство в [1].

Вычислимость в системе совпадает с классической вычислимостью, определяемой с помощью машины Тьюринга.

Лемма 1. Всякое рекурсивно перечислимое множество определяется дизъюнкцией вида

(1)

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

Это вариант леммы Энгелера для вычислимости в списочной надстройке, ее доказательство можно найти в [1]. Из леммы 1 и теоремы Поста следует, что если - бескванторная формула, то множество рекурсивно.

Определение 2. Множество X m сводится к Y (), если существует всюду определенная вычислимая функция , что

Множества X и Y m-эквивалентны (), если

m-степень множества X есть множество .

m-степень рекурсивна (р.п.), если она содержит хотя бы одно рекурсивное (р.п.) множество.

Так же, как и в классической теории алгоритмов, доказывается следующая лемма (см., например, [4]).

Лемма 3. Справедливы следующие утверждения:

1) отношение рефлексивно и транзитивно;

2) рекурсивная m-степень состоит только из рекурсивных множеств;

3) .

Известно [4], что в арифметике существует только три рекурсивные m-степени: , и степень всех остальных рекурсивных множеств. В данной работе описывается структура рекурсивных m-степеней в полях с трансцендентными элементами.

Итак, пусть - поле, рассматриваемое в сигнатуре - его простое подполе. Предполагаем, что содержит трансцендентные над элементы.

Лемма 4. Множество рекурсивно одно из множеств X или [] состоит из конечного набора алгебраических над элементов и вместе с каждым элементом содержит все алгебраически сопряженные с ним (т.е. корни того же самого минимального многочлена).

Доказательство. Пусть , - минимальные многочлены для элементов X, причем вместе с каждым ai множество X содержит и все остальные корни fi(x). Тогда - рекурсивное отношение.

Пусть рекурсивно над '. Тогда X и [] определяются рекурсивными дизъюнкциями бескванторных формул и вида (1).

Случай 1. Одна из есть конечная конъюнкция неравенств вида . Такой будут удовлетворять все элементы поля , за исключением конечного числа алгебраических элементов, т.е. X есть множество требуемого вида.

Случай 2. Все содержат хотя бы одно равенство вида t(x) = 0. Тогда множество X не содержит ни одного трансцендентного элемента, следовательно, существует , которой удовлетворяют трансцендентные элементы, но тогда содержит только одни неравенства . Таким образом, мы приходим к случаю 1 с заменой X на его дополнение.

Лемма 5. Если функция вычислима в системе , то для любых принадлежит подсистеме системы , порожденной элементами .

Доказательство. См. в [1].

Теорема 6. Пусть , рекурсивные множества. Тогда каждое поле содержит одно из полей .

Доказательство. Пусть . Тогда найдется вычислимая функция f(x), что . По лемме 5, f(ai), есть значение некоторого терма сигнатуры т.е. рациональной функции с коэффициентами из поля . Значит, , т.е. .

Обратно, пусть , , т.е. ti(ai) = bi для некоторого набора рациональных функций . Тогда посредством вычислимой функции

Непосредственно из определения следует, что для любого конечного Y.

Следствие 7. Справедливы следующие утверждения:

1) если X конечное рекурсивное множество и , то любое конечное рекурсивное Y сводится к X;

2) для рекурсивного X имеем: и ;

3) среди рекурсивных m-степеней существует наибольшая, это степень множества X из п.2.

Доказательство. 1. Следует из теоремы.

2. По лемме 4 можно считать, что множество X конечно, а конечно. Тогда существует a . Если и f сводящая функция, то , но по лемме 5 f(a) есть значение некоторой рациональной функции с коэффициентами из , т.е. . Обратно, если существует , то X и [] сводятся друг к другу посредством функции

3. Пусть X конечное рекурсивное множество и . Пусть Y произвольное рекурсивное. Если Y конечно, то по п.1. Если Y коконечно, то по лемме 3, но . Таким образом, упорядочение рекурсивных m-степеней в поле имеет вид:

Если в поле достаточно много алгебраических элементов, например, если алгебраически замкнуто, то существует бесконечное число рекурсивных m-степеней.

Следствие 8. Пусть поле алгебраически замкнутое характеристики 0, a рекурсивная m-степень, и не является наибольшей среди рекурсивных. Тогда:

1) существует счетное число рекурсивных степеней, несравнимых с a;

2) существует счетное число попарно несравнимых степеней , таких, что ;

3) существует счетное число попарно несравнимых степеней , таких, что ;

4) порядок на рекурсивных m-степенях плотный.

Доказательство. Пункты 1) - 3) следуют из теоремы 6 и свойств алгебраических расширений полей. Для доказательства 4) рассмотрим рекурсивные множества . Можно считать, что и , причем X и Y не содержат элементов из . Тогда , где , , но .

Список литературы

Ашаев И.В., Беляев В.Я., Мясников А.Г. Подходы к теории обобщенной вычислимости // Алгебра и логика. 32. N 4 (1993). С. 349-386.

Кфури А. Дж., Столбоушкин А.П., Ужичин П. Некоторые открытые вопросы в теории схем программ и динамических логик // УМН. 1989. Т.44. Вып.1 (265). С. 35-55.

Гончаров С.С., Свириденко Д.И. -программирование// Логико-математические проблемы МОЗ (Вычислительные системы. Вып. 107). Новосибирск, 1985. С. 3-29.

Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М: Мир, 1972.

Blum L., Shub M., Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines //Bull. Amer. Math. Soc. 1989. V.21. N1. P.1-46.

Friedman H. Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory //Logic Colloquium'69 (R.O. Gandy and C.E.M. Yates, eds). NorthHolland, 1971. Р. 361-390.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:57:23 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:54:51 24 ноября 2015

Работы, похожие на Статья: Структура рекурсивных m-степеней в полях

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151188)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru