РАЗРЕШЕНИЯ ПРОБЛЕМА


РАЗРЕШЕНИЯ ПРОБЛЕМА
    РАЗРЕШЕНИЯ ПРОБЛЕМА — возникла в связи с осознанием невозможности провести некоторые построения дозволенными методами. Первыми примерами неразрешимых задач явились решение в радикалах уравнений выше четвертой степени и невозможность провести некоторые построения циркулем и линейкой.
    Общая формулировка проблемы разрешения следующая: дан класс методов Ф, дан класс проблем Р. Можно ли найти единый метод/? Ф (разрешающий метод), позволяющий решить каждую из проблем Р, для которой в принципе существует решение?
    Часто в текстах по логике и математике рассматривается более частная формулировка проблемы разрешения, называемая алгоритмической разрешимостью, в которой разрешающий метод должен быть алгоритмом, т. е. класс методов Ф фиксируется и считается множеством алгоритмов. Исторически алгоритмическая неразрешимость была первым явно выделенным случаем общей проблемы разрешения. В последнее время в связи с осознанием разницы между теоретической и практической вычислимостью появилась третья формулировка, когда разрешающий метод — не просто алгоритм, а алгоритм ограниченной сложности. Напр., линейная разрешимость — разрешимость программой, вычислимая за линейное время относительно длины исходных данных, NP — полная проблема — проблема, разрешимая лишь программой полного перебора.
    Примерами в разной степени неразрешимых проблем являются: построение модели любой непротиворечивой классической теории — неразрешима однозначно определенными (без аксиомы выбора) теоретико-множественными функционалами; проверка истинности формул арифметики либо (соответствия) программ их спецификации — неразрешима средствами формальных теорий с алгоритмически заданным множеством аксиом; проверка доказуемости в формальной арифметике или в классической логике предикатов — алгоритмически неразрешима; задача нормализации выводов в логике предикатов — неразрешима примитивно-рекурсивными алгоритмами; задача перестройки естественного вывода в резолюционный — неразрешима алгоритмами, делающими не более
    У^раз)
    шагов, где и — длина вывода, k — любое фиксированное число; проверка тавтологичности формул классической логики высказываний — переборно разрешима, но неразрешима менее чем переборными алгоритмами.
    Заметим, что неразрешимость проблемы означает лишь отсутствие единого метода, хотя в каждом конкретном случае ее можно пытаться решать, если решение не претендует на слишком большую общность. В последнее время выявилось общее свойство частных решений неразрешимых проблем: по мере расширения класса решаемых задач сложность методов с некоторого момента быстро растет, а эффективность столь же быстро убывает.
    Точно так же результат о достаточно простой разрешимости проблемы может оказаться дезориентирующим, если эта достаточная простота достигается лишь на очень больших объектах, а для малых все равно приходится практически действовать перебором. Примером здесь может служить классическая задача о раскраске карт четырьмя цветами. Сведение к неразрешимым проблемам стало столь же мощным методом установления некорректности задач либо решений, каким является в физике сведение к возможности построить вечный двигатель. Напр., того, кто написал программу, ищущую зацикливание в других программах, не будут слушать, если он сам не предоставит примеры, когда его программа не работает либо работает неправильно, Неразрешимость проблемы разложения числа на простые множители достаточно простым алгоритмом стала основой современной теории надежных индивидуальных шифров. Одним из методов решения неразрешимых проблем является переход к вероятностным алгоритмам разрешения и к квантовым вычислениям. Показано, что для многих переборных задач есть быстрые алгоритмы, решающие их со сколь угодно близкой к 1 заранее заданной вероятностью.
    Н. Н. Непейвода

Новая философская энциклопедия: В 4 тт. М.: Мысль. . 2001.


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





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

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



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

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






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

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







    Locations of visitors to this page



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