ТОЖДЕСТВА ПРОБЛЕМЫ


ТОЖДЕСТВА ПРОБЛЕМЫ
проблемы эквивалентности, проблемы иден-тичности, проблемы равенства с л о в (англ. word problems) – задачи нахождения общего метода (алгоритма), позволяющего для произвольной пары элементов к.-л. множества, в к-ром определено отношение типа равенства (тождества, эквивалентности), установить, равны ли эти элементы в смысле данного отношения. Каждая Т. п. является, т.о., разрешения проблемой для множества всех пар равных (эквивалентных) друг другу "слов" в нек-ром "алфавите". Напр., не содержащие кванторов и переменных формулы т.н. ограниченной арифметики (т.е. формальной арифметич. системы, в число аксиом к-рой не входит принцип математической индукции или к.-л. равносильный ему постулат) можно понимать как слова, "буквами" к-рых являются цифровые знаки и символы арифметич. операций; алгоритм, дающий положительное решение Т. п. для выражений вида ?=?, образованных из таких формул с помощью стоящего между ними знака равенства, состоит в последовательном выполнении алгоритмов арифметич. действий в каждом из выражений А и В к последующей проверке, являются ли получившиеся в результате слова А и В, уже не содержащие букв "+", "–", "·" и ":", графически равными (т.е., попросту, совпадают ли они по написанию). Решение Т. п. даже для большинства сравнительно "простых" (по способу их задания) классов слов представляет, как правило, значит. трудности. Для нек-рых частных классов алгебраич. систем (групп, полугрупп) удалось найти алгоритмы, решающие (для них) Т. п. (М. Ден, В. Магнус, 1941, В. А. Тартаковский, 1949, и др.). Как и для любой массовой проблемы, для Т. п. положительное решение является в нек-ром смысле идеалом, к-рый, однако, достижим лишь в сравнительно редких случаях. Так, в 1947 А. А. Марков и амер. математик Э. Пост независимо друг от друга доказали алгоритмич. неразрешимость общей Т. п. для полугрупп (ассоциативных исчислений), поставленной еще в 1914. В 1950 Тьюринг установил неразрешимость Т. п. для т.н. полугрупп с сокращениями. Наконец, в 1952 П. С. Новиков доказал алгоритмич. неразрешимость Т. п. для групп, не поддававшуюся усилиям математиков с 1912 [этот результат был затем передоказан амер. математиками У. Буном (1959), Г. Хигманом (1961) и Дж. Бриттоном (1963)]. Дальнейшие результаты в этой области относятся к установлению иерархий, взаимной сводимости и степеней неразрешимости Т. п. для различных классов алгебраич. систем, а также к близким к Т. п. массовым проблемам логики, алгебры, теории алгоритмов и др. областей математики. Продолжаются и поиски частных классов систем с разрешимой Т. п. Неразрешимость важнейших случаев Т. п. свидетельствует о существенной нетривиальности не только различных Т. п., но и вообще самого понятия "равенства" ("тождества", "эквивалентности", "конгруентности" и т.п.), в т.ч. и в случаях "равенства по определению" (см. Определение), и об относит. характере этого важнейшего понятия логики и математики, зависящего, вообще говоря, от принимаемых в каждом конкретном случае исходных допущений (см. также Абстракция отождествления, Принцип абстракции, Тождество).
Лит.: Новиков П. С., Об алгоритмической неразрешимости проблемы тождества слов и теории групп, "Тр. Матем. ин-та АН СССР", 1955, т. 44; Адян С. И., Неразрешимость некоторых алгоритмических проблем теории групп, "Тр. Моск. матем. общества", 1957, т 6; Фридман ?. ?., Степени неразрешимости проблемы тождества для конечно-определенных групп, М., 1967; Rabin M. О., Recursive unsolvability of group theoretic problems, "Annals Mathematics", 1958, v. 67, No 1; Boone W., The word problem, там же, 1959, v. 70, No 2.
Ю. Гастев. Москва.

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


Просмотров: 1716
Категория: Словари и энциклопедии » Философия » Философская энциклопедия





Другие новости по теме:

  • “НОВЫЙ ОРГАНОН, ИЛИ ИСТИННЫЕ УКАЗАНИЯ ДЛЯ ИСТОЛКОВАНИЯ ПРИРОДЫ”
  • “О НЕОБХОДИМОСТИ И ВОЗМОЖНОСТИ НОВЫХ НАЧАЛ ДЛЯ ФИЛОСОФИИ”
  • “ФИЛОСОФИЯ ДЛЯ ДЕТЕЙ”
  • «ИСКУССТВО ДЛЯ ИСКУССТВА»
  • «НОВЫЙ ОРГАНОН, ИЛИ ИСТИННЫЕ УКАЗАНИЯ ДЛЯ ИСТОЛКОВАНИЯ ПРИРОДЫ»
  • Город для колесниц
  • ДЛЯ-МЕНЯ-БЫТИЕ
  • ДЛЯ-СЕБЯ-БЫТИЕ
  • Дорога для Рамы
  • жертвенник для курений
  • Загон для овец, овечий хлев
  • Квота для женщин
  • Комплекс испытаний для получения водительских прав (driver's license testing)
  • Кондаков И.М. Методика Для Изучения
  • Конференция Для Священнослужителей Разных Вероисповеданий
  • Кувшин Для Умывания
  • НЕРАЗРЕШИМОСТЬ АЛГОРИТМИЧЕСКОЙ ПРОБЛЕМЫ
  • НОВЫЙ ОРГАНОН, ИЛИ ИСТИННЫЕ УКАЗАНИЯ ДЛЯ ИСТОЛКОВАНИЯ ПРИРОДЫ
  • Новый органон, или Истинные указания для истолкования природы
  • Опросник Для Диагностики Устойчивых Форм
  • Оценка труда работника (для установления заработной платы) (job evaluation)
  • Письменные экзамены для аспирантов (graduate record examination (GREs))
  • Программы когнитивного вмешательства для пожилых людей (cognitive interventions with older persons)
  • Расстройство эмоций, специфическое для детского и подросткового возраста
  • Расстройство эмоций, специфическое для детского и подросткового возраста, с подавленностью и тоской
  • Расстройство эмоций, специфическое для детского и подросткового возраста, сопровождающееся тревогой и страхом
  • Такие подростки, как правило, зависимы от своих родителей и для них характерны социальная и психологическая незрелость и социальная изоляция.
  • Тесты для отбора кандидатов (selection tests)
  • ФИЛОСОФИЯ ДЛЯ ДЕТЕЙ
  • ЧЕЛОВЕК ДЛЯ СЕБЯ. ИССЛЕДОВАНИЕ ПСИХОЛОГИЧЕСКИХ ПРОБЛЕМ ЭТИКИ



  • ---
    Разместите, пожалуйста, ссылку на эту страницу на своём веб-сайте:

    Код для вставки на сайт или в блог:       
    Код для вставки в форум (BBCode):       
    Прямая ссылка на эту публикацию:       






    Данный материал НЕ НАРУШАЕТ авторские права никаких физических или юридических лиц.
    Если это не так - свяжитесь с администрацией сайта.
    Материал будет немедленно удален.
    Электронная версия этой публикации предоставляется только в ознакомительных целях.
    Для дальнейшего её использования Вам необходимо будет
    приобрести бумажный (электронный, аудио) вариант у правообладателей.

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







    Locations of visitors to this page



          <НА ГЛАВНУЮ>      Обратная связь