Язык может быть полным по Тьюрингу без поддержки массивов?
Нет того, потому что Вы не можете сделать этого в общем случае - что, если у Вас есть ленивый бесконечный генератор? Например:
def fib():
a, b = 0, 1
while True:
a, b = b, a + b
yield a
Это никогда не завершается, но генерирует Числа Фибоначчи. Можно получить столько Чисел Фибоначчи, сколько Вы хотите путем вызова next().
, Если действительно необходимо знать количество объектов, существует, тогда Вы не можете выполнить итерации через них линейно одного времени так или иначе, поэтому просто использовать различную структуру данных, такую как обычный список.
2 ответа
Конечно. Взгляните на Lambda Calculus , который является одним из самых минимальных полных языков Тьюринга, которые я когда-либо видел. По сути, все, что у вас есть, - это лямбды (функциональные литералы); без присваивания, без объявления, без структур данных. Все это очень и очень упрощено.
Однако вы можете смоделировать линейную структуру данных, такую как список, путем объединения функций в цепочку. Это становится довольно многословным, но это, безусловно, возможно, и это намного приятнее, чем иметь большой набор последовательно именованных переменных.
Вообще говоря, является ли язык полным или нет, не имеет ничего общего с тем, есть ли в нем массивы. В функциональных языках, таких как SML и Haskell, отсутствуют массивы, как и в Lambda Calculus, и это действительно полезные языки! Сказать, что язык является «полным по Тьюрингу», - это просто еще один способ сказать, что не существует вычислимой по Тьюрингу функции, которая не может быть выражена на указанном языке. Это на удивление слабая квалификация, позволяющая использовать многие языки, которые были бы совершенно непрактичными (например, лямбда-исчисление).
Существует множество языков, полных по Тьюрингу, в которых даже нет понятия «переменная»! Доступ к памяти и распределение - это детали реализации, поэтому они совершенно не важны. Вы должны понимать, что машины Тьюринга и полнота по Тьюрингу - очень теоретические концепции, полезные для доказательства, но полностью оторванные от реальности реального оборудования.
Пол Грэм написал длинное, но очень, очень интересное эссе по истории компьютерных языков, в котором он описывает две очень разные основные традиции компьютерных языков:
- Lisp, Scheme и т. Д. - выведенные из теоретических соображений, очень простые, но концептуально мощные языки, но долгое время непрактичные из-за полного игнорирования того, что?