Теория вычислимости или теория рекурсии.
Я готовлюсь к выступлению, направленному на студентов по математике, и в рамках этого я рассматриваю возможность обсуждения концепции разрешимости. Я хочу привести пример проблемы, о которой мы пока не знаем, что она разрешима или неразрешима. Таких проблем много, но пока что ни одна из них не...
Извините за запоминающееся название. Я хочу понять, что нужно сделать, чтобы опровергнуть тезис Черча-Тьюринга? Где-то я читал, что это математически невозможно сделать! Почему? Тьюринг, Россер и т. Д. Использовали разные термины, чтобы различать: «что можно вычислить» и «что можно вычислить с...
Есть ли связь между машиной Тьюринга и лямбда-исчислением - или они просто возникли примерно в одно и то же
У меня есть три связанных подвопроса, которые выделены пунктами ниже (нет, их нельзя разделить, если вам интересно). Андрей Бауэр писал здесь , что некоторые функции реализуются через машину Тьюринга, но не через лямбда-исчисление. Ключевой шаг его рассуждений: Однако, если мы используем...
Известно, что некоторые проблемы неразрешимы, но, тем не менее, можно добиться определенного прогресса в их решении. Например, проблема остановки неразрешима, но можно добиться практического прогресса в создании инструментов для обнаружения потенциальных бесконечных циклов в вашем коде. Проблемы с...
Насколько я понимаю, модель Тьюринга стала «стандартом» при описании вычислений. Мне интересно знать, почему это так - то есть, почему модель ТМ стала более широко используемой, чем другие теоретически эквивалентные (насколько мне известно) модели, например μ-Рекурсия Клини или Лямбда-исчисление (я...
Может ли каждая функция f:{0,1}∗→{0,1}f:{0,1}∗→{0,1}f : \{0,1\}^* \to \{0,1\} , вычисляемая за время ttt на одноленточной машине Тьюринга с использованием алфавита размера k=O(1)k=O(1)k = O(1) вычисляться за время O(t)O(t)O(t) на машина одной ленты Тьюринга с использованием алфавита размером 333...
Это вопрос, связанный с этим . Если после многих дискуссий там снова изложить это в гораздо более простой форме, то это стало совершенно другим вопросом. Классическое доказательство неразрешимости проблемы остановки зависит от демонстрации противоречия при попытке применить к себе гипотетический...
Я ищу окончательный ответ на вопрос, является ли генерация «действительно случайных» чисел вычислимой по Тьюрингу. Я не знаю, как точно сформулировать это. Этот вопрос StackExchange об «эффективных алгоритмах генерации случайных чисел» близок к ответу на мой вопрос. Чарльз Стюарт говорит в своем...
Недавно я услышал это: «Недетерминированная машина - это не то же самое, что вероятностная машина. В общих чертах, недетерминированная машина - это вероятностная машина, в которой вероятности переходов неизвестны». Я чувствую, как будто я понимаю, но я действительно не понимаю. Может ли кто-нибудь...
Пол Вегнер и Дина Голдин уже более десяти лет публикуют статьи и книги, утверждая, прежде всего, что тезис Черча-Тьюринга часто искажается в сообществе теории КС и в других местах. То есть он представлен как охватывающий все вычисления, когда на самом деле он применяется только к вычислению...
Постоянно растущая сложность компьютерных программ и все более важное положение, которое компьютеры занимают в нашем обществе, заставляют меня задуматься, почему мы до сих пор не используем все вместе языки программирования, на которых вам необходимо предоставить формальное доказательство...
Я взял класс один раз по вычислимости и логики. Материал содержал корреляцию между классами сложности / вычислимости (R, RE, co-RE, P, NP, Logspace, ...) и логикой (исчисление предикатов, логика первого порядка, ...). Корреляция включала в себя несколько результатов в одной области, которые были...
Невозможно написать язык программирования, который позволяет всем машинам, которые останавливаются на всех входах, и никаким другим. Тем не менее, кажется, что легко определить такой язык программирования для любого стандартного класса сложности. В частности, мы можем определить язык, на котором мы...
Я хочу закодировать простую машину Тьюринга в правилах карточной игры. Я хотел бы сделать его универсальной машиной Тьюринга, чтобы доказать полноту Тьюринга. До сих пор я создал игровое состояние, которое кодирует машину Тьюринга с 2 состояниями и 3 символами Алекса Смита . Тем не менее, кажется...
Компьютер с бесконечным потоком действительно случайных битов является более мощным, чем компьютер без него. Вопрос: достаточно ли он силен, чтобы решить проблему остановки? То есть может ли вероятностный компьютер определить, останавливается ли детерминированная программа? Пример вероятностного...
Существуют ли (функциональные?) Языки программирования, в которых все функции имеют каноническую форму? То есть любые две функции, которые возвращают одинаковые значения для всего набора ввода, представляются одинаково, например, если f (x) вернул x + 1, а g (x) вернул x + 2, то f (f (x )) и g (x)...
Известно, что с помощью счетного набора алгоритмов (характеризуемых числом Гёделя) мы не можем вычислить (построить двоичный алгоритм, который проверяет принадлежность) все подмножества N. Доказательство может быть обобщено следующим образом: если бы мы могли, то множество всех подмножеств N было...
В этой статье в Википедии о полноте Тьюринга говорится, что: Нетипизированное лямбда-исчисление является полным по Тьюрингу, но многие типизированные лямбда-исчисления, включая Систему F, - нет. Ценность типизированных систем основана на их способности представлять наиболее типичные компьютерные...
Если мы пойдем по книге (или любой другой версии спецификации языка, если вы предпочитаете), сколько вычислительной мощности может иметь реализация C? Обратите внимание, что «реализация C» имеет техническое значение: это конкретный экземпляр спецификации языка программирования C, в котором...