(простите, что повторяю базовые определения), доказательство в системе Гильбертовского типа — это конечная последовательность формул, удовлетворяющая известным условиям. А последовательность — это функция из натуральных чисел в множество формул (в данном случае).
Внимание вопрос: может ли такая функция быть невычислимой? Бывают ли невычислимыми "конечные" функции? 🧐
нужно, чтобы функция, имеющая доменом N, была неэффективной
Да. Точнее, конечное подмножество N. Такие вообще бывают?
если вопрос в том, вычислима ли функция с конечным доменом, то я почти уверен, что ответ “всегда да”
Да я тоже почти уверен, но интересно было бы взглянуть на такую теорему. 😊
Обсуждают сегодня