튜링 머신 대 Von Neuman 머신

튜링 머신 대 Von Neuman 머신

---

배경

폰 - 노이만 아키텍처는 명령이 일부 데이터 및 수정 데이터에서 작동 명령과 데이터 메모리와 내부 상태를 변경하여 기계 작동에 저장되어있는 저장 프로그램 컴퓨터, 즉 설명합니다. 따라서 본질적으로 시스템에는 상태가 유지됩니다.

튜링 기계 아키텍처는 테이프에 문자 조작하여 작동합니다. 즉, 슬롯 수가 무한한 테이프가 존재하며 어느 한 시점에서 Turing 머신은 특정 슬롯에 있습니다. 해당 슬롯에서 읽은 기호에 따라 기계는 기호를 변경하고 다른 슬롯으로 이동할 수 있습니다. 이 모든 것이 결정적입니다.

---

질문

1. 이 두 모델 사이에 어떤 관계가 있습니까? Von Neuman 모델은 Turing 모델을 기반으로했거나 영감을 얻었습니까?

2. Turing 모델이 Von Newman 모델의 상위 집합이라고 말할 수 있습니까?

3. 함수형 프로그래밍이 튜링 모델에 적합합니까? 그렇다면 어떻게? 함수형 프로그래밍이 Von Neuman 모델에 적합하지 않다고 가정합니다.

---

튜링 머신은 계산 가능한 문제의 영역을 수학적으로 탐구하고 이러한 계산을 설명하는 방법을 얻기 위해 고안된 이론적 개념 입니다.

Von-Neumann 아키텍처는 실제 컴퓨터 를 구성하기위한 아키텍처입니다 ( 이론적으로 Turing 머신이 설명 하는 것을 구현 ).

함수형 프로그래밍은 계산 또는보다 정확하게 계산 가능한 함수를 설명하는 또 다른 방법 인 lambda-calculus를 기반으로합니다 . 완전히 다른 접근 방식을 사용하지만 튜링 머신에도 똑같이 강력합니다 ( 튜링 완료 라고합니다 ).

모든 람다-미적분 프로그램 (용어) T은 다음 조합을 사용하여 작성됩니다.

• 같은 변수 x
• 익명 기능 λx. T
• 기능 응용 T T

Stateless 임에도 불구하고 이것은 컴퓨터가 수행 할 수있는 모든 계산에 충분 합니다. 튜링 머신과 람다 용어는 서로를 에뮬레이트 할 수 있으며 Von-Neumann 컴퓨터는 둘 다 실행할 수 있습니다 (튜링 머신에 필요할 수있는 무한 스토리지 제공과 같은 기술적 제한 사항 제외).

그러나 무국적 및 더 추상적 인 특성으로 인해 기능적 프로그램 은 바이너리, 메모리 및 업데이트 스타일을 따르는 명령형 프로그램에 비해 Von-Neumann 컴퓨터에서 덜 효율적이고 덜 "직관적"일 수 있습니다 .

---

일반적으로 하나는 Harvard 아키텍처 와 대조 되는 Von Neumann 아키텍처를 나타냅니다 . 전자는 코드와 데이터가 같은 방식으로 저장된 반면 후자는 코드와 데이터를위한 별도의 메모리와 버스 경로를 가지고 있습니다. 모든 최신 데스크탑 PC는 Von Neumann이며 대부분의 마이크로 컨트롤러는 Harvard입니다. 둘 다 이론적 인 튜링 머신을 에뮬레이트하려는 실제 디자인의 예입니다 (진정한 튜링 머신에는 무한한 메모리가 필요하기 때문에 불가능합니다).

---

Turing 모델은 구현에 깊이 들어 가지 않고 계산 기능을 정의합니다. 아무도 문자 그대로 Turing Machine처럼 보이는 컴퓨터를 만들지 않습니다. (매니아 http://www.youtube.com/watch?v=E3keLeMwfHY 제외 ).

Turing 모델은 아키텍처 가 아닙니다 .

Von Neuman은 컴퓨터 구축 방법을 안내합니다. 계산 능력에 대해서는 아무것도 말하지 않습니다. 명령 세트에 따라 생산 된 컴퓨터는 튜링이 완료되거나 완료되지 않을 수 있습니다 (튜링 머신과 동일한 작업을 해결할 수 있음).

함수형 프로그래밍 (람다 미적분)은 Turing이 완성되었지만 기본적으로 Von Neumann 아키텍처에 맞출 수없는 또 다른 계산 모델입니다.

---

Turing 기계와 von Neuman 아키텍처 사이에 어떤 역사적 관계가 있는지 모르겠습니다. 그러나 나는 von Neuman이 von Neuman 아키텍처를 개발할 때 Turing 기계에 대해 알고 있었다고 확신합니다.

그러나 계산 능력에 관한 한 Turing 기계와 von Neuman 기계는 동등합니다. 둘 중 하나가 다른 하나를 에뮬레이트 할 수 있습니다 (IIRC, Turing 머신에서 von Neuman 프로그램을 에뮬레이트하는 것은 O (n ^ 6) 작업입니다). 람다 미적분 형태의 함수형 프로그래밍도 동일합니다. 사실, 적어도 Turing 머신만큼 강력한 알려진 모든 계산 프레임 워크는 동일합니다.

• 튜링 머신
• Lambda 미적분 (함수 프로그래밍)
• 폰 노이만 머신
• 부분 재귀 함수

이러한 모델로 계산할 수있는 함수 집합에는 차이가 없습니다.

함수형 프로그래밍은 람다 미적분에서 파생되므로 Turing 또는 von Nemuan 기계에 직접 매핑되지 않습니다. 어느 쪽이든 에뮬레이션을 통해 기능적 프로그램을 실행할 수 있습니다. 저는 Turing 기계에 대한 매핑이 von Neuman 기계에 대한 매핑보다 더 지루할 것이라고 생각하므로 세 번째 질문에 대한 제 대답은 "아니요, 사실 더 나쁩니다."

---

Turing "모델"은 전혀 건축 모델이 아닙니다. 튜링이 결정 문제를 증명하기위한 수단으로 사용한다고 가정 한 것은 존재하지 않는 기계였습니다 .

참고 URL : https://stackoverflow.com/questions/2782014/turing-machine-vs-von-neuman-machine