Возможно, просто перебором конечных подмножеств натуральных чисел мощности
, где
- количество переменных.
Не понял. Натуральных чисел же "много".
Не так то и много - всего
, соответственно, конечных упорядоченных подмножеств ("с повторениями") мощности
- тоже
, значит их всех можно пронумеровать натуральными числами. Представим, что алгоритмически неразрешимая система имеет решение
, тогда это подмножество пронумеровано каким-то натуральным числом
, значит перебор закончится на конечном
- том шаге.
Я также читал, что из алгоритмической неразрешимости гипотезы Римана следует её истинность, поскольку иначе можно с помощью алгоритма найти ноль, нарушающий её условие.
А вы не про константу Хайтина там читали? Или про пример для теоремы Гёделя?
Нет.
Нельзя просто перебором решить алгоритмически неразрешимую задачу.
Нельзя перебором решить произвольную алгоритмически неразрешимую задачу. Но речь не о произвольной. Речь об очень небольшой конечной задаче. Её - можно.
Речь не о конечной задаче, речь конкретной системе. Для того, чтобы перебором доказать отсутствие решений, нужно перебрать всё бесконечное количество подмножеств, что не осуществимо.
Поймите, для ограниченного мозга надо всю математику переписывать.
Это для компьютера надо было бы переписать. И есть вроде бы математика, где все множества конечны. А мозг и так справляется, а за счёт чего именно - это другой вопрос. Гипотезы по этому поводу есть.
М. Вербицкий писал(а):
Пенроуз объяснял это явление так. Пространство обычной эйнштейновской гравитации искривлено. В квантовом приближении, эти искривления непрерывно меняются, причем даже таким образом, что меняется сама топология пространства: пространство кипит, в нем появляются и исчезают дырки, пузыри и ручки наподобие кренделя. Если мы хотим подсчитать квантовую гравитацию, нам придется, видимо, усреднять наш функционал по всем топологическим конфигурациям 4-мерного пространства. Но перечислить такие конфигурации ("четырехмерные многообразия") невозможно - эта задача равносильна по сложности с задачей решения целочисленных уравнений. То есть никакого алгоритмического способа решить уравнения четырехмерной гравитации, видимо, нет. С другой стороны, в природе эти решения как-то получаются, то есть природа каким-то образом умеет подсчитать четырехмерные многообразия. Вероятно, делая наблюдения над природными феноменами, мы сможем научиться эти многообразия тоже различать, то есть путем наблюдения решать задачи, алгоритмически неразрешимые в принципе и доказывать теоремы, которые никак не вытекают из любой конечной системы аксиом.
Пенроуз предположил, что в голове у человека находится такой механизм. Таким образом, абстрактное мышление превращается в нечто вроде эксперимента в физической лаборатории, имя которой - мозг - а результатом эксперимента оказывается научная истина.
(Оффтоп)
Вы принялись вместо тех аргументов, которые слышите, спорить с "оппонентом типовым, резиновым"?
Только не вместо, а одновременно, поскольку я на аргументы тоже ответил. Это плохо, конечно, я сделал, но драматизировать не стоит.
Я говорю о конкретных задачах, которые компьютер решить не может, а человек - может. В качестве примера можно взять систему диофантовых уравнений, указанную Матиясевичем. Она не имеет решений, но нет формального алгоритма, который бы это вывел.
Нет таких задач - это противоречит тезису Тьюринга. Упомянутую задачу человек также не может решить: он не может предъявить алгоритм, разрешающий это уравнение.
Речь идёт о том, что тезис Тьюринга имеет ограничения, и в том числе и в связи с мышлением человека. Так что Вы не можете приводить его в качестве аргумента.
А упомянутую задачу человек решить может. Ещё раз. Система алгоритмически неразрешима. Если бы она имела решения, то она не была бы алгоритмически неразрешима. Значит она не имеет решений. Алгоритма, разумеется, нет, но это справедливо считается математиками доказательством. Я же приводил цитату М. Вербицкого. Хотя, я не только у него это встречал. А компьютер не сможет прийти к выводу, что решений нет.
М.Вербицкий писал(а):
Действительно, если бы у X были бы решения, эти решения можно было бы предъявить, и при наличии решений X не могло бы быть независимым от остальных аксиом. Поэтому, доказательство независимости наличия решений у X от остальных аксиом является доказательством того, что у X нет решений.
С другой стороны, легко написать программу, которая будет просто печатать доказательство Матиясевича, что можно интерпретировать как то, что программа может доказать, что данное уравнение неразрешимо.
Так не считается. Эта программа не решает задачу, а совершенно дибильно рисует картинки. Можете в ту же программу подставить другие символы и она же Вам "докажет", что это уравнение алгоритмически разрешимо. Или ещё какую-нибудь хрень напишет. Можно также по-другому интерпретировать символы и представить какую-нибудь ахинею, написанную в стандартных обозначениях, как доказательство в новой интерпретации тех же символов. Короче, это заведомое жульничество, к мышлению отношения не имеющее.