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


ТОЖДЕСТВА ПРОБЛЕМЫ
проблемы эквивалентности, проблемы иден-тичности, проблемы равенства с л о в (англ. 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.


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





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

  • “ДВЕ ОСНОВНЫЕ ПРОБЛЕМЫ ЭТИКИ”
  • “ПРОБЛЕМЫ ИДЕАЛИЗМА”
  • “ПРОБЛЕМЫ ТВОРЧЕСТВА ДОСТОЕВСКОГО”
  • ГЛОБАЛЬНЫЕ ПРОБЛЕМЫ
  • Гендерные проблемы инвалидности
  • Групповое решение проблем (group problem solving)
  • ЗАКОН ТОЖДЕСТВА
  • ЗАКОН ТОЖДЕСТВА
  • История европейской культурной традиции и ее проблемы
  • Каннера феномен тождества
  • НЕРАЗРЕШИМОСТЬ АЛГОРИТМИЧЕСКОЙ ПРОБЛЕМЫ
  • ОТНОШЕНИЯ ТИПА РАВЕНСТВА
  • Основные проблемы экономической статики и динамики: предварительный эскиз
  • Поведенческая терапия: проблемы и вопросы (behavior therapy: problems and issues)
  • Пространство проблемы
  • Психологическое тестирование: проблемы выживания (psychological testing: its survival problems)
  • РАЗРЕШЕНИЯ ПРОБЛЕМЫ
  • ТОЖДЕСТВА ЗАКОН
  • ТОЖДЕСТВА ФИЛОСОФИЯ
  • Тождества феномен
  • ФИЛОСОФИЯ ТОЖДЕСТВА
  • Феномен тождества
  • Философские проблемы психологии (philosophical problems in psychology)
  • Фундаментальные проблемы теорий истины
  • Этические проблемы в психологии (ethical problems in psychology)
  • Явление и смысл. Феноменология как основная наука и ее проблемы
  • алгоритмическая неразрешимость
  • отношение типа равенства
  • проблемы мира и войны
  • тождества закон



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

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






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

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







    Locations of visitors to this page



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