Похожие чаты

В связи с недавним спором возник вопрос теоретического свойства... Как известно

(простите, что повторяю базовые определения), доказательство в системе Гильбертовского типа — это конечная последовательность формул, удовлетворяющая известным условиям. А последовательность — это функция из натуральных чисел в множество формул (в данном случае).

Внимание вопрос: может ли такая функция быть невычислимой? Бывают ли невычислимыми "конечные" функции? 🧐

4 ответов

7 просмотров

нужно, чтобы функция, имеющая доменом N, была неэффективной

Alexander-Chichigin Автор вопроса
Brenoritvrezorkre
нужно, чтобы функция, имеющая доменом N, была неэф...

Да. Точнее, конечное подмножество N. Такие вообще бывают?

если вопрос в том, вычислима ли функция с конечным доменом, то я почти уверен, что ответ “всегда да”

Alexander-Chichigin Автор вопроса
Rust Skye
если вопрос в том, вычислима ли функция с конечным...

Да я тоже почти уверен, но интересно было бы взглянуть на такую теорему. 😊

Похожие вопросы

Обсуждают сегодня

А кто-то пробовал, уезжая из Эстонии получить э-рез и продолжить вести предпринимательскую деятельность внутри Эстонии, используя свой OÜ?
Lalalashechki Lalala
62
At which price point will BCH, an ASIC mined coin, be succeptible to reorg attacks because of low hashrate? $10? $1? $0.1? $0.01?
Kishniev
18
Is Kadena onto something special? No one really knows. Good luck!
Bright Uncle Stephen EqualBet
40
зачем же переименовывать ? чтобы кол-во участников возросло или вдруг IBM от этого снова на свифте начнет кодить ? Я не понимаю что страшного в том что свифт гавно, если это т...
Oleh Nerzh
10
Гайз, кто-нибудь пробовал запустить probe-rs под камень, которого нет в probe-rs? Мб есть какой-нибудь пример у кого... Через target-gen попробовал сгенерировать chip-descript...
Максим Смирнов
2
я не магистр хаскеля, но разве не может лейзи тип конвертнуться в не-лейзи запросив вычисление содержимого прям при инициализации?
deadgnom32 λ madao
100
здравствуйте. совершаю вот такую вещь: strcpy(line, (char)current_number); где current number — неподписанный шорт, line — массив чаров. ругань следующая: main.c:29:30: error...
Roberto's Ширгозиев
13
Hello VIC team, I had previously used the “wallet.tomochain.com” with a ledger connection. Unfortunately, the site is no longer accessible and the ledger account is not visibl...
carpe noctem
7
@MrMiscipitlick А можешь макрос написать, который будет вычислять смещение относительно переданных меток? Просто .label1-.label2, и вернуть значение.
КТ315
35
А еще в перле можно уже @arr1 + @arr2?
Sergei Zhmylove
53
Карта сайта