튜링 머신과 PDA에 대해 공부할 때 첫 번째 컴퓨팅 디바이스가 튜링 머신이라고 생각했습니다.튜링 기계가 실제 장치 또는 가상 개념입니까?
따라서 나는 튜링 기계라고 불리는 실용적인 기계가 있으며 그 상태가 특수 장치 (예 : 플립 플롭)로 표현 될 수 있으며 자기 테이프의 입력을 받아 들일 수 있다고 생각했습니다.
따라서 의심 나는 How input string is represented in magnetic tapes?을 물었습니다. 그러나 대답과 나의 책에서 주어진 세부 사항에 의해, 나는 튜링 기계가 가설 적이라는 것을 알게되었다.
제 질문은 튜링 기계가 실제로 어떻게 구현 될까요? 예를 들어, 현재의 프로세서에서 맞춤법 오류를 검사하는 데 어떻게 사용됩니까?
튜링 기계가 구형인가요? 또는 그들은 아직도 사용되고 있는가?
튜링 기계는 여러 가지 이유로 실제로 사용되지 않습니다. 처음에는 무한 테이프를 만드는 데 무한한 자원이 필요하기 때문에 하나를 만드는 것은 불가능합니다. 게다가, 튜링 기계는 본질적으로 데이터 액세스의 순차적 특성 때문에 다른 계산 모델보다 느립니다. 예를 들어, 튜링 기계는 건너 뛸 어레이의 모든 요소를 거치지 않고 배열의 중간으로 점프 할 수 없습니다. 게다가 튜링 기계는 설계하기가 극히 어렵습니다. 32 비트 정수의리스트를 정렬하기 위해 Turing 머신을 작성해보십시오. (실제로는 제발하지 말아요. 정말 힘들어요!)
다음은 왜 튜링 기계를 전혀 연구하지 않는 질문입니까?
가능성이 계산 될 수 있는지의 한계를 추론하기 : 다행히도,이 작업을 수행하는 이유의 거대한 숫자가있다. 튜링 기계는 지구상의 컴퓨터를 시뮬레이션 할 수 있기 때문에 (또는 교회 - 튜링 논제, 물리적으로 실현 가능한 컴퓨팅 장치에 따라), 튜링 기계가 산출 할 수있는 한계를 보여줄 수 있다면, 우리는 실제 컴퓨터에서 수행되기를 희망 할 수 있습니다.
알고리즘 정의를 형식화합니다. "이 답을 추측하십시오"라는 문구가 아닌 동안 왜 이진 검색이 알고리즘입니까? 이 질문에 답하기 위해 우리는 컴퓨터가 무엇인지, 알고리즘이 무엇을 의미하는지에 대한 공식적인 모델을 가지고 있어야합니다.튜링 머신을 계산 모델로 삼아 알고리즘이 무엇인지를 엄격하게 정의 할 수 있습니다. 아무도 실제로 알고리즘을 형식으로 변환하려고하지만 알고리즘 및 계산 이론의 분야는 확고한 수학적 근거를 제공합니다.
결정 성 및 비 결정적 알고리즘의 정의를 공식화합니다. 아마도 컴퓨터 과학에서 가장 열려있는 질문은 P = NP인지 아닌지에 관한 문제입니다. 이 질문은 P와 NP에 대한 공식적인 정의가있는 경우에만 의미가 있으며 결정적 및 비 결정적 계산의 경우 정의가 필요합니다 (기술적으로는 2 차 논리를 사용하여 정의 할 수 있음). 튜링 기계를 가짐으로써 우리는 NP의 중요한 문제에 대해 이야기 할 수 있으며, NP 완전 문제를 발견 할 수있는 방법을 제공합니다. 예를 들어, SAT가 NP 완성이라는 증거는 SAT를 사용하여 튜링 기계를 인코딩하고 입력에서 실행한다는 사실을 사용합니다.
희망이 있습니다.
실현 불가능한 개념 장치입니다 (무한 테이프가 필요하기 때문에). 어떤 사람들은 튜링 기계의 물리적 구현을 구축했지만 물리적 인 제한으로 인해 진정한 튜링 기계는 아닙니다. http://www.youtube.com/watch?v=E3keLeMwfHY
이것은 이론적 기계
튜링 기계 테이프의 스트립 심볼을 조작 이론적 디바이스 테이블에 따라되는 위키
에서 다음 단락이다 : 여기 하나의 동영상 의 규칙. 단순함에도 불구하고 Turing 머신은 모든 컴퓨터 알고리즘의 로직을 시뮬 레이팅 할 수 있으며 특히 컴퓨터 내부의 CPU 기능을 설명하는 데 유용합니다. 는 인용문
비 결정적 기계 (실제 존재하지 않는)와 같은 다른 기계와 함께이 기계는 계산의 복잡성에 매우 유용 하나의 알고리즘이 다른 것보다 어렵거나 하나의 알고리즘이 풀 수없는 것을 증명 .. .etc
튜링 머신은 정확히 물리적 인 기계가 아니라 기본적으로 개념적인 기계입니다. Turing 개념은 가설이며, 작고 쉬운 솔루션을 위해 무한 테이프가 필요하기 때문에 현실 세계에서 구현하기가 매우 어렵습니다.
그 대답은 이전 답변이 놓친 것에 전혀 기여하지 않습니다. –
튜링 기계가 구식입니까? 또는 현재 날짜에 어떻게 사용됩니까? –
그들은 모든 경우에 대해 일반화하기 위해 이론 bcz에서 "무한 테이프"라고 말합니다. 그러나 나는 우리 사건의 입력 또는 스택이 얼마나 오래 걸릴지를 알고 있다고 생각한다. (적어도 대략) –
이들은 알고리즘 계산을 위해 만들어진 수학 개념이다. 그것들은 단순한 아이디어이기 때문에 구식이 될 수 없습니다. 계산 연구를위한 또 다른 아이디어는 Alonzo Church에서 그의 Lambda Calculus와 함께 나왔습니다. 그들은 실제 기계가 아니라 증명과 연구에 사용되는 추상 개념입니다. –