ПРЕДИКАТОВ КЛАССИФИКАЦИИ

ПРЕДИКАТОВ КЛАССИФИКАЦИИ
ПРЕДИКА́ТОВ КЛАССИФИКА́ЦИИ
(иерархии предикатов) – методы приписывания предикатам (в формализованных исчислениях логики и математики) различных "степеней конструктивности", базирующиеся на идеях и аппарате теории алгоритмов и теории рекурсивных функций и предикатов и играющие существ. роль в метаматематических (см. Метатеория) исследованиях. Идеи эти обнаруживают близкое родство с известными принципами классификации множеств и функций, предложенными Р. Бэром, Э. Борелем, Ш. Ж. де ла Валле Пуссеном, Η. Η. Лузиным и др. математиками. Примером классификаций такого рода могут служить иерархии, предложенные С. К. Клини и. А. Мостовским. П. к. Клини – Мостовского позволяет также приписывать различные степени конструктивности арифметическим множествам и функциям и строить иерархии логич. систем. Принцип П. к., разработанный амер. математиком Э. Постом (1944), исходит из разбиения систем множеств, предикатов, св-в, отношений и т.п. посредством рефлексивного, симметричного и транзитивного отношения: "А рекурсивно относительно В и В рекурсивно относительно А" на классы эквивалентности, наз. "степенями (рекурсивной) неразрешимости", причем транзитивное отношение "А рекурсивно относительно В" для представителей классов естеств. образом упорядочивает (см. Порядка отношение) эти степени неразрешимости. Как показали сов. математик А. А. Мучник и амер. математик Р. Фридберг (1956), предикаты (множества), входящие в классификацию Поста, не образуют линейно упорядоченной иерархии. Идея упорядочения классов эквивалентности лежит и в основе предложенной сов. математиком Ю. Т. Медведевым классификации массовых проблем по "степеням трудности" (см. Сводимость).
Лит.: Медведев Ю. Т., Степени трудности массовых проблем, "Докл. АН СССР", 1955, т. 104, No 4, с. 501–04; Кlееnе S. С., Recursive predicates and quantifiers, "Trans. Amer. Math. Soc.", 1943, v. 53, p. 41–73; Ρоst Ε. L., Recursively enumerable sets of positive Integers and their decision problems, "Bull. Amer. Math. Soc.", 1944, v. 50, p. 284–316; Mostowski Α., On definable sets of positive integers, "Fundamenta Mathematicae", 1947, v. 34, p. 81–112.

Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. . 1960—1970.


.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "ПРЕДИКАТОВ КЛАССИФИКАЦИИ" в других словарях:

  • ПРЕДИКАТ — (от лат. praedicatum сказанное) языковое выражение, обозначающее к. л. свойство или отношение. П., указывающий на свойство отдельного предмета (напр., «зеленый», «теплый»), называется одноместным. П., обозначающий отношение, называется… …   Философская энциклопедия

  • ТЕОРИЯ МНОЖЕСТВ — теория, в к рой изучаются множества (классы) элементов произвольной природы. Созданная прежде всего трудами Кантора (а также Р. Дедекинда и К. Вейерштрасса), Т. м. к концу 19 в. стала основой построения сложившихся к тому времени математич.… …   Философская энциклопедия

  • АРИСТОТЕЛЬ — (Aristoteles) (384 322 до н.э.) великий др. греч. философ и ученый, создатель логики, основатель психологии, этики, политики, поэтики как самостоятельных наук. Родившись на северо востоке Греции (г. Стагира), провел 20 лет в Академии Платона (см …   Философская энциклопедия

  • ЛОГИКА — (от греч. logos слово, понятие, рассуждение, разум), или Формальная логика, наука о законах и операциях правильного мышления. Согласно основному принципу Л., правильность рассуждения (вывода) определяется только его логической формой, или… …   Философская энциклопедия

  • Перцептрон — Логическая схема перцептрона с тремя выходами Перцептрон, или персептрон[nb 1] (англ. perceptron от …   Википедия

  • Персептрон — Логическая схема перцептрона с тремя выходами Перцептрон, или персептрон[nb 1] (англ. perceptron от лат. perceptio  восприятие; нем. perzeptron)  математическая и компьютерная модель восприятия информации мозгом (кибернетическая модель мозга),… …   Википедия

  • КАРИНСКИЙ — Михаил Иванович [4(16) ноября 1840 – 20 июля (2 авг.) 1917 ] – рус. логик и философ материалист. Род. в семье священника. Окончил Моск. духовную академию (1862). В 1869–94 преподавал философию в С. Петербургской духовной академии и др. учебных… …   Философская энциклопедия

  • _2. Теоретическая база словаря и исходные теоретические положения — При работе над словарем мы опирались на следующие теоретические положения лексикологии и семантического синтаксиса. Первое. Идея единства лексики и грамматики. Это взаимодействие осуществляется главным образом на уровне семантических моделей… …   Экспериментальный синтаксический словарь

  • ПОНЯТИЕ — общее имя с относительно ясным содержанием и сравнительно четко очерченным объемом. П. являются, напр., «химический элемент», «закон», «сила тяготения», «астрономия», «поэзия» и т.п. Отчетливой границы между теми именами, которые можно назвать П …   Философская энциклопедия

  • Типов теория — I Типов теория         в химии, одна из ведущих химических теорий середины 19 в. В 1839 1840 Ж. Б. Дюма предложил рассматривать химические соединения как продукты замещения одних элементов или радикалов (см. Радикалов теория) другими в немногих… …   Большая советская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»