컴퓨터의 근본 원리가 된 finite state machine 개념 익히기

1. definition

 

특정 input을 받으면 현재 상태에서 특정 상태로 변화하는 일종의 machine

 

컴퓨터 작동의 기본 원리

 

동그라미 2개 된 곳은 terminal state

 

finite state machine 예시 그림

 

input을 받으면 S1에서 시작하고 a를 주면 S2로 간다는 뜻이 아니라 S1에서 a를 받으면 S2로 가는것

 

S2에서 b를 받으면 S1으로 가는 것이고 c를 받으면 S4(terminal state)로 가는것

 

 

2. example - theory of computation

 

모든 computing 연산은 finite state machine로 나타낼 수 있다.

 

 

input state에서 algorithm, time, space 등을 받으면 output state로 변화하는 computing 연산

 

 

3. example - database

 

database에서 새로 create하여 database를 만든다거나 새로운 database를 읽는다거나 새로운 내용을 update한다거나 내용을 지운다거나하면 새로운 database 상태로 변화

 

 

현재 database에서 create, read, update, delete 등 각종 operation을 받으면 새로운 database로 상태 변화

 

4. example - security

 

현재 message에서 code rule에 의해 새로운 message로 상태변화하고 inverse rule에 의해 원래 message로 복원되는 과정

 

code rule이 외부에 알려지지 않은 encoding을 encrypt라 하고 이 경우 복원 과정을 decrypt라고 부름

 

당연하지만 rule을 모르니 decoding(decrypt)을 아무나 할 수 없게 됨

 

encrypt도 compression처럼 encoding의 subset 개념이다.

 

 

현재 message에서 code rule을 받아 encrypt를 하면 새로운 message로 상태변화

 

 

5. example - network

 

client가 server에 request를 하면 server는 client의 request에 따라 상태를 업데이트

 

server는 HTTP 같은 약속에 의해 update가 되었다는 것을 client에게 알린다는 의미로 response

 

response를 받은 client는 다시 request하여 위 과정을 반복함

 

 

client가 request를 하여 server의 상태 변화를 일으키며 server는 response로 업데이트 되었다는 것을 client에게 알림

 

 

6. example - operating system

 

hardware에 의해 정보를 받은 operating system이 application 상태를 변화

 

application 상태 변화 정보가 operating system에 전달되면 operating system이 hardware를 update하는 과정을 반복함

 

operating system의 상호작용

 

7. example - machine learning

 

model의 underfit 상태에서 train을 진행하면 overfit 상태로 가고 overfit 상태에서 regularization을 통해 underfit 상태로 변화시킨다.

 

underfit과 overfit의 중간쯤에 존재하는 optimal한 상태를 얻고자 하는 것이 machine learning

 

 

machine learning의 training도 사실 finite state machine의 일종

 

 

8. example - coding

 

(프로그래밍) 언어가 어떻게 조합되느냐에 따라 program이 될 수 있고 machine이 될 수 있고 program이나 machine의 output이 될 수 있고

 

program이 compile을 통해 machine이 될 수도 있고

 

 

coding하는 과정 자체가 finite state machine가 될 수 있다.

 

neural network가 data input을 받아 task를 수행하여 output을 내는 과정도 하나의 encoding 과정이며(decoding은 불가능한..??) finite state machine이다.

 

neural network도 하나의 finite state machine이다.

 

neural network는 그 자체로 거의 항상 input data의 dimension을 compression하여 output data로 상태 변화 시킨다.

 

network나 data나 벡터 공간 위의 점들의 집합이고 점들의 집합이 어떻게 조합되느냐에 따라 weight의 모임인 network가 되고 혹은 input data가 되고

 

 

 

neural network는 input data의 차원을 압축시켜 output data로 만든다

 

network(=set of weight)나 data나 벡터 공간 위 점들의 조합이다.

 

 

9. example - entropy

 

정보가 없는 무질서한 high entropy 상태에서 정보가 들어와 정보가 반영된 상태인 low entropy로 변화하는 것도 finite state machine

 

이 entropy 변화를 구현한 것이 machine learning model

 

 

entropy의 변화도 finite state machine의 일종