LLM은 Turing Completeness 할까?

발생

문뜩 떠오른 생각이다 대충 생각하기에는 Turing Complete(튜링 완전)할거 같긴한데 실제로 확인 해보고 싶었다.

참고

이 글에서 말하는 LLM은 Transformer 모델 기반의 순수한 단일 LLM을 의미한다.
이 글에서 말하는 튜링 완전성은 결정론적(deterministic) 튜링 완전성을 의미한다.

추론

우선 튜링 완전하려면 몇가지 조건이 존재한다. 조건을 아주 단순화하면 아래와 같다.

조건적 분기
1. e.g., if, while, goto 등
2. 어떤 입력된 상태에 따라 동작을 달리 할 수 있어야한다.
무한 저장 공간
1. e.g., 테이프가 무한한 튜링 머신, 스택 제한이 없는 시스템, 동적 메모리 할당에 제한이 없는 언어 등
2. 이론적으로 저장 공간을 무한하게 확장 시킬 수만 있다면 해당 조건을 충족한다.

자세한 튜링 완전한 조건을 보려면 내가 이전에 작성해둔 글을 참고하면 좋을 것 같다.

LLM 이 이 두가지 조건을 충족하는지 확인 해보자

조건적 분기 충족 여부

순수한 LLM 자체는 조건적 분기가 엄밀히 말해서 불가능하다.

그 이유는 아래와 같다.

LLM은 확률에 기반한 언어 모델이며 별도로 정보를 저장 할 수 없다.
결정론적 튜링 머신에서는 조건적 분기를 위해서는 정확한 기계적 연산이 필요하다.
기계적 연산은 정보를 이용해 확률이 아닌 정해진 규칙에 따라 결과 값을 도출해내는 것이다.
그러므로 LLM은 조건적 분기를 처리 할 수 없다.

하지만 LLM은 조건적 분기 같은 텍스트 생성은 가능하다 하지만 이는 확률적으로 실행되어 나온 결과일 뿐 실제 기계적 연산과는 본질적으로 다르다.

결론적으로 LLM은 조건적 분기 조건을 충족하지 못한다.

무한 저장 공간

순수한 LLM은 입력을 받아 고정된 Parameter 기반 연산을 통해 결과 값을 반환 할 뿐 별도로 새로운 정보를 저장하거나 내부 상태를 업데이트 할 수 없다.

이는 곧 만약 LLM의 Parameter 혹은 Context Window 를 이론적으로 무한히 늘린다 하여도 실질적으로 외부 혹은 직접 산출해낸 정보를 별도로 저장 혹은 수정 할 수 있는 저장공간이 없다는 것이다.

참고로 Context Window 는 일시적 입력일 뿐 지속(Persistence) 가능한 저장 공간은 아니라는 점을 유의하길 바란다.

결론적으로 순수한 LLM은 무한 저장 공간 조건도 충족하지 못한다.

결론

순수한 LLM은 튜링 완전하기 위한 최소 조건 두가지를 모두 충족하지 못하므로 튜링 완전성을 갖지 못한다.

하지만

보편적으로 사용하는 LLM은 기본적으로 외부 메모리와 외부 도구들을 사용하고 있기에 느슨한 의미에서는 튜링 완전하다라고 할 수 있다.

느슨한 의미에서 튜링 완벽하다는 의미는 아래와 같다.

나는 결정론적 튜링 완전성을 기준으로 LLM이 튜링 완전하지 못하다고 추론하였지만 확률적 튜링 완전성을 기준으로 추론한다면 보편적으로 사용하는 LLM은 외부 메모리를 이용해 무한 저장 공간 조건을 이론적으로 충족 시킬 수 있고 LLM 또한 확률적 튜링 머신과 같이 동작 할 수 있기에 튜링 완전하다고 할 수 있다.

결론

전제에 따라 LLM의 튜링 완전성은 성립할수도 있고 아닐수도 있다.

개인적으로 추후 LLM이 더욱 발전하여 확률적이라고는 하지만 기계적 연산과 동일한 수준으로 결과를 반환할 수 있다면 그건 비/결정론적 튜링 머신과 다를바가 없지 않을까라는 생각이 들기도 한다.

제 식견이 모자라 오류가 존재할수도 있으니 메일로 피드백을 주신다면 반영하도록 하겠습니다.

Day-62

tech