Может ли язык быть полным по Тьюрингу без какой-либо поддержки массивов?
Если язык имеет управляющие структуры и переменные, но не поддерживает массивы, списки, доступ к памяти и распределение и т. Д., Может ли он быть завершенным по Тьюрингу?
Может быть, если не было ограничений на количество переменных, которые вы можете создать, вы можете моделировать массивы, создавая переменные, такие как array_1, array_2... array_6000 и вручную перебирать их, и как-то создавать сложные структуры данных и рекурсию?
Редактировать: даже если вы не можете получить доступ к переменным путем манипулирования именами (array_10+i не допускается)?
2 ответа
Конечно. Взгляните на Lambda Calculus, один из самых минимальных языков Turing Complete, который я когда-либо видел. По сути, у вас есть только лямбды (функциональные литералы); нет присваивания, нет декларации, нет структур данных. Это все очень, очень худой.
Однако вы можете имитировать линейную структуру данных, например, List, объединяя функции. Это довольно многословно, но, безусловно, возможно, и гораздо приятнее, чем иметь большой набор последовательно именованных переменных.
Вообще говоря, является ли язык Turing Complete или нет, не имеет никакого отношения к тому, есть ли у него массивы. Функциональным языкам, таким как SML и Haskell, не хватает массивов, как, например, Lambda Calculus, и это действительно полезные языки! Сказать, что язык "завершен по Тьюрингу", - это просто еще один способ сказать, что не существует функции вычислимости по Тьюрингу, которая не может быть выражена на указанном языке. Это удивительно свободная квалификация, позволяющая использовать многие языки, которые были бы абсолютно непрактичными (например, лямбда-исчисление).
Существует множество языков, полных тьюринга, которые даже не имеют понятия "переменная"! Доступ к памяти и ее распределение - это детали реализации, поэтому они не имеют никакого значения. Вы должны понимать, что машины Тьюринга и полнота Тьюринга - это очень теоретические концепции, полезные для доказательства, но полностью оторванные от реальности реального оборудования.
Пол Грэм написал длинное, но очень, очень интересное эссе по истории компьютерных языков, где он описывает две очень разные основные традиции компьютерных языков:
- Lisp, Scheme и т. Д. - основаны на теоретических соображениях, очень простых, но концептуально мощных языках, но в течение длительного времени непрактичных из-за их полного игнорирования того, что легко и эффективно реализовать
- Ассемблер, FORTRAN, C и почти все "основные" языки - более или менее напрямую получены из возможностей оборудования, просты в реализации, эффективны, но в течение продолжительного времени уступают (более старому!) Семейству Lisp с точки зрения выразительности,
Похоже, вы знаете только вторую традицию, но полнота Тьюринга - это концепция, которая исходит из тех же принципов, что и первая традиция, и имеет мало смысла, если вы не знаете этих принципов.