Если я определяю функции Poly-time, функции, которые вычисляются машиной Тьюринга за максимальное полиномиальное (n) время, где n — размер ввода. Является ли класс этих функций рекурсивно перечислимым?

В этой статье автор утверждает: ... программа действительно показала, что механизм создания экземпляров шаблона представляет собой примитивный рекурсивный язык, который может выполнять нетривиальные вычисления во время компиляции. Я...

автограмма  – это предложение, описывающее содержащиеся в нем символы, обычно перечисляющее каждую букву алфавита, но возможно, также пунктуация, которую он содержит. Вот пример, приведенный на странице вики. В этом предложении две буквы...

Если L — любой язык. Язык perms(L) — это язык всех перестановок слов из L. Верно или неверно: если L рекурсивно перечислимо (вычислимо перечислимо), то perms(L) также рекурсивно перечислимо. Это было в предыдущем финале вместе с вопросом:...

Я изучаю вычислимость и сложность, и у меня возникли сомнения. Функция, которая сводит проблему к другой, является вычислимой по Тьюрингу. Мне было интересно, является ли это даже взаимно-однозначной функцией (соответствием), поскольку, глядя,...

Определите SAT2016 = {\phi | \phi — формула CNF с не более чем 2016 пунктами}. Если предположить, что P\neq NP, является ли SAT2016 NP-полным? Поскольку количество литералов в каждом предложении не ограничено, не сразу ясно, существует ли...

Я пытаюсь осмыслить лямбда-исчисление и то, как оно соотносится с языком, компилятором и двоичным кодом. Что на самом деле означает, что лямбда-исчисление эквивалентно машине Тьюринга, и где оно на самом деле проявляется? Я не понимаю, как...

Почему в доказательстве проблемы остановки мы должны передавать машину и ее описание в качестве входных данных? Например, я мог бы передать описание машины и некоторые другие входные данные (не саму машину), и все же доказательство от противного...

Насколько я понимаю, поскольку это не вычислимо, оно не может остановиться, когда ответ будет «да» или «нет». Вот почему он не может быть рекурсивно перечислимым, поскольку он не может гарантировать, что он всегда останавливается на «нет».

Характеристики вычислимой задачи: Полный означает, что он охватывает все случаи; Механистический означает, что он точен; Детерминированный означает, что при вводе одних и тех же входных данных будут предоставлены одни и те же выходные...

Как я могу выразить следующую функцию с помощью лямбда-члена? f(n) = T if n != 0. F if n = 0. n обозначает число Черча. Я знаю, что 0 := λf.λx.x, где λx.x — тождественная функция, а все остальные натуральные числа могут быть выражены как n :=...