튜링 기계란 무엇인가?

https://stackoverflow.com/questions/236000

04-07-2019
|

문제

튜링 기계란 무엇이며 사람들이 계속해서 언급하는 이유는 무엇입니까?내 IBM PC만 있으면 계산을 할 수 있습니다!왜 누군가가 이 기계에 관심을 갖는 걸까요?

해결책

튜링 머신이 큰 이유는 클래식 컴퓨팅 과학 또는 계산 유형의 이론에 대한 연구와 관련이 있습니다. 그것은 기본적으로 컴퓨터의 일반적인 속성을 분석하는 것, 예를 들어 컴퓨터의 이론적 능력과 한계, 그리고 우리가 무언가를 "컴퓨팅"에 대해 이야기 할 때 의미하는 바와 같은 것입니다.

튜링 머신을 사용하여 공부할 수있는 것의 한 가지 예는 다음과 같습니다. 정지 문제. 이 문제는 학문적 운동이지만, 실질적인 실제 영향을 쉽게 할 수 있습니다. 프로그램에 무한 루프가 포함되어 있는지 여부를 단순히 알려주는 디버거를 작성하지 않겠습니까? 중단 문제는 일반적인 경우 에이 문제를 해결하는 것이 불가능하다는 것을 확립합니다.

튜링 머신에 대한 연구는 또한 언어 문법과 그 클래스의 연구에 적합하여 언어 개발을 프로그래밍합니다. "정규 표현"이라는 용어는 일반 문법, 그리고 이러한 문법 (계산 이론의 일부)에 대한 연구는 정규 표현이 해결할 수있는 문제와 그들이 할 수없는 것에 대해 정확히 더 많이 알려줄 것입니다. 예를 들어, 기존의 정규 표현 구문은 다음과 같은 문제를 해결할 수 없습니다. 입력에있는 'a'char의 숫자 n을 구문 분석 한 다음 동일한 숫자 n의 char 'b'를 구문 분석합니다.

이런 종류의 것에 대한 좋은 텍스트에 관심이 있으시면 확인하십시오. 계산 이론 소개 Michael Sipser. 좋아요.

다른 팁

Turing Machine은 Alan Turing이 수학 계산을위한 이상적인 모델로 사용하기 위해 발명 한 이론적 컴퓨팅 머신입니다. 기본적으로 간단한 형태의 컴퓨터로 구성됩니다. 줄자 (종이 리본), a 머리 기호를 읽고 새 기호를 제자리에 작성한 다음 왼쪽 또는 오른쪽으로 이동할 수 있습니다.

튜링 머신은 상태, 그런 다음 프로그램은 목록입니다 전환, 머리 아래에 현재 상태와 기호가 있는데, 테이프에 작성해야 할 내용, 다음 상태가 무엇인지, 머리가 움직일 위치.

여기에 있습니다 기본 튜링 머신, JavaScript로 구현되었습니다 ...

그리고 스케치 :

turing machine

내 IBM PC만 있으면 계산을 할 수 있습니다!

다른 사람들이 지적하지 않은 것 :귀하의 IBM PC ~이다 튜링 기계.보다 정확하게는 PC가 할 수 있는 모든 작업을 Turing 기계가 수행할 수 있고 Turing 기계가 수행할 수 있는 모든 작업을 PC에서 수행할 수 있다는 점에서 동일합니다.

구체적으로 튜링 머신은 다음과 같다. 계산 모델 이는 계산 가능성의 개념을 완벽하게 포착하는 동시에 PC 아키텍처의 모든 구체적인 세부 사항 없이 추론하기 단순하게 유지합니다.

(일반적으로 받아들여지는) "Church-Turing 이론"은 모든 계산 장치나 모델이 Turing 기계보다 더 강력하지 않다고 주장합니다.따라서 많은 이론적 문제(예:P 및 NP와 같은 클래스, "다항식 시간 알고리즘" 개념 등)은 Turing 기계의 관점에서 공식적으로 설명되지만, 물론 다른 모델에도 적용할 수 있습니다.(예를 들어 때로는 람다 미적분학이나 조합 논리 등의 관점에서 계산을 생각하는 것이 편리할 수 있습니다.그들은 모두 서로의 성능은 동일하며 IBM PC와도 동일합니다.)

그럼 여기까지입니다:사람들이 Turing 기계에 대해 이야기하는 이유는 그것이 CPU 아키텍처, 제약 조건 등의 모든 세부 사항을 설명할 필요 없이 "컴퓨터"가 무엇인지 말하는 정확하고 완전하게 지정된 방식이기 때문입니다.

실제로 튜링 머신의 예가 있습니다. 구체적으로, 리보솜, RNA를 단백질로 번역하고 튜링 기계를 구현합니다.

첫째, 일부 배경 :

RNA는 유전자 알파벳의 문자를 정의하는 일련의 뉴클레오티드 ( "염기")로 구성됩니다.
RNA 알파벳에는 4 개의 염기가 있습니다 -A, C, G, U.
베이스는 방향성입니다 : 컨벤션에 따라 끝은 5 프라임과 3 개의 프라임 (5 ', 3')이라고합니다.
RNA 문자열의베이스는 "반면 평면 상보 적 쌍"의 다른 RNA 줄에베이스를 끌어들일 수 있으며, 여기서 U와 C에 대한 스틱은 G에 붙어 있습니다.
염기는 3 그룹으로 결합되어 "코돈"(단어)을 형성합니다.
코돈에 대한 64 개의 가능한 조합이 있습니다 (4^3).
각 코돈은 "반 코돈"과 일치 할 수 있습니다. 예를 들어 8 월 <-> uac
특정 항 코돈을 갖고 특정 아미노산 (단백질)에 부착 된 특수한 캐리어 분자 ( "TRNA")가 있습니다.

리보솜의 작동은 간단합니다.

전사는 "읽기 프레임"을 정의하는 "시작 코돈"에서 시작됩니다.
전사는 항상 5 '-> 3'방향으로 진행됩니다.
읽기 프레임 하의 코돈은 특정 아미노산을 함유하는 특정 trNA와 일치합니다.
시작 코돈은 항상 아미노산 메티오닌을 암호화합니다.
새로운 아미노산은 성장하는 단백질에 부착됩니다.
그런 다음 프레임은 다음 코돈으로 3 개의 염기를 전진시키고 단백질은 지속적으로 확장됩니다.
"정지"코돈을 만나면, 번역이 종결되고, 아미노산은 부착되지 않으며 리보솜은 mRNA로부터 해리됩니다.

보시다시피, 이것은 가장 복잡한 작동 인 Nature 자체를 수행하는 매우 간단한 튜링 머신입니다!

Turing-Machine은 컴퓨터의 한계에 대해 추론하는 데 사용될 수있는 이론적 인 기계입니다. 간단히 말해서, 그것은 무한 메모리를 가진 상상의 컴퓨터입니다.

우리는 Turing-Machines에 관심이 있습니다. 왜냐하면 실제 컴퓨터 (IBM PC와 같은)로 성취 할 수없는 것을 발견하는 데 도움이되기 때문입니다. 튜링 머신이 특정 계산을 수행하는 것이 불가능한 경우 중단 문제), 그런 다음 IBM PC가 동일한 계산을 수행하는 것이 불가능하다는 이유가 있습니다.

비행기를 디자인하는 사람들이 Wright Brothers 또는 고정 날개 항공기를 날 수있는 "리프트"의 과학에 관심을 갖는 이유는 무엇입니까?

Alan Turing은 현대 컴퓨팅의 아버지로 칭찬을받습니다. 튜링 머신은 모든 현대 컴퓨터의 선구자입니다.

계산 성 이론은 대학에서 가장 어려운 수업 이었지만, 나는 그것을 가져 갔다는 것이 기쁩니다. 그것은 내가 결코 가질 수없는 것들에 대해 생각하게 만들었거나, 결코 가질 수없는 방식으로 사물에 대해 생각하게 만들었습니다.

튜링 머신은 계산할 수있는 추상 기계입니다.

Wikipedia에서 :

튜링 머신은 단순성에도 불구하고 컴퓨터 알고리즘의 논리를 시뮬레이션하기 위해 적응할 수있는 기본 추상 기호 관리 장치입니다. 그들은 1936 년 Alan Turing에 의해 묘사되었습니다. 튜링 머신은 실제 컴퓨팅 기술이 아니라 기계 계산의 한계에 대한 사고 실험입니다. 따라서 그들은 실제로 건설되지 않았습니다. 그들의 추상적 특성을 연구하면 컴퓨터 과학과 복잡성 이론에 대한 많은 통찰력이 생성됩니다.

다른 튜링 머신을 시뮬레이션 할 수있는 튜링 머신을 범용 튜링 머신 (UTM 또는 단순히 범용 기계)이라고합니다. Alonzo Church는 비슷한 "보편적 인"자연을 가진보다 수학적으로 지향적 인 정의를 소개했는데, Alonzo Church는 람다 미적 큘러에 대한 연구가 교회-튜링 논문으로 알려진 공식 계산 이론에 튜닝과 얽혀 있습니다. 논문은 튜링 머신이 실제로 논리와 수학에서 효과적인 방법에 대한 비공식적 개념을 포착하고 알고리즘 또는 '기계적 절차'의 정확한 정의를 제공한다고 명시하고 있습니다.

Turing Machine은 일부 논리에 따라 일련의 데이터에서 작동 할 수 있으며 자체 상태와 데이터를 변경할 수있는 추상 머신입니다.

이것은 알고리즘, 저장된 프로그램 및 일반적으로 계산의 기초를 형성하는 개념입니다. 알고리즘, 상태, 데이터 등을 처리하는 경우 좋은 통찰력과 추상화를 제공합니다.

생각을위한 음식.

Wikipedia 항목 외에도 책을 집어 들고 싶을 수도 있습니다. 주석이 달린 튜링 Charles Petzold. 자막 "Alan Turing의 계산 가능성과 Turing Machine에 관한 역사적인 논문을 통한 가이드 투어"라는 자막에는 역사적 관점을 포함하여 주제에 대한 많은 담론이있는 덩어리가있는 완전한 종이가 포함되어 있습니다.

튜링 머신은 알고리즘과 같습니다. 문자열을 받아 들일 때 중단, 문자열을 허용하지 않을 때 무한 루프를 거부하거나 유입됩니다.

테이프는 메모리 역할을하며 전환 규칙은 '그렇다면'조건으로 작용합니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow