Описание тега turing-complete
Модель вычислений называется полной по Тьюрингу, если она способна моделировать машину Тьюринга. Языки программирования, полные по Тьюрингу, по крайней мере так же мощны, как самые мощные модели допустимых вычислений, о которых когда-либо говорилось.
1
ответ
В чем причина полной системы типов Тьюринга?
Scala и Haskell имеют "системы полного типа Тьюринга". Обычно полнота по Тьюрингу относится к вычислениям и языкам. Что это действительно означает в контексте типов? Кто-нибудь может привести пример того, как программист может извлечь из этого польз…
30 ноя '15 в 15:27
3
ответа
Полный словарь
Под "словарем" я подразумеваю массив пар ключ / значение с уникальными ключами. Если нет, то почему? Если достаточно долго, вы можете использовать ключ в качестве входных данных и значение в качестве выходных данных, и это может решить столько пробл…
12 май '11 в 04:11
2
ответа
Может ли язык быть полным по Тьюрингу без какой-либо поддержки массивов?
Если язык имеет управляющие структуры и переменные, но не поддерживает массивы, списки, доступ к памяти и распределение и т. Д., Может ли он быть завершенным по Тьюрингу? Может быть, если не было ограничений на количество переменных, которые вы може…
07 сен '09 в 15:56
4
ответа
Полнота по Тьюрингу
Таким образом, можно сказать, что язык является полным по Тьюрингу, если он удовлетворяет некоторым критериям, и он может делать все, что может сделать другой полный по Тьюрингу язык. Значит ли это, что я теоретически могу реализовать Google, исполь…
11 сен '10 в 01:10
1
ответ
Субтьюринговый полный класс вычислительных моделей
Многие языки программирования и системы полны по Тьюрингу; они могут моделировать любую машину Тьюринга и, следовательно, могут моделировать любой конечный автомат. Рассмотрим следующую неформальную модель: Язык A определяет конечный набор вентилей …
30 май '17 в 15:32
10
ответов
Может ли язык быть полным, но не полным другими способами?
Например, существуют ли определенные вещи при написании операционной системы, которые не могут быть выполнены на языке полного тестирования?
01 май '09 в 23:07
2
ответа
Корреляционное исчисление кортежей
Является ли безопасное корреляционное исчисление кортежей полным языком?
10 янв '10 в 17:24
1
ответ
Является ли Wolfram Language настоящим языком программирования?
Wolfram собирается выпустить свой "язык программирования, основанный на знаниях", но действительно ли это настоящий язык программирования так же, как C#, Java и т. Д.? Чтобы это не было слишком субъективным, я поясню, что под "истинным языком програ…
27 фев '14 в 16:14
1
ответ
HTML5 тьюринг завершен?
Я хотел бы знать, возможно ли это сделать? <turning> <complete /> <complete /> </turing> Спасибо
30 апр '18 в 23:32
2
ответа
Почему язык сценариев должен быть "намеренно неполным по Тьюрингу"?
Итак, я читал о Bitcoin Script в их официальной документации и нашел следующую строку: "Скрипт прост, основан на стеке и обрабатывается слева направо. Он специально не является полным по Тьюрингу, без циклов". Я пытался рассуждать трудно, но не мог …
03 фев '15 в 00:00
0
ответов
Разрешает ли BlooP косвенную адресацию?
Дуглас Хофштадтер описывает язык программирования BlooP в своей книге "Gödel, Escher, Bach: Eternal Golden Braid". Мне неясно, требуют ли переменные ячейки постоянные индексы или разрешено косвенное обращение. Четыре примера, показанные в книге, пок…
06 дек '18 в 08:53
0
ответов
Почему машина Тьюринга делает n^k шагов для вычисления ввода?
Я читал о теореме Кука для машины Тьюринга. В доказательстве говорится, что Тьюрингу потребуется не более n^k шагов (где k - целое число, а k > 0), чтобы вычислить входные данные длины 'n'. Это, вероятно, предполагает, что машина Тьюринга останавлив…
17 дек '18 в 04:01
5
ответов
Действительно минимальный шут
Какой минимальный набор примитивов требуется для того, чтобы язык был полным по Тьюрингу и вариантом lisp? Похоже, автомобиль, CDR и некоторые управления потоком и что-то для REPL достаточно. Было бы хорошо, если бы был такой список. Предположим, ес…
28 апр '10 в 17:07
1
ответ
Brainfuck с 1-битными ячейками памяти?
Будет ли реализация языка программирования Brainfuck по-прежнему завершена, если его ячейки памяти будут иметь емкость 1 бит вместо обычных 8 бит? Инструкции + и - становятся идентичными, однако это не должно быть проблемой. Я не вижу проблем с, нап…
04 фев '17 в 11:04
5
ответов
Что заставляет людей думать, что NN обладают большей вычислительной мощностью, чем существующие модели?
Я читал в Википедии, что функции нейронной сети, определенные на поле произвольных действительных / рациональных чисел (наряду с алгоритмическими схемами и спекулятивными "транскурсивными" моделями), обладают большей вычислительной мощностью, чем ко…
10 май '10 в 16:27
0
ответов
Из каких элементов должен состоять тьюринговый полный язык программирования?
Я искал это, но ни к чему не привело. Я видел это объяснение однажды в какой-то книге о питоне, но я не помню, какая именно. Итак, из каких элементов (переменных, циклов, ветвлений и т. Д.) Должен состоять язык программирования, чтобы быть полным по…
05 янв '17 в 10:54
2
ответа
Является ли препроцессор C++ метапрограммирования полным по Тьюрингу?
Я знаю, что метапрограммирование шаблона C++ завершено по Тьюрингу. То же самое относится и к метапрограммированию препроцессора?
22 сен '11 в 01:14
3
ответа
Каковы шесть основных примитивов в Тьюринге?
Я слушаю урок edX, и профессор подчеркивает, что каждую машину, способную выполнить эти шесть основных примитивов, можно назвать Turing Complete. Но каковы шесть основных примитивов?
26 янв '15 в 10:41
1
ответ
Какое свойство системы типов Scala делает его полным по Тьюрингу?
Scala использует систему типов, основанную на Системе F ω, которая обычно считается сильно нормализующей. Сильно нормализующая подразумевает нетюринговую полноту. Тем не менее, система типов Скалы полна по Тьюрингу. Какие изменения / дополнения / мо…
13 дек '11 в 23:36
4
ответа
Критерии, чтобы определить, является ли это язык программирования
Какие критерии или основные функции необходимы, чтобы сказать, что X или Y является (или не является) языком программирования? Я немного прочел ( HTML считается языком программирования?, завершен по Тьюрингу и т. Д.) И пришел к выводу, что язык или …
31 янв '11 в 10:52