튜링 기계 - 위키백과, 우리 모두의 백과사전 튜링 기계 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 인공지능의 정도를 판별하는 테스트에 대해서는 튜링 테스트 문서를 참조하십시오. 튜링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계 ( 영어 : Turing machine ) 는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고 [ 1 ] 이 장치에 영어 단어인 automatic의 a를 따서 " a - 기계 " 라는 이름을 붙였다.
를 대표할 수 있는 가상의 장치를 만들었고 [ 1 ] 이 장치에 영어 단어인 automatic의 a를 따서 " a - 기계 " 라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다. 1948년 " 똑똑한 기계 " 라는 글에서 앨런 튜링은 자신의 " a - 기계 " 를 간결히 정의하였다. 1936년 논문 " 계산 가능한 수와 결정성 문제에의 응용 " 을 언급하며 튜링기계 ( 이 글에서는 논리적 계산 기계라는 표현을 사용한다. ) 를 다음과 같이 기술하였다. "... 무한한 저장공간은 무한한 길이의 테이프로 나타나는데 이 테이프는 하나의 기호를 인쇄할 수 있는 크기의 정사각형들로 쪼개져있다. 언제든지 기계속에는 하나의 기호가 들어가있고
모순을 포함하지 않는가 수학은 결정 가능한가 첫 번째와 두 번째 문제는 1930년 쿠르트 괴델에 의해 해결되었으나, 세 번째 문제는 1930년대 중반까지 해결되지 않았다. 앨런 튜링의 a - 기계 [ 편집 ] 1935년 봄, 케임브리지 킹스 칼리지의 젊은 박사 과정 학생이었던 튜링은 한 과제에 직면했다. 그는 논리학자 뉴먼의 강의에 자극을 받았으며, 결정 문제에 대한 괴델의 연구에 대해서 알게 되었다. 뉴먼은'기계적'이라는 단어를 사용했으며, 1955년 튜링의 부고에 뉴먼은 다음과 같이 기술했다. "'기계적'과정이란 무엇인가'라는 질문에 튜링은'기계로 할 수 있는 것'이라는 답을 내놓았다. - Gandy, p. 74 튜
있듯이, 튜링의 본래 모델은 N1, N2, N3라고 불리는 세 가지의 행동만을 허용했다. 예를 들어, 읽혀진 구간의 지우기를 0번째 기호인 S0 = " 지움 " 또는 " 비어있음 " 등으로 표현하는 것은 허용했으나 아무것도 쓰지 않는 것은 허용하지 않았기 때문에 모든 행동에는 " 기호 Sk를 인쇄한다 " 또는 " 지운다 " 라는 명령이 포함되어 있었다. 약어들은 튜링이 만든 것인데, 튜링의 원문이 나온 이후 기계 모델은 9가지의 5투플을 포함하고 있다. 현재 m - 배형 ( 튜링 상태 ) 테이프 기호 인쇄 테이프 행동 최종 m - 배형 ( 튜링 상태 ) 5투플 5투플 주석 4투플 N1 qi Sj Print ( Sk ) Left L qm
" 지금은 이 발견이 당연하다고 생각하지만 그 당시 ( 1936 ) 로서는 정말 놀라운 발견이었다. 일부 학자들은 튜링이 범용 기계 ( Universal Machine ) " 이라고 부른 이 계산 모델이 프로그램 내장식 컴퓨터를 위한 기초적인 이론적 해결책을 제시했다고 생각한다. " 튜링의 논문은... 기본적으로 현대 컴퓨터와 관련된 일부 프로그래밍 기술의 발견을 서술하고 있다. " - 민스키 ( 1967 ) p. 104 계산복잡도의 측면에서 보면 다중테이프 튜링 기계는 이 기계가 시뮬레이트하는 기계에 비해 로그 인수만큼 느려야 한다. 이 결과는 1966년에 F. C. 헨리와 R. E. 스턴에의해 얻어졌다. ( 아오라와 바락, 2009, 정리 1. 9 ) 실제 기계와의 비교 [ 편집 ] 흔히들 튜링 기계는 다른 오토마타와 다르게
] 튜링 기계를 설명하는 데 있어서 상태라는 말은 두 가지의 뜻을 가진다. 대부분의 경우는 현재 지시의 이름이나 내용을 뜻한다 ( 상태 기록기에 저장된 정보 ). 하지만 튜링 ( 1936 ) 은 계산과정 상에서 기계의 m배열과 기계의 진행 상태를 확실하게 구분했다. 튜링이 " 상태식 " 이라 표현했던 것은 현재의 지시와 테이프 상의 모든 기호들을 포함한다. " 따라서 튜링 기계가 수행하는 모든 단계에서 계산의 진행 상태는 지시와 테이프의 기호에 따라 결정된다. 즉, 시스템의 상태는 테이프 위에 존재하는 기호들의 나열로 표현된 하나의 식과 지시로 표현된다. 이 식을 " 상태식 " 이라고 부른다. " - 해독불가능에 관해서, p. 139 - 140, 강조가 포함됨 튜링 기계의 " 상태 " 모식도 [
universal Turing machine FOM email list. October 26 - 27, 2007. Alasdair Urquhart, 2007 " Smallest universal machine ", FOM email list. October 26, 2007. Hector Zenil ( Wolfram Research ), 2007 " smallest universal machine ", FOM email list. October 29, 2007. Todd Rowland, 2007, " Confusion on FOM ", Wolfram Science message board, October 30, 2007. 기타 [ 편집 ] 마틴 데이비스 ( 2000 ). 《 Engines of Logic : Mathematicians and the origin of the Computer 》 1판. W. W. Norton & Company, New York.
한 길이의 테이프로 나타나는데 이 테이프는 하나의 기호를 인쇄할 수 있는 크기의 정사각형들로 쪼개져있다. 언제든지 기계속에는 하나의 기호가 들어가있고 이를 " 읽힌 기호 " 라고 한다. 이 기계는 " 읽힌 기호 " 를 바꿀 수 있는데 그 기계의 행동은 오직 읽힌 기호만이 결정한다. 테이프는 앞뒤로 움직일 수 있어서 모든 기호들은 적어도 한번씩은 기계에게 읽힐 것이다. " - ( 튜링, 1948, p. 61 ) 목차 1 개론 2 정의 2. 1 튜링 기계를 실행하거나 실체화하기 위해 필요한 추가적인 요소 2. 2 다른 정의들 2. 3 상태 2. 4 튜링 기계의 " 상태 " 모식도 3 튜링 머신과 동치인 다른 모델들 4 범용 튜링 기계 5 실제 기계와의 비교 5. 1 튜링 기계의 한계 ( 시간 복잡
es 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. ). Reprinted in
링 기계의 " 상태 " 모식도 3 튜링 머신과 동치인 다른 모델들 4 범용 튜링 기계 5 실제 기계와의 비교 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 외부 링크 개론 [ 편집 ] 튜링 기계는 수학적 모형의 일종으로, 특수한 테이프를 기반으로 작동하는 기계이다. 튜링 기계가 사용하는 테이프 위에는 테이프 머릿기호를 바탕으로 기계가
수학 또는 이론 전산학에서 튜링 기계(영어: Turing machine)는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고 이 장치에 영어 단어인 automatic의 a를 따서 "a-기계"라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다. 1948년 "똑똑한 기계"라는 글에서 앨런 튜링은 자신의 "a-기계"를 간결히 정의하였다. 1936년 논문 "계산 가능한 수와 결정성 문제에의 응용"을 언급하며 튜링기계(이 글에서는 논리적 계산 기계라는 표현을 사용한다.)를 다음과 같이 기술하였다.