배열의 지원 없이 언어는 튜링 완전할 수 있을까요?

언어에 제어 구조와 변수가 있지만 배열, 리스트, 메모리 접근 및 할당 등의 지원이 없는 경우에도 튜링 완전(Turing-complete)할 수 있을까요?

만약 생성할 수 있는 변수의 양에 제한이 없다면, array_1, array_2, ... array_6000과 같은 변수를 생성하여 수동으로 반복하고 복잡한 데이터 구조와 재귀를 어떻게든 만들어 배열을 시뮬레이션할 수 있을 것입니다.

편집: 이름 조작으로 변수에 접근할 수 없는 경우에도 가능할까요? (array_10+i는 허용되지 않음)

답변 1

확실합니다. 람다 계산법을 살펴보세요. 이는 내가 본 가장 최소한의 튜링 완전한 언어 중 하나입니다. 기본적으로 람다 (함수 리터럴)만 있는데, 할당도 없고 선언도 없고 데이터 구조도 없습니다. 모든 것이 매우 간소화되어 있습니다.

하지만 함수를 연결하여 List와 같은 선형 데이터 구조를 시뮬레이션 할 수 있습니다. 상당히 장황해질 수 있지만 가능하고 연속적으로 이름이 지정된 변수의 큰 연속을 가지는 것보다 훨씬 좋습니다.

일반적으로, 언어가 튜링 완전(Turing Complete)인지 아닌지는 해당 언어에 배열이 있는지 여부와는 무관합니다. SML과 Haskell과 같은 함수형 언어는 람다 계산법과 마찬가지로 배열이 없지만, 실제로 유용한 언어입니다! 언어가 튜링 완전이라는 것은 해당 언어로 표현할 수 없는 튜링 계산 가능한 함수가 없다는 뜻입니다. 이는 놀랍게도 매우 유연한 자격 조건이며, 람다 계산법과 같이 완전히 비실용적인 많은 언어를 허용합니다.

답변 2

한국어로 작성된 이 글은 SEO에 최적화되었습니다.
배열 지원 없이도 언어가 튜링 완전(Turing-complete)할 수 있을까요?
튜링 완전한 언어는 알고리즘이나 계산 과정을 표현할 수 있는 언어를 말합니다. 튜링 기계(Turing machine)에 의해 계산이 가능한 언어라고도 할 수 있습니다. 이번 글에서는 배열 지원 없이도 언어가 튜링 완전할 수 있는지에 대해 알아보겠습니다.
배열은 데이터를 저장하고 순회하며 처리할 수 있는 중요한 자료 구조입니다. 따라서 배열은 프로그래밍 언어에서 매우 중요한 역할을 합니다. 그러나 배열을 지원하지 않는 언어에서도 튜링 완전한 언어가 존재할 수 있습니다.
언어가 튜링 완전하려면 다음의 세 가지 기능을 갖추어야 합니다: 조건 분기(if-else 문), 반복(loop 문), 변수 지원. 이러한 기능들만 있다면, 어떠한 연산도 수행할 수 있습니다. 배열은 이러한 기능 중의 하나일 뿐입니다.
배열을 지원하지 않는 언어에서는 대신 다른 자료 구조를 활용할 수 있습니다. 예를 들어, 연결 리스트(linked list)나 해시 테이블(hash table)은 배열과 유사한 기능을 수행할 수 있습니다. 이를 통해 배열 없이도 데이터의 저장, 관리, 처리를 할 수 있습니다.
한 가지 예시로는 람다 대수(lambda calculus)라는 수학적 모델을 들 수 있습니다. 람다 대수는 함수의 형태로 계산을 표현하는 수학적 모델입니다. 람다 대수는 배열을 지원하지 않지만, 함수의 조합과 활용을 통해 어떠한 계산도 수행할 수 있습니다.
결론적으로, 배열을 지원하지 않는 언어가 튜링 완전할 수 있습니다. 배열은 중요한 자료 구조이지만, 튜링 완전성을 달성하기 위해서는 배열이 반드시 필요한 것은 아닙니다. 언어가 조건 분기, 반복, 변수 등의 기능을 갖추었다면, 배열 없이도 어떠한 계산이든지 표현할 수 있습니다.