튜링 기계 - 위키백과, 우리 모두의 백과사전 튜링 기계 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 인공지능의 정도를 판별하는 테스트에 대해서는 튜링 테스트 문서를 참조하십시오. 튜링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계 ( 영어 : Turing machine ) 는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고 [ 1 ] 이 장치에 영어 단어인 automatic의 a를 따서 " a - 기계 " 라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다. 1948년 " 똑똑한 기계 " 라는 글에서 앨런 튜링은 자신의 " a - 기계 " 를 간결히 정의하였다. 1936년 논문 " 계산 가능한 수와 결정성 문제에의 응용 " 을 언급하며 튜링기계 ( 이 글에서는 논리적 계산 기계라는 표현을 사용한다. ) 를 다음과 같이 기술하
히 정의하였다. 1936년 논문 " 계산 가능한 수와 결정성 문제에의 응용 " 을 언급하며 튜링기계 ( 이 글에서는 논리적 계산 기계라는 표현을 사용한다. ) 를 다음과 같이 기술하였다. "... 무한한 저장공간은 무한한 길이의 테이프로 나타나는데 이 테이프는 하나의 기호를 인쇄할 수 있는 크기의 정사각형들로 쪼개져있다. 언제든지 기계속에는 하나의 기호가 들어가있고 이를 " 읽힌 기호 " 라고 한다. 이 기계는 " 읽힌 기호 " 를 바꿀 수 있는데 그 기계의 행동은 오직 읽힌 기호만이 결정한다. 테이프는 앞뒤로 움직일 수 있어서 모든 기호들은 적어도 한번씩은 기계에게 읽힐 것이다. " - ( 튜링, 1948, p. 61 ) 목차 1 개론 2 정의 2. 1 튜링 기계를 실행하거나 실체화하기 위해 필요한 추가적인 요소 2. 2 다른 정의들 2. 3 상태 2. 4 튜링 기계의 " 상태 " 모식도 3 튜링 머신과 동치인 다른 모델들 4 범용 튜링 기계 5 실제 기계와의 비교 5. 1 튜링 기계의 한계 ( 시간 복잡도 이론 ) 6 역사 6. 1 역사적 배경 : 계산 기계 6. 2 판정문제 6. 3 앨런 튜링의 a - 기계 6. 4 1937 - 1970 :
전자 컴퓨터를 현재의 튜링 기계인'컴퓨터와 같은 이론적 오브젝트'로 환원시켜 생각했다. 1950년대 후반에서 1960년대 초반에 멜자크와 레벡 ( 1961 ), 민스키 ( 1961 ), 셰퍼슨과 스터기스 ( 1961 ) 등의 유럽 연구자들은 일련의 연구들을 통해 튜링 기계를 좀 더 친숙하고 컴퓨터와 같은'셈 기계 counter machine'로 만들었다. 이후 1970년대 초반에는 엘곳과 로빈슨 ( 1964 ), 할트마니스 ( 1971 ), 쿡과 렉하우 ( 1973 ) 등은 이 연구를 진척시켜'기록 기계 register machine'와 RAM의 모델로 발전시켰다. 1970 - 현재 : 계산 모델로서의 튜링 기계 [ 편집 ] 오늘날의 셈 기계, 기록 기계, 그리고 RAM은 그 근간을 튜링 기계에 두고 있으며, 수많은 연구자들은 계산 이론을 풀어나가는 데에 있어서 튜링 기계를 사용한다. 특히 계산 복잡도 이론의 경우 튜링 기계의 사용이 필수적이다. 같이 보기 [ 편집 ] 확률적 튜링 기계 양자 튜링 기계 교대 튜링 기계 범용 튜링 기계 ( UTM, en : Universal Turing machine ) 참고 [ 편집 ] ↑ 1935년 중반, 막스 뉴만은 그의 강의에서
고 있다는 사실이 증명되었다 ( 홉크로프트와 울만, p. 159, cf Minsky ( 1967 ) ( 1967 ) ). 그 기계들이 더 높은 속도와 적은 저장 공간을 가질지언정, 범용 튜링 기계보다 더 많은 수학적 함수들을 계산 할 수는 없다는 것이다. ( 처치 - 튜링 명제는 모든 기계가 이러한 법칙을 따를 것이라고 주장한다. 즉 모든 계산 가능한 문제는 튜링 기계로 계산할 수 있으며, 그 역 역시 성립한다는 의미이다. ) 몇 개의 다른 모델들도 튜링 기계와 동일한 계산 능력을 가지고 있다는 것이 밝혀졌다. 그중에는 다중 테이프 튜링 기계, 다중 트랙 튜링 기계, 입력과 출력이 있는 튜링 기계, 비결정론적 튜링 기계등이 있다. 범용 튜링 기계 [ 편집 ] 튜링은 미결정성에 다음과 같이 적었다. " 계산 가능한 수열을 계산하는 단일 기계를 만들 수 있다. 만약 이 기계 U에 들어온 테이프의 처음 부분이 어떤 계산기계 M이 처리한 세미콜론 ( ; ) 으로 분할된 5 - 튜플이라면 U는 M과 똑같은 계산 과정을 거치게 된다. " 지금은 이 발견이 당연하다고 생각하지만 그 당시 ( 1936 ) 로서는 정말 놀라운 발견이었다. 일부
sive Unsolvability of a Problem of Thue ", Journal of Symbolic Logic, vol. 12, pp. 1 - 11. 해독불가능에 대해서 재출판됨. pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936 - 1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on Turing's first and second proofs. 튜링, A. M. ( 1936 ). " 계산가능수와 결정문제에 대한 응용에 관하여 ". 《 런던수학회지 》. 2 ( 1937 ) 42 : 230 - 65. doi : 10. 1112 / plms / s2 - 42. 1. 230. ( and 튜링, A. M. ( 1938 ) ( 1938 ). " 계산가능수와 결정문제에 대한 응용에 관하여 : 수정판 ". 《 런던수학회지 》. 2 ( 1937 ) 43 ( 6 ) : 544 - 6. doi : 10. 1112 / plms / s2 - 43. 6. 544. ). Rep
종류 최종 ( 다음 ) 상태 5투플 표현 A 0 1 R B ( A, 0, 1, R, B ) 1 1 L C ( A, 1, 1, L, C ) B 0 1 L A ( B, 0, 1, L, A ) 1 1 R B ( B, 1, 1, R, B ) C 0 1 L B ( C, 0, 1, L, B ) 1 1 N H ( C, 1, 1, N, H ) 다음 표에서 볼 수 있듯이, 튜링의 본래 모델은 N1, N2, N3라고 불리는 세 가지의 행동만을 허용했다. 예를 들어, 읽혀진 구간의 지우기를 0번째 기호인 S0 = " 지움 " 또는 " 비어있음 " 등으로 표현하는 것은 허용했으나 아무것도 쓰지 않는 것은 허용하지 않았기 때문에 모든 행동에는 " 기호 Sk를 인쇄한다 " 또는 " 지운다 " 라는 명령이 포함되어 있었다. 약어들은 튜링이 만든 것인데, 튜링의 원문이 나온 이후 기계 모델은 9가지의 5투플을 포함하고 있다. 현재 m - 배형 ( 튜링 상태 ) 테이프 기호 인쇄 테이프 행동 최종 m - 배형 ( 튜링 상태 ) 5투플 5투플 주석 4투플 N1 qi Sj Print (
스터를 호출하는 것이 가능하다. 메모리 인덱스를 이용한 연산의 최적화가 튜링 기계에서는 불가능하므로 튜링 기계로 모델링 할 때 일부 알고리즘에 대해서는 시간복잡도의 잘못된 하한을 줄 수 있다. 예를 들어 이진 검색 알고리즘의 경우 튜링 기계 모델보단 RASP 모델로 훨씬 더 빠르게 연산이 가능하다. 역사 [ 편집 ] 알고리즘, 처치 - 튜링 명제 문서를 참고하십시오. 역사적 배경 : 계산 기계 [ 편집 ] 앨런 튜링 ( 1912 - 1954 ) 의 제자이자 평생의 친구인 로빈 간디 ( 1919 - 1995 ) 는'계산 기계 ( calculatng machine )'의 관념의 기원을 배비지에서 찾았으며 실제로 배비지 이론을 제안했다. 간디는 배비지의 해석 기관을 다섯 개의 연산으로 묘사했다. 산술적 함수, -, x ( 이 때의 - 는 [UNK] 일 때 x - y = 0이 되는 적절한 [UNK]. ) 그 어떤 일련의 연산도 하나의 연산으로 표현될 수 있다. 반복 ( 연산 P를 n번 반복 ) 조건부 반복 ( 시험 T가 성공한다는 조건 하에 연산 P를 n번 반복 ) 조건부 이동 ( 결과값에 따라 계산 순서가 변경 ) 간디는 1, 2, 4에 의해 계산될 수 있는 함수를 계산 가능한 함수로 정의했다.
간다 " 와 같이 유한한 개수의 기초적 지시문으로 이루어진다. 원문 ( " 계산가능수와 결정문제에 대한 응용에 관하여On computable numbers, with an application to the Entscheidungsproblem " ) 에 따르면 튜링이 상상한 것은 이러한 연산을 특출하게 수행할 수 있는 " 컴퓨터 " 라 불릴 사람이었다. 더 자세히 설명하자면, 튜링 기계는 다음과 같은 부분들로 구성되어 있다. 테이프 : 테이프는 서로 연속한 단위 구간들로 나뉜다. 각각의 구간은 알파벳을 가지고, 특정 알파벳은 비어있음을 나타낸다. 테이프는 왼쪽이나 오른쪽으로 임의적으로 확장될 수 있으며, 한번도 쓰이지 않은 구간은 비어있다는 기호로 표시된다. 어떤 테이프는 왼쪽을 고정시키고 오른쪽을 무한히 확장시키는 반직선의 형태로 되어있다. 머리 : 기계가 머리를 읽으면 테이프를 왼쪽이나 오른쪽으로 한 칸 ( 오직 한 칸만 ) 이동시키는 역할을 한다. 다른 모델에서는 머리가 움직이고 테이프가 고정되기도 한다. 상태 기록기는 튜링 기계의 유한히 많은 상태 중 하나를 기록한다.'개시 상태'는 상태 기록기를 초기화시키는 특별한 상태이다. 유한한 표 ( 또는 행동표 ) 는 특정
확률적 튜링 기계 양자 튜링 기계 교대 튜링 기계 범용 튜링 기계 ( UTM, en : Universal Turing machine ) 참고 [ 편집 ] ↑ 1935년 중반, 막스 뉴만은 그의 강의에서 " 과연 수학적 표현에 적용되어 그 표현이 증명될 수 있는지를 알려주는 명확한 방법이 ( 뉴만은 이를 기계적 과정이라고 표현하였다. ) 존재하는가 " ( 호지스 1983 : 93 ) 라는 질문을 던졌다. 이 강의를 들고 튜링은 그 가상의 장치를 생각해내었다고 한다. ( 더 자세한 사실은 역사부분을 참조하시오 ) 그는 이 논문을 런던 수학회지에 1936년 5월 31일에 제출하였으나 ( 참고 : 호지스 1983 : 112 ), 정작 이 논문이 출판된 것은 1937년 초였고, 그 해 2월이 다 돼서야 발췌 인쇄가 가능해졌다. ( 참고 : 호지스 1983 : 129 ) 참고 문헌 [ 편집 ] 1차 저서, 재출판, 편집 [ 편집 ] B. Jack Copeland ed. ( 2004 ), The Essential Turing : Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enig
기계와의 비교 5. 1 튜링 기계의 한계 ( 시간 복잡도 이론 ) 6 역사 6. 1 역사적 배경 : 계산 기계 6. 2 판정문제 6. 3 앨런 튜링의 a - 기계 6. 4 1937 - 1970 : 디지털 컴퓨터, 그리고 컴퓨터 과학의 탄생 6. 5 1970 - 현재 : 계산 모델로서의 튜링 기계 7 같이 보기 8 참고 9 참고 문헌 9. 1 1차 저서, 재출판, 편집 9. 2 계산 이론 9. 3 처치 - 튜링 명제 9. 4 작은 튜링 기계 9. 5 기타 10 외부 링크 개론 [ 편집 ] 튜링 기계는 수학적 모형의 일종으로, 특수한 테이프를 기반으로 작동하는 기계이다. 튜링 기계가 사용하는 테이프 위에는 테이프 머릿기호를 바탕으로 기계가 인식하거나 기록할 수 있는 기호들이 있다. 작동 방식은, " 42번째 상태에서 0이라는 기호가 있다면 1을 쓴다. 1이라는 기호가 있다면 17번째 상태로 간다. 17번째 상태에서 0이라는 기호가 있다면 1을 쓰고, 1이라는 기호가 있다면 6번째 상태로 간다 " 와 같이 유한한 개수의 기초적 지시문으로 이루어진다. 원문 ( " 계산가능수와 결정문제에 대한 응용에 관하여On computable numbers, with an application to the Entsche
수학 또는 이론 전산학에서 튜링 기계(영어: Turing machine)는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고 이 장치에 영어 단어인 automatic의 a를 따서 "a-기계"라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다. 1948년 "똑똑한 기계"라는 글에서 앨런 튜링은 자신의 "a-기계"를 간결히 정의하였다. 1936년 논문 "계산 가능한 수와 결정성 문제에의 응용"을 언급하며 튜링기계(이 글에서는 논리적 계산 기계라는 표현을 사용한다.)를 다음과 같이 기술하였다.