1. Welcome Aboard

Computer Concept & Practice(컴퓨터 개념 및 실습)

컴퓨터에 대해서 배우기전에 개론의 역할을 하는 "Computer Concept & Practice(컴퓨터 개념 및 실습)" 수업.
컴퓨터를 처음 접하는 학생들을 대상으로 컴퓨터에 대한 일반적인 기초개념 등을 설명하고, 프로그램이 수행되는 과정과 프로그램 작성을 위한 논리적인 사고에 대하여 강의한다. 

 

 

오늘 강의에서는 전체적인 큰 그림과 2가지 정도의 주요개념을 알아보자.

우선 핵심개념 중 하나인, Abstraction(굳이 번역하면 '추상화'가 제일 나을 것 같다. 하지만 단어 그자체로 알고 있는게 좋을 것 같다.)에 대해서 배워보자. 

 

Abstraction

Abstraction은 간단하게 말하면 복잡한 구조들을 다루기 쉽게 추상화하는 것이다.
예를 들면, 아래의 그림처럼 우리는 차가 LPG이든, 디젤이든, 전기차이든 상관없이 그 원리를 몰라도 interface를 통해 운전을 할 수 있다. 
왜냐하면, 자동차는 abstraction이 되어있으니깐.

어떤 엔진을 쓰든 우리의 운전에는 큰 문제가 없다.

인간이 한순간에 다룰 수 있는 문제의 Complexity(복잡도)에는 제한이 있다.
핸들만 돌리면 자동차의 바퀴가 방향을 전환하지만, 차체안정시스템을 이용하며 바퀴가 방향전환을 하기 위한 공학적인 원리를 생각하고 휘발유가 엔진에서 이용되며 그 힘이 전달되는 것 등등등 하나하나 신경쓸려면 끝이 없다.
이러면 아무도 자동차를 운전할 수 없을 것이다.

하지만 그런 디테일한 부분들이 abstraction 되고, 또 abstraction되어 우리는 핸들과 기어봉 등의 비교적 간단한 interface로 운전을 할 수 있다.
(ex: 우린 유튜브의 원리를 몰라도, 조정이 가능하다. 유튜브 자체의 알고리즘은 엄청 복잡하겠지만, abstraction되고 또 abstraction 되어서, 우리는 간단한 interface를 통해 쉽게 이용 할 수 있다.)

정말 복잡하지만 우리는 abstraction을 이용하여 자동차를 다룰 수 있다.

그래서 우리는 abstraction을 '어떤 시스템에서 내부의 자세한 사항들을 interface로 정의하여, 그 시스템을 하나의 building block(구성요소)사용 가능하게 하는 메카니즘'이라고 생각 할 수 있다. 

그리고 이런 abstraction은 인간이 만든 것(man-made)외에도 자연에서도 찾아 볼 수 있다.
밑의 그림처럼 인간의 형성 과정도 abstraction이라고 할 수있다.

원자-분자-세포-...-인간 까지의 abstraction

생명은 뭔가 1개의 단위인 것 같지만, 결국 작은 단위에서 부터 abstraction된 것이다.
(내 분야와 연관지어 설명하자면, 우리는 근육이 어떻게 움직이는지 모르지만, action과 myosin이 어떤 기전으로 결합하는지 몰라도, 우리는 뇌라는 최고의 interface를 통해 조정이 가능하다)
*생명의 탄생과 성장 자체가 abstraction이라는 의미가 아니라, 저렇게 복잡하고 작은시스템들이 간략화되고 또 간략화되어서 우리가 움직이고 살아가는 것이 abstraction이라는 의미라고 말씀드린 것입니다.

민상렬 교수님의 말씀.
"저는 종교가 없지만, 창조주가 하는 식을 따라하면 최소한 중간이상은 간다라고 생각합니다.  그래서 창조주가 이런 계층적인 구조를 따랐으면, 우리도 abstraction을 시키면서 거기서 interface를 만들면서 그 component(요소)를 이용해서 더 큰 시스템을 구축하는 그리고 그런 과정을 계층적으로 하는 접근방식을 가지는게 좋다고 생각합니다."

 

컴퓨터의 abstraction 과정

이처럼 가장 위에서 보면 어떤 problems를 풀고 싶은 것이지만, 가장 아래로 파고들어 간다면 전자가 있을 것이다. 
ex) electron를 가지고 transistor를 만들고, 그걸 이용해 gate를 만들고, 계속해서 더 복잡한 것을 만들어나가며 ISA(Instruction Set Architecture)를 만들것이고, language를 만들고 algorithms를 만들어 problems를 해결 할 수 있을 것이다.
(*여기서 transistor가 무엇인지, gate가 무엇인지 등은 아직은 알 필요 없다. 단순히 컴퓨터가 저런 것들이 abstraction되어 problem을 해결한다는 정도만 알면된다. 저런 것들이 무엇인지는 뒤에서 자세히 배울 예정이다.)

 

Universal Computing Device

우리가 이번에 알야할 것은,
'모든 컴퓨터에 충분한 시간과 메모리가 주어진다면, 틀림없이 똑같은 것을 해낼 수 있다'는 사실이다.
(All computers, given enough time and memory, are capabel of computing exactly the same things.)

문제풀이의 파워에 있어서는 전부 차이가 없다.

당연히 어떤 문제를 스마트폰에서 푸는 것과 슈퍼컴퓨터에서 푸는 것은 차이가 있겠지만,
그것 자체를 푸는 power에는 큰 차이가 없다. 그래서 충분한 메모리와 시간이 있다면 문제를 해결 할 수 있다는 사실은 같다는 의미이다.

 

그렇다면 가장 작은 computing device는 무엇일까?

가장 작은 것은  A.M.turing가 고안해낸 수학적 모델인 turing machine이라고 볼 수 있다.
그리고 turing은 이렇게 말하기도 하였다.
'Every computation can be performed by some Turing machine'
즉, 실제 컴퓨팅 될 수 있는 것은 자신이 고안한 turing machine로도 풀 수있다고 말하였다.

우리가 위에서 스마트폰과 슈퍼컴퓨터의 문제해결power에는 차이가 없다고 배웠듯이, turing machine은 아주 간단하지만 우리가 실제로 계산가능한 어떤 문제도 풀 수 있다고 말하였다. (*물론 시간은 별개의 문제지만)

이 turing machine에는 기본 전제가 있다. (아래의 그림을 참조하자)
1. 위의 tape의 길이가 무한해야한다.
2. head는 왼쪽이나 오른쪽으로 움직일 수 있다.
3. 현재 head가 위치한 곳의 symbol 값을 read 할 수 있고, write 할 수 있다.

turing machine의 time step

그리고 이러한 time step을 거친다고 생각하면 된다.(위의 그림 참조)
head의 위치에서 read - write - move(left or right)

그래서 조금 더 이해를 돕기 위하여 Example을 살펴보면,
head가 자신의 위치에 있는 symbol인 a를 read하였고, 
거기에 대해 k라는 값을 write 했으며, 
이후 왼쪽으로 move 했다. 
(*결국엔 영어에 익숙해져야 후에 이해할 때 좋기 때문에, 최대한 영어로 적었습니다.)

그렇다면 이것으로 어떻게 computation을 할 수 있을까?

예를 들어 Cmoputable한 아래와 같은 function(함수)가 있다고 해보자.

f(x,y) = x+y (*x,y는 integers정수이다)

Turing machine에서는 이것을 unary(1진법)으로 표현한다.
(*1진법의 예: 5 = 11111, 2 = 11, 3 = 111)

Input string: x0y
Output string: xy0

(*input으로 x0y가 들어가면 일련의 과정을 거쳐 output으로 xy0이 나오는 것이다.)
더 자세한 이해를 돕기위해, 이를 그림으로 표현하면 아래와 같다.

turing machine에서 function의 computation과정

*여기서 ◇는 시작과 끝을 알리는 역할이라고 보면된다.
*head의 q옆에 숫자는 몇번째 state인지 의미한다.
*여기서 state는 번역하여 생각하기보단 그냥 state 그 자체로 받아들이는 것이 좋을 것 같다.

그림에서 start 부분을 보면,
initial state(처음 state)에서
head가 ◇옆에 위치하고, x와 y사이에 0이 위치한 모습을 볼 수 있다.
(0은 두 숫자를 나누는 delimiter(구분자)역할을 하고 있다)
이 모습이 위에서 보았던 input string인

x0y

그리고 Finish 부분을 보면,
final state(마지막 state)에서 
head가 다시 ◇옆에 위치하며, x값과 y값이 붙어있고 마지막에 0이 온 모습을 볼 수 있다.
이 모습이 위에서 보았던 output string인

xy0

unary의 특성상,
단순히 붙여서 세어주기만 하면된다는 특성을 이용한 것이다. 
위의 Example를 살펴보면, 
x=2, y=2 일때, unary으로 x=11, y=11로 표현할 수 있다.

*unary는 간단히 설명하자면 1이라는 막대기의 갯수로 숫자를 표현하는 것이다.
2는 1이란 작대기 2개 (2=unary 11)
5는 1이란 작대기 5개 (5=unary 11111)
그래서 우리는 위와 같이 add(더하기)를 할 때,
그냥 1이란 작대기 수를 합쳐서 세어버리면 되는 것이다. 
2+5 ->unary->11+11111=1111111 -> 7 

그래서 이 turing machine에서는
단순히 더하고자 하는 두 값을 0으로 구분하고,
두 값 사이의 0을 끝으로 치워버리면, 
unary로 표현된 두 값이 자동으로 add되어 버리는 것이다.

 

그림으로 표현된 turing machine에서의 과정

그렇다면 결국 우리가 turing machine을 이용해 add를 할 때 필요한 과정은
head가 처음위치에서
1이 read되면 오른쪽으로 move 반복,
0이 read되면 1을 write,
다시 1이 read되면 오른쪽으로 move 반복,
◇가 read되면 왼쪽으로 move,
이후 1이 read되면 0으로 write,
이제 1이 read되면 왼쪽으로 move 반복,
◇가 read되면 오른쪽으로 move
가 될것이다. (위의 그림 참조)
*이전 시간에 배웠던 task를 처리하는 3가지 방법(sequential, conditional, iterative)를 함께 생각해보면 좋을 듯 하다!

 

Universal Turing Machine

우리는 위에서 turing machine의 간단한 예를 살펴보았다. 
이번에는 여러가지 turing machine 중 가장 general한 universal turing machine에 대해서 알아보자.

universal turing machine의 간략한 모습

위의 그림을 보면,
input(입력)으로 받는 것이 2개인 것을 볼 수 있다.
T(add), T(mul)과 a, b, c
universal turing machine에서는 input의 하나로
add기능이나 mul(multiply곱하기)기능을 가진 turing machine을 받는다.
그리고 다른 input으로 실제 계산할 data(a,b,c 같은 것들)를 받는다고 보면 된다.
(*ex: 컴퓨터로 생각해보면 이해하기 쉽다. 컴퓨터도 단순히 값만 준다고 돌아가는게 아니라, 프로그램이 있어야 값을 줄 때 작동하는 것처럼,  turing machine이란 프로그램을 받아서 data를 처리한다고 생각하면 된다)
*어렵다면 turing machine을 시행하는 더 큰? turing machine이라고 생각해도 될 듯 하다.
A machine that can implement all Turing machines --this is also a Turing machine!

이처럼 Universal Turing machine은 임의의 Turing machine(program으로 해석할 수도 있는)을 받아들일 수 있으므로,
computer와 같이 programmable하다고 할 수 있으며, 이론적으로는 이런 turing machine을 계속해서 조합해 나가면 현재 우리가 사용하는 computer와 같은 것도 만들 수 있을 것이다.
Universal Turing machin is programmable - so is a computer!
-program is part of the input data
-a computer can emulate a Universal Turing Machine and vice versa

 

Halting Problem

우리는 위에서 turing machine을 이용해 computer가 어떤 방식으로 이루어졌는지 배웠고, 이를 통해 이론적으로는 turing machine 또한 computer 란 것을 알 수 있었다.
그렇다면 A.M.Turing이 말한 것처럼 computation이 가능하다면 모든 문제를 풀 수 있을까?

이에 대해선 유명한 Halting problem이라는 것이 있다.
우리가 기계장치들을 이용하다보면, 기계의 정상작동유무가 중요하다. 
한 마디로 기계가 후에 halting(멈춤)될지 안될지 말이다.
halting problem은 우리가 후에 '모든' 기계를 halting 될지 안될지 '정확히' 파악할 수 있는 기계를 만들 수 있냐에 대한 고민이다. 

https://youtu.be/92WHN-pAFCs

이에 대한 부분은 사고 실험을 통해 논리적으로 불가능 하다는 것이 밝혀졌는데, 자세한 내용은 위의 영상을 참조하면 이해할 수 있을 것이다.

 

*나의 생각

아주 중요한 개념인 abstraction에 대해 배울 수 있는 장이였다.
이전에 본 만화 중에 현재 netflex에도 있는 'dr.stone'라는 만화가 있다. (대략 지구가 멸망했고, 그 원흉이 달에 있어서 과학천재가 구석기 시대 부터 과학적 발전을 거듭해서 달로 향하려 한다는 내용이다.)

여기서 컴퓨터를 만드는 과정이 나온다. 여기서 이들은 현대의 컴퓨터를 흉내내기 위해 동과 아연을 섞은 금속에 전선을 감는식으로 parametron(컴퓨터의 기억,연산 소자)을 만들고, 그외 다양한 부품을 통해 간단한 turing machine를 만들어낸다. 
이후 abstraction의 과정이 나오는데, 간단한 계산 과정을 시행 할 수 있는 이러한 turing machine들을 모아 universal turing machine을 만들고 다시 이것을 몇 만개씩 만들어서 훨씬 더 복잡한 계산을 할 수 있는 turing machine, 현대의 컴퓨터에 가까운 것을 만들어낸다. 

이처럼 어떤 과정을 통해 turing machine이 computation을 할 수 있는지, 그리고 단순히 여기서 끝이 아니라 이것이 abstraction 되면 어떤 일이 일어날 수 있는지 배울 수 있는 장이라고 생각한다. 

+아무래도 haltling problem 같은 사고실험을 할 수 있는 논리력을 갖춘다면, 이후 어떤 problem을 해결하기 위해 programming 할 때, 어떤 방식으로 접근해야 하며 무엇이 가능하고 불가능한지 계획을 세우는데 큰 도움이 될 것 같다.

+abstraction의 개념으로, 인간이 뇌라는 interface를 이용하여 motor control 하는 데 있어서(물론 뇌만이 담당하는 것은 아니지만) 더 많은 아이디어를 얻을 수 있는 장이기도 했다.

 

+오늘의 영단어

complexity 복잡도
building block  구성요소
component 요소, 부품
capable of ~할 수 있는
exactly 틀림없이, 정확히
computation 계산
transition 이행
integer 정수
unary 1진법
function 함수
delimiter 구분자
implement 시행하다
description 서술, 설명
vice versa 반대도 같다, 거꾸로 해도 같다
emulate 흉내내다, 유사한 기능을 할 수 있다
halt 중단, 멈춤