Имеют ли соображения неразрешимости Тьюринга и вычислительной сложности (NP-трудность и т. д.) последствия для эпистемологии? Если функция X или предложение неразрешимы или требуют вычисления неразрешимого количества ресурсов, считается ли оно по-прежнему познаваемым?
До сих пор соображения, основанные на вычислительных ресурсах, имеют значение только для небольшой группы философов, известных как радикальные антиреалисты, которые распространяют строгий финитизм на эпистемологию. В отличие от конструктивистов и умеренных антиреалистов (интуиционистов), таких как Даммет, которых обычно удовлетворяет вычислимость в принципе, радикальные антиреалисты настаивают на большем, чем на «практической осуществимости». В частности, они отвергли бы закон исключенного третьего даже для вычислимых предикатов.
Одно из предложений эпистемологической логики радикального антиреализма, данное Дюбуксом и Мэрион, состоит в том, чтобы использовать вычислимость за полиномиальное время как формализацию «практической осуществимости», поэтому, по-видимому, они сочувствуют таким проблемам, как NP-трудность редукции. теории более высокого уровня к более низкоуровневым. По крайней мере, на данный момент классические и даже господствующие антиреалистические эпистемологии довольствуются этим «в принципе».
См. обзор Видаля-Россета и оригинальную статью Дюбукс-Марион .
Я бы сказал ДА в отношении проблемы NP. См. Фундаментальную теорему арифметики . Это теорема, поэтому ее можно познать как истинную и доказуемую. Однако, если вы можете разложить число на множители за время NP, то вы бог и облажались со всем Интернетом.
Изучение предложений как обоснованного рассуждения не имеет ничего общего с требуемым временем или количеством шагов. Последствия NP/NPC/NPH будут аналогичны последствиям попытки Божественной Машины обнаружить столкновение: это просто раздражающий вопрос времени, но не обоснованности рассуждений.
Что касается проблемы неразрешимости, символической проблемой здесь является проблема остановки, и да, она имеет эпистемологические последствия . В основном: есть некоторые ограничения в вашей способности что-то доказать в вашей собственной системе, и в системе схемы Тьюринга такая проблема выражается в терминах неразрешимых (или полуразрешимых) проблем, подобных этой.
Корт Аммон
Корт Аммон