"튜링 머신"의 두 판 사이의 차이

주합루 오픈 위키
둘러보기로 이동 검색으로 이동
 
(같은 사용자의 중간 판 2개는 보이지 않습니다)
14번째 줄: 14번째 줄:


   Halting Problem
   Halting Problem
  임의의 튜링 머신과 인풋이 있을 때, 이것이 멈출 것인가를 결정할 수 있는 튜링 머신은 없다.
  Halting problem은 결정 또는 판정 문제의 하나이다. Decision problem
  튜링 머신에서 Circuit과의 관련성이 나오고 Computational complexity가 나온다.
  [[Computational Complexity]]

2022년 10월 13일 (목) 23:31 기준 최신판

 튜링 머신이란, input tape에 0,1 정보가 저장되어 있고
 이 정보와 내부 상태를 argument로 하는 머신의 산출값이 (output)과 (tape moving)의 정보이다.
 f( input, state ) = (output, tape moving)
 output으로 input을 대체하고 테이프 리더의 위치를 tape moving의 정보를 통해 이동한다.  (tape moving)= R, L, Stay (output)=(0, 1)


 U라는 튜링머신은, M이라는 튜링 머신의 룰을 잘 가지고 있어서
 U( M, x ) = M(x)의 결과를 잘 만든다.
 이 튜링머신을 유니버설 튜링머신이라고 한다.
 Non-computibility : 전산불가능이라는 말은 어떤 함수가 튜링머신으로 계산할 수 없을 때를 말한다.


 Halting Problem
 임의의 튜링 머신과 인풋이 있을 때, 이것이 멈출 것인가를 결정할 수 있는 튜링 머신은 없다.
 Halting problem은 결정 또는 판정 문제의 하나이다. Decision problem
 튜링 머신에서 Circuit과의 관련성이 나오고 Computational complexity가 나온다.
 Computational Complexity