Turing machine (튜링 머신)

안녕하세요. 그린입니다 🍏

이번 포스팅에서는 iOS가 아닌 좀 더 컴퓨터의 근간인 튜링 머신에 대해 한번 알아보려합니다!

 

일단, 튜링 머신이라하면 생소하신분이 정말 많으실것 같아요.

사실상 우리가 사용하는 스마트폰도 컴퓨터의 일종이고 그 컴퓨터의 원리는 튜링 머신의 개념과 원리에서 이어집니다.

 

즉, 튜링 머신이 근간이라는거죠 😉

 

그렇기에 이번 포스팅에서는 그냥 제가 재밌어서 해보고 싶은 공부인 튜링 머신에 대해 자세히 정리해볼까 합니다!

 

먼저 튜링 머신을 알기전에 앨런 튜링이라는 사람에 대해 알아봐야 합니다 🙋🏻

---

앨런 튜링

다들 혹시 이미테이션 게임이라는 영화 보셨나요?

간략한 내용은 2차 세계 대전에서 독일군이 글자 배열을 바꿔 무한대에 가까운 암호 조합을 만들어내는 애니그마를 사용하여 연합군이 곤욕을 치루는데요.

여기서 이 암호를 해독하기 위해 연합군에 천재 수학자인 앨런 튜링을 암호 해독팀에 선발하고 앨런이 애니그마 해독을 위해서 특별한 기계를 발명하게 됩니다.

 

여기 나오는 주인공인 앨런 튜링 역을 오이형인 베네딕트 컴버배치가 했습니다!

뭔가 영화 홍보같긴 하지만 그건 아니고 앨런 튜링이라는 사람을 이해하는데 글로 어렵다면 영화로도 보시는걸 추천합니다 👍

넷플에 있던데... 재밌습니다ㅎㅎ

 

이미테이션 게임 중 한장면

 

즉 우리는 여기서 앨런 튜링이라는 사람이 최초의 컴퓨터 개념을 탄생시킨 사람이라는것을 알고 있어야 합니다.

 

앨런 튜링의 유년 시절이나 뭐 그런 일대기는 좀 접어두고 오늘 알아볼 튜링 머신에 관련한 부분들만 한번 꺼내서 소개해볼께요!

(근데 인생 자체가 너무 화려해서... 위키 보시면 소설처럼 재밌으실 거에요.)

 

튜링은 처음 영국 케임브리지 대학을 다녔는데, 그때 <On Computable Numbers, with an Application to the Entscheidungsproblem> 이라는 논문을 발표합니다.

이는 곧 튜링 머신 이론과 폰 노이만형 컴퓨터에 있어서 이론적인 토대를 제공했습니다.

여기서 튜링 머신은 밑에서 자세히 설명하고~

 

중요한건 케임브리지에서 수학과 석사를 수료하고 미국 프린스턴 대학에서 수학과 박사 과정을 거치게 됩니다.

이때, 중요한 인물인 존 폰 노이만과 친분을 쌓게 됩니다.

폰 노이만 많이 들어보셨죠!?

 

컴퓨터의 구조를 배울때 폰 노이만과 하버드 구조가 나오고 현재까지 사용되고 있어 친근한 이름입니다 😀

 

그리고 여차저차 이미테이션 게임에서 나왔듯이 종전 후 영국 최초로 폰 노이만형 컴퓨터인 프로그램 내장형 컴퓨터 구조에 대한 논문을 발표합니다.

 

그리고 1950년에는 인공지능에 대한 논문인 <Computing machinery and intelligence 계산 기계와 지능>을 발표해요.

이때는 사실 인공지능이란 개념 자체가 없었을 때인데 인공지능을 고안하고 광범위하게 사용될거란 예측을 한것이죠.

논문 속에서도 현재 튜링 테스트라 불리는 인공지능 실험을 제안하죠.

 

즉, 어떻게 보면 인공지능의 시초라고 볼 수 있습니다 🤖

 

여기까지 간단히 앨런 튜링이라는 인물에 대해 간략히 알아봤습니다!

 

그럼 튜링 머신으로 바로 넘어가기전에 우리 하나 더 중요한 폰노이만 구조에 대해서 간략히 역사적으로 오해하고 있는것과 설명을 짚어볼께요 🥲

(그냥 이번 포스팅은 제가 알아보고 싶은거 두서없이 알아보는중 ☺️)

 

---

폰노이만 구조

폰 노이만이 제시한 컴퓨터 구조로 프로그램 내장 방식으로도 불리며 현재 컴퓨터의 모든 구조에서 CPU 외부에서 이 구조를 사용합니다.

즉 간단히는 메모리가 1개로 명령어 + 데이터 메모리를 한곳에서 처리하는 구조입니다.

명령어 메모리와 데이터 메모리가 별도로 메모리 2개로 있는 하버드 구조보다는 속도가 느리지만 값이 쌉니다.

다만 메모리 속박 및 버스 병목 문제를 가집니다.

 

폰 노이만 구조는 이론상 튜링 머신과 같은 일을 합니다.

폰 노이만 구조가 나오기전 컴퓨터들은 스위치를 이용해 전선을 연결해 데이터를 전송하고 신호를 처리하는 식으로 프로그래밍을 했습니다.

폰 노이만 구조는 CPU / 메모리 / 프로그램 이 세가지 구성 요소로 이뤄져있습니다.

 

그럼 한번 어떤 역사적 오해가 있는지 살펴볼까요?

 

우리는 최초의 컴퓨터라고 불리는 에니악(ENIAC)을 알고 있거나 들어봤을겁니다!

근데 이 에니악을 만든 인원은 모클리와 에커트라는 사람이 개발했고 이들은 이 후 EDVAC을 설계하면서 프로그램을 기억장치에 저장 및 명령을 로드하는 방법을 연구했죠.

 

근데 폰 노이만이 이때 에니악 제작에 뛰어들면서 에드박에 관한 보고서를 씁니다.

이 보고서를 폰 노이만에게 에니악을 소개시켜준 사람이 배포해버리게 되죠.

여기서 문제는 보고서에 폰 노이만의 이름밖에 없었다는점입니다 🥲

그래서 이 보고서에 있는 에니악의 설계 때문에 모클리와 에커트의 에니악 특허도 무효가 되어 버립니다.

그리고, 폰 노이만은 폰 노이만 구조의 제창자로 유명세를 날리게 되죠ㅠㅠ

 

그렇기에 사실은 폰 노이만 구조가 아니라 에커트 구조로 불려야된다고 주장하는 사람들도 많습니다 😱

 

어쨋거나 현재 공식적인건 폰 노이만 구조라는 이름이기에 우리도 폰 노이만이라고 칭하죠!

 

이러한 비화들 이후에 폰 노이만 보고서를 통해 내장 프로그램 방식인 에드삭이 만들어졌습니다.

즉, 많은 사람들이 폰 노이만이 에드박과 에드삭을 만들었다고 잘못 인식하고 있습니다.

(불쌍한 모클리와 에커트.......... 🥲)

 

여튼 이 편의성들 덕분에 현재까지도 클라우드 컴퓨팅 같이 네트워크가 필수인 구조를 제외하고 거의 모든 컴퓨터들은 이 폰 노이만 구조를 따르고 있죠.

 

그럼 이어서 오늘의 하이라이트!!! 튜링 머신을 알아보겠습니다 ⭐️⭐️⭐️

---

Turing machine (튜링 머신)

지금까지 글을 쭉 읽어 내려오셨다면 튜링 머신은 앨런 튜링이 만든것을 알 수 있습니다.

튜링 머신은 1936년에 앨런 튜링이 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계이며 오토마타의 일종입니다.

 

초기에는 automataic machine이라고 해서 a-machine이라고 불렸는데 후에 앨런 튜링의 이름을 따 튜링 머신이라고 불리게 되었죠.

 

튜링 머신은 아래와 같은 장치들로 구성이 되어 있습니다.

 

1️⃣ Tape: 일정한 크기의 셀들로 나눠져있는 종이 테이프로 각 셀은 기호가 기록되어 있고 길이는 무한히 늘어날 수 있습니다.

2️⃣ Head: 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드를 의미하여 이동이 가능하죠. 헤드는 고정되어 있고 테이프가 이동합니다.

3️⃣ State register: 상태 기록기라고 불리며 현재 튜링 머신의 상태를 기록하고 있는 장치로 Start state와 Halt State로 구분됩니다.

4️⃣ Action table: 행동표라고 불리며 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시합니다.

 

즉 튜링 머신에서 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 갯수는 유한해야하며 서로 구분되어야 합니다.

 

튜링 머신은 이런 개념을 가지고 있고 현대 사용하고 있는 폰 노이만 구조는 보편 튜링 머신이라는 개념을 채택합니다.

 

이 보편 튜링 머신에 대해서 한번 살펴보죠!

---

Universal Turing Machine (보편 튜링 머신)

튜링 머신은 행동표에 적힌 규칙에 따라서 할 수 있는 일이 이미 정해져 있지만 모든 일을 다 처리할 수 있는 기계를 원하게 되고 결국 보편 튜링 머신이라는 개념이 나오게 되었습니다.

 

즉 보편 튜링 머신은 하나의 튜링 머신이면서 다른 임의의 튜링 머신을 시뮬레이션할 수 있죠.

이것들은 모두 행동표에 해당하는 내용을 테이프에 적어놓음으로 가능합니다.

 

간단히 튜링 머신의 개념과 동작을 절차화하면 이렇게 표현되죠.

 

👉🏻 현재 상태가 1이고 기호 A를 읽었을땐 B를 기록하고 정지

👉🏻 현재 상태가 1이고 기호 B를 읽었을땐 오른쪽 한칸 이동 후 상태 2 변경

👉🏻 현재 상태가 2이고 기호 C를 읽으면 오른쪽 한칸 이동

 

이런식으로 모든것이 짜여져 있는것입니다.

 

이 보편 튜링 머신을 바탕으로 만든 계산기계가 바로 폰 노이만 구조 컴퓨터로 프로그램 내장형 컴퓨터 개념의 시초가 되는 아주 중요한 녀석이죠 🔥

 

그럼 컴퓨터와 튜링 머신은 어떤 관계가 있을까요?

---

튜링머신과 컴퓨터의 관계

현대의 컴퓨터들은 모두 폰 노이만 구조로 되어 있는데 모두 보편 튜링 머신 개념을 따르고 있습니다.

즉 모든 컴퓨터의 동작을 포함하는 큰 집합이 보편 튜링 머신이죠.

명령어 메모리와 데이터 메모리가 분리된 하버드 구조는 테이프를 두개 달아놓은 튜링 머신이라고 생각할 수도 있습니다.

즉, 결국 정리하면 모든 컴퓨터의 구조는 이 튜링 머신 이론을 활용한것이죠..!

 

---

정리

결국 iOS 개발뿐 아니라 클라이언트 개발이라는것을 대입해보자면, 우리는 화면 즉 컴퓨터에 보여질 상태값을 변경함으로 모든 동작을 완성해냅니다.

 

그렇기에 우리가 앱 개발을 할때에도 근본적으로 들어가서 치중해야할것은 이 상태 관리라는 개념입니다.

 

어떻게 상태를 변경하여 기능을 구현할것인지가 가장 핵심적이고 원초적인 근간인것이죠.

 

앱 개발에서 가장 중요한 개념과 원초적인게 뭘까? 라는 고민으로 여기까지 점차 파고들어온것 같은데 재밌는 학습이였습니다 😉

 

이렇게 글로만은 이해가 잘 되지 않을 수 있어 강의 하나를 추천드립니다.

 

 

서울대 이광근 교수님이 강의하신 튜링 머신에 대한 이해 강의가 유튜브에 아주 잘 나와있습니다!

정말 정말 많은 도움이 되고 훨씬 쉽고 잘 설명해주시기에 더 관심이 있으신분은 보셔도 좋을것 같습니다 😀

 

---

레퍼런스

https://namu.wiki/w/앨런%20튜링

앨런 튜링 - 나무위키

https://namu.wiki/w/폰노이만%20구조?from=폰%20노이만%20구조 

폰노이만 구조 - 나무위키

https://namu.wiki/w/튜링%20머신

튜링 머신 - 나무위키