처치-튜링 논제: 두 판 사이의 차이

'''처치-튜링 명제'''(Church-Turing thesis)는 [[계산가능한 함수]]에 대한 명제이다. 간단히 요약하면, 어떤 함수는 [[튜링 기계]]가 계산할 수 있으면, 그리고 그 때만 [[알고리듬]]으로 계산 가능하다 명제이다. [[알론조 처치]]와 [[앨런 튜링]]의 이름을 따 지어졌다. 튜링 기계는 모든 범용 [[프로그래밍 언어]]로 번역될 수 있으므로, 이것은 어떤 컴퓨터에게든 충분한 시간과 메모리가 주어진다면 존재하는 모든 알고리즘의 결과를 출력할 수 있다는 명제와 동치이다.

 

 

실제로 증명되거나 반증된 적은 없으며, 영원히 증명할 수 없을 것이라고 주장하는 학자도 있다. 다만 현재까지 인간이 발명한 모든 종류의 계산법([[양자컴퓨터]]를 포함하여)이 적절한 형태의 튜링 기계로 표현될 수 있음이 알려져 있다.