Машина Тьюринга является фундаментальной моделью вычислений, особенно в теоретической работе.
Есть ли связь между машиной Тьюринга и лямбда-исчислением - или они просто возникли примерно в одно и то же
У меня есть три связанных подвопроса, которые выделены пунктами ниже (нет, их нельзя разделить, если вам интересно). Андрей Бауэр писал здесь , что некоторые функции реализуются через машину Тьюринга, но не через лямбда-исчисление. Ключевой шаг его рассуждений: Однако, если мы используем...
Насколько я понимаю, модель Тьюринга стала «стандартом» при описании вычислений. Мне интересно знать, почему это так - то есть, почему модель ТМ стала более широко используемой, чем другие теоретически эквивалентные (насколько мне известно) модели, например μ-Рекурсия Клини или Лямбда-исчисление (я...
Реальные компьютеры имеют ограниченную память и ограниченное число состояний. Так что они по сути конечные автоматы. Почему теоретические компьютерные ученые используют машины Тьюринга (и другие эквивалентные модели) для изучения компьютеров? Какой смысл изучать эти гораздо более сильные модели по...
Может ли каждая функция 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 об «эффективных алгоритмах генерации случайных чисел» близок к ответу на мой вопрос. Чарльз Стюарт говорит в своем...
Пол Вегнер и Дина Голдин уже более десяти лет публикуют статьи и книги, утверждая, прежде всего, что тезис Черча-Тьюринга часто искажается в сообществе теории КС и в других местах. То есть он представлен как охватывающий все вычисления, когда на самом деле он применяется только к вычислению...
Во введении и объяснении P и NP классы сложности часто даются через машину Тьюринга. Одной из моделей вычислений является лямбда-исчисление. Я понимаю, что все модели вычислений эквивалентны (и если мы можем ввести что-либо в терминах машины Тьюринга, мы можем представить это в терминах любой...
Если ограничить машины Тьюринга конечной лентой (т. Е. Использовать ограниченное пространство ), то проблема остановки решаема, в основном потому, что после ряда шагов (которые можно рассчитать из числа состояний Q , S и размер алфавита), конфигурация должна быть повторена.SSSQQQSSS Существуют ли...
Я хочу закодировать простую машину Тьюринга в правилах карточной игры. Я хотел бы сделать его универсальной машиной Тьюринга, чтобы доказать полноту Тьюринга. До сих пор я создал игровое состояние, которое кодирует машину Тьюринга с 2 состояниями и 3 символами Алекса Смита . Тем не менее, кажется...
Компьютер с бесконечным потоком действительно случайных битов является более мощным, чем компьютер без него. Вопрос: достаточно ли он силен, чтобы решить проблему остановки? То есть может ли вероятностный компьютер определить, останавливается ли детерминированная программа? Пример вероятностного...
Если мы пойдем по книге (или любой другой версии спецификации языка, если вы предпочитаете), сколько вычислительной мощности может иметь реализация C? Обратите внимание, что «реализация C» имеет техническое значение: это конкретный экземпляр спецификации языка программирования C, в котором...
В этой статье в Википедии о полноте Тьюринга говорится, что: Нетипизированное лямбда-исчисление является полным по Тьюрингу, но многие типизированные лямбда-исчисления, включая Систему F, - нет. Ценность типизированных систем основана на их способности представлять наиболее типичные компьютерные...
Мы знаем, что (см., Например, теоремы 1 и 3 из [1]), грубо говоря, при подходящих условиях функции, которые могут быть эффективно вычислены машиной Тьюринга за полиномиальное время («эффективно вычисляемое»), могут быть выражены полиномиальными нейронными сетями. с разумными размерами, и, таким...
Предположим, я хотел формализовать доказательство Тьюринга относительно проблемы остановки, чтобы машина могла его проверить. Некоторые из известных автоматизированных систем доказательства теорем включают Mizar, Coq и HOL4. Я скачал и экспериментировал с Coq, но у него нет библиотеки для машин...
Давайте исправим кодирование без Трекинга машин Тьюринга и универсальную машину Тьюринга которая на входе (закодированный как код без префиксов последующим ) выводит все выходные данные на входе x (возможно, оба бегают вечно). Определим колмогоровскую сложность x , K (x) как длину самой короткой...
Я не могу думать ни о какой такой модели, может быть, о какой-то форме типизированного лямбда-исчисления? какой-то элементарный клеточный автомат? Это почти опровергло бы «Принцип вычислительной эквивалентности» Вольфрама: Почти все процессы, которые не являются явно простыми, могут рассматриваться...
Я знаю, что это очень специфический вопрос, и я сомневаюсь, что на него ответит любой, кто еще не знаком с правилами Магии. Перекрестная публикация на Draw3Cards . Вот исчерпывающие правила игры Magic: The Gathering . Смотрите этот вопрос для получения списка всех магических карт. У меня вопрос -...
Мне трудно преподавать понятие вычислимых функций. Я попытался развить идею, почему такие исследователи, как Гильберт / Аккерманн / Годель / Тьюринг / Черч / ... изобрели понятие «вычислимости». Студенты сразу спросили: «что означает вычислимость?» и я не могу ответить, пока не научу их машинам...
Читая некоторые недавние темы о квантовых вычислениях ( здесь , здесь и здесь ), я вспоминаю интересный вопрос о мощности некоторой машины, сохраняющей ℓpℓp\ell_p норму. Для людей, работающих в области теории сложности, которые идут на квантовую сложность, хорошим вступительным текстом является...