Issn 2072-0297 Молодой учёный Международный научный журнал Выходит еженедельно №3 (137) / 2017 р е д а к ц и о н н а я к о л л е г и я : Главный редактор
жүктеу/скачать 9,13 Mb. Pdf көрінісі
|
moluch 137 ch1
| .
№ 3 (137) . Январь 2017 г. 2 Математика Возьмем формальный язык L, основные символы которого будут интерпретированы так, чтобы на языке L удалось выразить отношения, согласно которым модель замещает объект. Можно считать L языком узкого исчисления предикатов, логические константы которого составляют сигнатуру Σ . Через ( ) L T A обозначим элементарную теорию объекта A, т. е. множество предложений, истинных в A [1]. Вообще нас могут интересовать не все свойства даже среди тех, которые выразимы на языке L. Поэтому естественно говорить о подмножестве В множества предложений языка L, выражающих интересующие исследователя свойства. Далее уточним форму отношения моделирования между объектами А и Б путем использования сведения проблемы истинности предложений для Б к проблеме истинности предложений из А. В теории алгоритмов существуют различные классы сводимостей. Принципиально они отличаются по выбору одного или нескольких объектов для принятия решений, а также по тому факту, что информация может быть точно получена или может быть когда-либо получена, но в данный момент времени это неизвестно. Главное в процессе сведения — эффективность, или алгоритмичность. Например, pm-сводимость (частичная) в применении выглядит следующим образом. Мы имеем возможность делать утверждения о свойствах Б на основании утверждений о свойствах А как конструктивное существование языка М и эффективного способа F перевода предложений P из В в предложения F(P) языка М таким образом, что ( ) ( ) ( ) P B P T Б F P T A ∈ ⇒ ∈ ⇔ ∈ Важным здесь является не только эффективность F, но и невысокая алгоритмическая сложность F. Эта эквивалентность вообще говоря, может выполняться не на всех высказываниях, а на некоторой части, что соответствует неполному соответствию модели объекту. Если построенная теория Т(Б) изучаемого объекта достаточно проста и допускает непосредственное изучение, тогда объектом А можно считать систему, для которой Т(А)=Т(Б) и тогда проблема адекватности модели — это проблема адекватности теории. Если заданы теории объектов А и Б, то существование или несуществование сводимости является математической проблемой, решение которой в положительном смысле обосновывает отношение моделирования объектом А объекта Б в плане свойств из В, обосновывает с той достоверностью, с которой заданные теории адекватны своим объектам. Итак, концепция заключается в рассмотрении отношения моделирования А — модель Б как частичного отношения вида (*) или более общего между теориями этих объектов. В математической логике одной из основных проблем является массовая проблема разрешимости для формальных теорий, т. е. проблема существования алгоритма, позволяющего по любому предложению языка определить, является ли оно истинным или принадлежит ли оно теории. Работы 30-х годов двадцатого века показали, что не существует разрешающего алгоритма для УИП, с тех пор было доказано много теорем об алгоритмической неразрешимости, причем большинство — путем сведения известной проблемы к рассматриваемой. Метод сводимости стал широко распространенным. Это и привело к изучению сводимостей как таковых. Сводимости стали мощным средством классификации множеств по сложности (степеням неразрешимости). Хорошим введением в эту область служит книга [3]. Введем необходимые формализмы. Множества и функции заданы на { } 0,1,2, ω = … . Всюду определенные функции обозначаются через f,g,h, частичные — α , β . n D — каноническая нумерация конечных множеств, x W — стандартная нумерация вычислимо перечислительных множеств (области определения частичных функций, задаваемых машиной Тьюринга с номером х). Среди сводимостей по разрешимости выделяютс наиболее общая тьюрингова и так называемые табличные сводимости. Говорят, что А tt-сводится к В, если существует алгоритм, который по любому жүктеу/скачать 9,13 Mb. Достарыңызбен бөлісу:
|