. pp. 289ff. 에밀 포스트 ( 1947 ), " Recursive 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
##의 주제를 다루며 9장 튜링 기계는 재귀 이론에 대해서 조금 다루고 있다. 마틴 데이비스 ( 1958 ). 《 Computability and Unsolvability 》. McGraw - Hill Book Company, Inc, New York.. On pages 12 - 20 he gives examples of 5 - tuple tables for Addition, The Successor Function, Subtraction ( x y ), Proper Subtraction ( 0 if x < y ), The Identity Function and various identity functions, and Multiplication. 데이비스, 마틴 ; 론 시갈, 엘레인 J. 웨커 ( 1994 ). 《 Computability, Complexity, and Languages and Logic : Fundamentals of Theoretical Computer Science 》 2판. San Diego : Academic Press, Harcourt, Brace & Company. ISBN 0 - 12 - 206382 - 1. 더 이상 지원되지 않는 변수를 사용함 ( 도움말 ) Hennie, Fredrick ( 1977 ). 《 Introduction to Computability 》. Addison - Wesley, Reading, Mass. 지원되지 않는 변수 무시됨 : |
qi Sj None N Left L qm ( qi, Sj, N, L, qm ) ( qi, Sj, L, qm ) 5 qi Sj None N Right R qm ( qi, Sj, N, R, qm ) ( qi, Sj, R, qm ) 6 qi Sj None N None N qm ( qi, Sj, N, N, qm ) Direct " jump " ( qi, Sj, N, qm ) 7 qi Sj Erase Left L qm ( qi, Sj, E, L, qm ) 8 qi Sj Erase Right R qm ( qi, Sj, E, R, qm ) 9 qi Sj Erase None N qm ( qi, Sj, E, N, qm ) ( qi, Sj, E, qm ) 어떠한 종류의 튜링표도 위의 아홉 개의 5투플로부터 조합될 수 있다. 기술적인 이유로 세 개의 " N " 지시는 무시되기도 한다. 반면, 4투플은 잘 사용되지 않는다. 이들은 튜링 지시를 단순화할 때 사용된다. 상태 [ 편집 ] 튜링 기계를 설명하는 데 있어서 상태라는
향하는 연구들이 독일과 미국에서 행해지고 있었으며, 그러한 노력의 결과물은 2차 세계 대전 동안 연합국과 주축국의 군사 활동에 사용되었다. 1950년대 중반 하오 왕과 마빈 민스키는 튜링 기계를 좀 더 간단한 형태로 바꾸었다. 동시에 유럽의 연구자들은 최신식의 전자 컴퓨터를 현재의 튜링 기계인'컴퓨터와 같은 이론적 오브젝트'로 환원시켜 생각했다. 1950년대 후반에서 1960년대 초반에 멜자크와 레벡 ( 1961 ), 민스키 ( 1961 ), 셰퍼슨과 스터기스 ( 1961 ) 등의 유럽 연구자들은 일련의 연구들을 통해 튜링 기계를 좀 더 친숙하고 컴퓨터와 같은'셈 기계 counter machine'로 만들었다. 이후 1970년대 초반에는 엘곳과 로빈슨 ( 1964 ), 할트마니스 ( 1971 ), 쿡과 렉하우 ( 1973 ) 등은 이 연구를 진척시켜'기록 기계 register machine'와 RAM의 모델로 발전시켰다. 1970 - 현재 : 계산 모델로서의 튜링 기계 [ 편집 ] 오늘날의 셈 기계, 기록 기계, 그리고 RAM은 그 근간을 튜링 기계에 두고 있으며, 수많은 연구자들은 계산 이론을 풀어나가는 데에 있어서 튜링 기계를
##ference to the role of Turing machines in the development of computation ( both hardware and software ) see 1. 4. 5 History and Bibliography pp. 225ff and 2. 6 History and Bibliographypp. 456ff. Zohar Manna, 1974, Mathematical Theory of Computation. Reprinted, Dover, 2003. ISBN 978 - 0 - 486 - 43238 - 0 마빈 민스키, Computation : Finite and Infinite Machines, Prentice - Hall, Inc., N. J., 1967. See Chapter 8, Section 8. 2 " Unsolvability of the Halting Problem. " 초보자도 읽을만 하며 재밌는 부분도 있다. Christos Papadimitriou ( 1993 ). 《 Computational Complexity 》 1판. Addison Wesley. ISBN 0 - 201 - 53082 - 1. Chapter 2 : Turing machines, pp. 19 - 56. Michael Sipser ( 1997 ). 《 Introduction to the Theory of Computation 》. PWS Publishing
근간을 튜링 기계에 두고 있으며, 수많은 연구자들은 계산 이론을 풀어나가는 데에 있어서 튜링 기계를 사용한다. 특히 계산 복잡도 이론의 경우 튜링 기계의 사용이 필수적이다. 같이 보기 [ 편집 ] 확률적 튜링 기계 양자 튜링 기계 교대 튜링 기계 범용 튜링 기계 ( UTM, en : Universal Turing machine ) 참고 [ 편집 ] ↑ 1935년 중반, 막스 뉴만은 그의 강의에서 " 과연 수학적 표현에 적용되어 그 표현이 증명될 수 있는지를 알려주는 명확한 방법이 ( 뉴만은 이를 기계적 과정이라고 표현하였다. ) 존재하는가 " ( 호지스 1983 : 93 ) 라는 질문을 던졌다. 이 강의를 들고 튜링은 그 가상의 장치를 생각해내었다고 한다. ( 더 자세한 사실은 역사부분을 참조하시오 ) 그는 이 논문을 런던 수학회지에 1936년 5월 31일에 제출하였으나 ( 참고 : 호지스 1983 : 112 ), 정작 이 논문이 출판된 것은 1937년 초였고, 그 해 2월이 다 돼서야 발췌 인쇄가 가능해졌다. ( 참고 : 호지스 1983 : 129 ) 참고 문헌 [ 편집 ] 1차 저서, 재출판, 편집 [ 편집 ] B. Jack Copeland ed.
. 《 런던수학회지 》. 2 ( 1937 ) 43 ( 6 ) : 544 - 6. doi : 10. 1112 / plms / s2 - 43. 6. 544. ). Reprinted in many collections, e. g. in 해독불가능에 대해서 pp. 115 - 154 ; available on the web in many places, e. g. at Scribd. 앨런 튜링, 1948, " Intelligent Machinery. " Reprinted in " Cybernetics : Key Papers. " Ed. C. R. Evans and A. D. J. Robertson. Baltimore : University Park Press, 1968. p. 31. F. C. Hennie and R. E. Stearns. Two - tape simulation of multitape Turing machines. JACM, 13 ( 4 ) : 533 - 546, 1966. 계산 이론 [ 편집 ] 불로스, 조지 ; 리차드 제퍼리 ( 1989, 1999 ). 《 Computability and Logic 》 3판. Cambridge UK : Cambridge University Press. ISBN 0 - 521 - 20402 - X. 더 이상 지원되지 않는 변수를 사용함 ( 도움말 ) ; 다음 날짜
7624 - 1922 - 7. Includes Turing's 1936 - 1937 paper, with brief commentary and biography of Turing as written by Hawking. Rolf Herken ( 1995 ). 《 The Universal Turing Machine - A Half - Century Survey 》. Springer Verlag. ISBN 3 - 211 - 82637 - 8. 앤드류 호지스, Alan Turing : The Enigma, Simon and Schuster, New York. Cf Chapter " The Spirit of Truth " for a history leading to, and a discussion of, his proof. Ivars Peterson ( 1988 ). 《 The Mathematical Tourist : Snapshots of Modern Mathematics 》 1판. W. H. Freeman and Company, New York. ISBN 0 - 7167 - 2064 - 7 ( pbk. ) | isbn = 값 확인 필요 : invalid character ( 도움말 ). Paul Strathern ( 1997 ). 《 Turing and the Computer - The Big Idea 》. Anchor Books / Doubleday. ISBN 0
Computability 》. Addison - Wesley, Reading, Mass. 지원되지 않는 변수 무시됨 : | unused - data = ( 도움말 ). On pages 90 - 103 Hennie discusses the UTM with examples and flow - charts, but no actual'code '. 존 홉크로프트와 제퍼리 울만, ( 1979 ). 《 Introduction to Automata Theory, Languages and Computation 》 1판. Addison - Wesley, Reading Mass. ISBN 0 - 201 - 02988 - X. | isbn = 값 확인 필요 : invalid character ( 도움말 ). A difficult book. Centered around the issues of machine - interpretation of " languages ", NP - completeness, etc. Hopcroft, John E. ; Rajeev Motwani, Jeffrey D. Ullman ( 2001 ). 《 Introduction to Automata Theory, Languages, and Computation 》 2판. Reading Mass : Addison - Wesley. ISBN
##런 튜링계산 모형정형 기법계산 가능성 이론잉글랜드의 발명품오토마타 이론형식 언어숨은 분류 : 영어 표기를 포함한 문서인용 오류 - 오래된 변수를 사용함인용 오류 - 날짜인용 오류 - ISBN인용 오류 - 지원되지 않는 변수 무시됨LCCN 식별자를 포함한 위키백과 문서GND 식별자를 포함한 위키백과 문서BNF 식별자를 포함한 위키백과 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 다른 프로젝트 공용 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 ( ) IndonesiaItaliano 日 本 語 / / 中 文 - - 링크 편집 이 문서는 2018년 9월 12일 ( 수 ) 10 : 46에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허
수학 또는 이론 전산학에서 튜링 기계(영어: Turing machine)는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고 이 장치에 영어 단어인 automatic의 a를 따서 "a-기계"라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다. 1948년 "똑똑한 기계"라는 글에서 앨런 튜링은 자신의 "a-기계"를 간결히 정의하였다. 1936년 논문 "계산 가능한 수와 결정성 문제에의 응용"을 언급하며 튜링기계(이 글에서는 논리적 계산 기계라는 표현을 사용한다.)를 다음과 같이 기술하였다.