Существует ли набор конструкций языка программирования на языке программирования, чтобы его можно было считать завершенным по Тьюрингу? Из того, что я могу сказать из Википедии , язык должен поддерживать рекурсию или, по-видимому, должен иметь возможность работать без остановки. Это все, что...
Я столкнулся со странной проблемой при написании интерпретатора, который (должен) подключаться к внешним программам / функциям: функции в «C» и «C ++» не могут перехватывать переменные функции , например, я не могу создать функцию, которая вызывает «printf» с точно такими же аргументами, которые он...
Я пытался объяснить кому-то, что C завершена по Тьюрингу, и понял, что на самом деле не знаю, действительно ли он технически завершен по Тьюрингу. (C как в абстрактной семантике, а не как в реальной реализации.) «Очевидный» ответ (грубо говоря: он может адресовать произвольный объем памяти, поэтому...
Я вижу, что большинство определений того, что должно быть полным по Тьюрингу, в некоторой степени тавтологично. Например, если вы Google «что значит быть полным по Тьюрингу», вы получите: Компьютер завершается по Тьюрингу, если он может решить любую проблему, которую может выполнить машина Тьюринга...
Я читал о Йоте и Джоте и нашел этот раздел запутанным: В отличие от Iota, где синтаксическое дерево для строки может разветвляться либо слева, либо справа, синтаксис Jot равномерно разветвляется слева. В результате, Йота не зависит от контекста, но Йот - это обычный язык. Насколько я понимаю, и...
Обратите внимание, хотя я знаю, как программировать, я довольно новичок в теории CS. Согласно этому ответу Полнота по Тьюрингу - это абстрактное понятие вычислимости. Если язык является полным по Тьюрингу, то он способен выполнять любые вычисления, которые может выполнять любой другой полный по...
Возможно, мое ограниченное понимание предмета неверно, но это то, что я понимаю до сих пор: Функциональное программирование основано на лямбда-исчислении, сформулированном Алонзо Черчем. Императивное программирование основано на модели машины Тьюринга, созданной Аланом Тьюрингом, учеником Черча....
Я знаю, что в императивных языках программирования цикла while-do достаточно в качестве конструкции потока управления, чтобы сделать язык Тьюринга завершенным (что касается потока управления - конечно, нам также нужна неограниченная память и некоторые операторы ...) , Суть моего вопроса такова:...
Относительно квантовых ворот Тоффоли : это классически универсально, и если так, то почему? это квантово универсально и почему?
Я прочитал страницу Википедии для правила 110 в клеточных автоматах, и я более или менее знаю, как они работают (набор правил решает, где рисовать следующие 1 или 0). Я только что прочитал, что они завершены по Тьюрингу, но я даже не могу понять, как бы вы «запрограммировали» «правило 110»?...
Какие операции необходимо выполнить, чтобы выполнить произвольные аналоговые вычисления ? Достаточно ли будет сложение, вычитание, умножение и деление? Кроме того, кто-нибудь знает точно, какие проблемы можно решить с помощью аналоговых вычислений, но не с...
Я знаю, что можно доказать, что PROLOG является полным по Тьюрингу, создав программу, которая имитирует машину Тьюринга, например: turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, Rs0, Rs) :-...
Такие языки, как являются сокращением много-один. Нетрудно видеть, что имеет полные проблемы. С. Шмитц [1] рассматривает некоторые классы между и . Они представляют полные проблемы для этих классов при специально созданных...
Я знаю, что шлюзы NAND можно использовать для создания схем, реализующих каждую таблицу истинности, а современные компьютеры состоят из вентилей NAND. Какова теоретическая связь между воротами NAND и полнотой Тьюринга? Мне кажется, что схемы затворов NAND ближе к конечным автоматам, чем машины...
Я задал похожий вопрос на cstheory.SE . Согласно этому ответу на Stackoverflow существует алгоритм, который на не ленивом чисто функциональном языке программирования имеет сложность , тогда как тот же алгоритм в императивном программировании - Ω ( n ) . Добавление ленивости к языку FP сделало бы...
Комментарий к tex.SE заставил меня задуматься. Утверждение по существу: Если я могу написать компилятор для языка X на языке X, то X полон по Тьюрингу. В терминах вычислимости и формальных языков это: Если решает , L ⊆ L T M и ⟨ M ⟩ ∈ L , то F L = R E .MMML ⊆ LТ МL⊆LTML \subseteq L_{\mathrm{TM}}⟨...
Brainfuck - полный язык программирования Тьюринга, который использует только 8 символов (6, если вы игнорируете ввод / вывод). Две наиболее заметные из них , которые толкают его на Тьюринга полнота [и ], по существу , этикетки и Гото Brainfuck в. Обычно программы в Brainfuck используют несколько...
Если у нас есть какая-либо произвольная компьютерная программа, которая может изменить ее инструкции, возможно ли смоделировать эту программу с помощью программы, которая не может изменить ее инструкции? Редактировать: Я новичок в stackexchange, поэтому не уверен, что мне разрешено задавать НОВЫЙ...
Я видел веб-сайты, которые якобы «доказывают», что HTML5 + CSS является Turing Complete. Я видел сайты, которые якобы «доказывают», что SQL завершен по Тьюрингу. Я видел множество веб-сайтов, которые якобы «объясняют», что значит быть завершенным по Тьюрингу. Достаточно! Где я могу найти книгу...
Я пытаюсь найти ответы на два вопроса об универсальной машине Тьюринга. Как универсальная машина Тьюринга может моделировать машину Тьюринга, если моделируемая машина имеет большее число состояний? Как универсальная машина Тьюринга может имитировать машину Тьюринга, если на моделируемой машине...