튜링 머신은 계산을위한 초기 모델 중 하나였습니다. 즉 계산 자체가 잘 이해되지 않았을 때 (1940 년경) 개발되었습니다. 나는 그 당시에 그들이 선호하는 모델이되게했던 두 가지 측면에 초점을 맞추고 자하는데, 그 결과 가장 확립 된 표준 모델이되었다.

1. 입증의 단순성
   이론 모델로서, 튜링 기계는 현재 기계 상태가 일정한 크기만을 갖는다는 점에서 “단순”하다는 매력을 가지고 있습니다. 다음 머신 상태를 결정하는 데 필요한 모든 정보는 하나의 심볼과 하나의 (제어) 상태 번호입니다. 머신 상태로의 변경은 똑같이 작으며 머신 헤드의 움직임 만 추가합니다. 이를 통해 (공식) 증명, 특히 구별되는 사례 수가 상당히 단순 해집니다.

   이 측면을 RAM 모델과 비교하십시오 (최소한 형식으로 사용되지 않는 경우). 다음 작업은 여러 개의 작업 중 하나 일 수 있으며이 작업은 임의의 (2) 레지스터에 액세스 할 수 있습니다 . 여러 제어 구조가 있습니다.

2. 런타임 및 공간 사용
   Turing Machine과 거의 동시에 발생하는 두 가지 주요 계산 모델, 즉 Church의 calculus 및 Kleene의 recursive 함수가 있습니다. 그들은 튜링이 힐버트의 Entscheidungs 문제로했던 것과 같은 질문에 대답 했지만, 런타임과 공간 사용을 정의하는 데 훨씬 덜 쉽게 빌려 주었다 . 어떤 점에서는 그것들이 너무 추상적이기 때문에보다 현실적인 기계 모델과 관련이 없습니다.λ

   λ

   μ

   μ

   그러나 튜링 기계의 경우 두 가지 개념을 쉽게 정의 할 수 있습니다. 실제로 작업을 수행하는 데 효율성 에 대한 고려 가 곧 매우 중요 했기 때문에 이것은 튜링 머신의 확실한 이점이었습니다.

따라서, 튜링 기계로 설립 된 역사 “사고”와 주요 속성 중 일부의 조합으로 볼 수 계산 모델. 그럼에도 불구하고, 특히 튜링 머신의 단점을 극복하기 위해 많은 모델이 정의되어 열렬히 사용되었습니다. 예를 들어, 그들은 “프로그램”(즉, 정의)하기가 지루합니다.

실제 적용되는 직접적인 응용 프로그램은 없습니다. 특히, 계산 실습은 계산 이론과 병행하여 (그리고 처음에는 대부분 독립적으로) 발전했다. 프로그래밍 언어 는 공식적인 기계 모델없이 개발 되었습니다 . 그러나 이론에 의해 계산 실습의 많은 발전이 가능하다는 것이 (후시) 분명하다.

또한 이론적 개념이 실제로 가져 왔던 가치는 모든 후손, 즉 후속 작업, 결과 및 그 개념에 의해 가능해진 새로운 아이디어 를 고려하여 측정해야한다는 점 을 명심하십시오. 그런 점에서 튜링 기계의 개념 (다른 것들 중에서)이 세계를 혁명적으로 만들었다 고 말하는 것이 공정하다고 생각합니다.

답변