Turing Machine과 Lambda 미적분학의 관계는? 있습니까? 아니면 거의 같은

Turing Machine과 Lambda 미적분학 사이에 관계가 있습니까? 아니면 거의 같은 시간에 발생 했습니까?

답변

람다 미적분은 튜링의 기계 모델보다 오래되었으며 1928-1929 (Seldin 2006) 시대부터 시작되었으며 교회가 그가 고안 한 기본 논리에 필요한 개략적 인 기능의 개념을 캡슐화하기 위해 발명되었습니다. 계산 가능한 기능의 일반적인 개념을 포착하기 위해 발명되지 않았으며, 더 약한 유형의 버전은 그의 목적을 더 잘 수행했을 것입니다.

비록 나중에 교회가 람다 계산법을 효과적으로 계산할 수있는 기능 (1936) 이라고 부르는 기초로 사용했지만 , 튜링이 그의 논문에서 호소 한 것은 비록 계산법이 튜링 완성으로 판명되었다는 것이 우연 인 것처럼 보인다. .

교회의 간단한 유형 이론 (1940)은 고차원 논리의 구문을 표현하기에는 충분하지만 모든 재귀 함수를 표현하지는 않는, 더 온건하고 형식화 된 함수 이론을 제공합니다. 이 이론은 교회의 원래 동기와 더 조화를 이룬 것으로 볼 수 있습니다.

참고 문헌

  • 교회 (1936). 초등 수 이론에서 풀 수없는 문제. American Journal of Mathematics 58 : 345—363.
  • 교회 (1940). 간단한 유형 이론의 공식화 . Symbolic Logic 5 (2) : 56 ~ 68.
  • 셀딘 (2006). 카레와 교회의 논리 . 에서 논리의 역사 핸드북, 5 집 : 논리 러셀에서 교회 쪽. 819 ~ 874. 북 홀란드 : 암스테르담.

참고이 답변은 Kaveh와 Sasho의 반대 의견으로 인해 수정되었습니다. 나는 Kaveh가 제안한 Wikipedia 타임 라인을 추천한다 . 교회의 역사 – 논문 작성.

답변

람다 미적분학과 튜링 머신이 모두 같은 클래스의 숫자 이론 함수를 계산하지만 상상할 수있는 모든 방식에서 정확하게 동등하지는 않다는 것을 지적하고 싶습니다. 예를 들어, 실현 가능성 이론에는 튜링 머신에 의해 실현 될 수 있지만 람다 미적분에 의해 실현 될 수없는 진술이 있습니다. 그러한 진술 중 하나는 다음과 같이 공식적인 교회 논문이다.

∀f:nat→nat ∃e ∀n ∃k (T(e,n,k)∧U(k,f(n)))

T

c

f

e

f

f

c

c

f

. 이것은 할 수 없습니다 (별도의 질문으로 물어 보면 이유를 설명 할 수 있습니다).

답변

그것들은 수학적으로나 역사적으로 관련이 있습니다.

람다 미적분학은 1928 년에서 1929 년에 Alonzo Church (1932 년에 출판)에 의해 개발되었습니다.

튜링 기계는 Alan Turing (1937 년에 출판)에 의해 1935 년에서 1937 년에 개발되었습니다.

Alan Turing은 Alonzo Church의 박사 학위를 받았습니다. 1936 년부터 1938 년까지 프린스턴의 학생.

튜링 머신과 람다 미적분은 전산 력에서 동등합니다. 각각은 서로 효율적으로 시뮬레이션 할 수 있습니다.

답변

Entscheidungsproblem 은 수학자 David Hilbert가 제안한 유명한 23 가지 문제 중 하나입니다.

1936 년과 1937 년에 Alonzo Church와 Alan Turing은 각각 산술적 진술이 참인지 거짓인지 알고리즘 적으로 결정하는 것이 불가능하다는 것을 보여주는 독립적 인 논문을 발표했으며, 따라서 엔 차이 둔 문제에 대한 일반적인 해결책은 불가능하다.

이것은 1936 년 Alonzo Church가 그의 λ 미적분학을 기반으로 한 “유효한 계산 능력”이라는 개념으로, 그리고 같은 해에 그의 튜링 기계 개념으로 Alan Turing에 의해 수행되었습니다. 나중에 이것들은 동등한 계산 모델이라는 것이 인식되었습니다. -위키 백과

따라서 람다 미적분학 및 튜링 기계 는 밀접하게 관련되어있을뿐만 아니라 동등한 계산 모델입니다 .

찰스 Petzold에 의해 Alan Turing의 컴퓨팅 및 튜링 기계에 대한 역사적인 논문을 통해 안내 된 튜링 : 가이드 투어를 읽어보십시오
. 이 책은 주제에 관한 흥미로운 정보를 담고 있습니다.

답변

튜링 머신과 람다 미적분학은 알고리즘 개념 (기계적 계산)을 포착하는 두 가지 모델입니다. Lambda 미적분학은 교회에서 함수로 계산을 수행하기 위해 발명했습니다. 기능적 프로그래밍 언어의 기초입니다. 기본적으로 Turing machine이 계산할 수있는 (결정 가능한) 모든 문제는 Lambda 미적분을 사용하여 계산할 수 있습니다. 따라서 두 개의 동등한 계산 모델 (다항식 요소까지)이며 모든 기계적 계산의 힘을 포착하려고합니다.

답변