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

내용 삭제됨 내용 추가됨
잔글 Monsieur Lichan님이 처치-튜링 명제 문서를 처치-튜링 논제 문서로 이동했습니다
잔글편집 요약 없음
1번째 줄:
'''처치-튜링 명제논제'''(Church-Turing thesis)는 [[계산 가능 함수|계산 가능한 함수]]에 대한 명제이다논제(thesis)이다.<ref>김항곤. [https://news.naver.com/main/read.nhn?mode=LSD&mid=sec&sid1=105&oid=030&aid=0002039711 로봇 발전에 기여한 3人을 기억하며]. 전자신문. 2009년 10월 12일.</ref> 간단히 요약하면, 어떤 함수는 [[튜링 기계]]가 계산할 수 있으면, 그리고 그 때만 [[알고리듬|알고리즘]]으로 계산 가능하다가능하다는 명제이다. [[알론조 처치]]와 [[앨런 튜링]]의 이름을 따 지어졌다. 튜링 기계는 모든 범용 [[프로그래밍 언어]]로 번역될 수 있으므로, 이것은 어떤 컴퓨터에게든 충분한 시간과 메모리가 주어진다면 존재하는 모든 알고리즘의 결과를 출력할 수 있다는 명제와 동치이다.
 
처음 이 명제가 나왔을 때에는 "효과적으로 계산할 수 있는 (effectively computable) 함수"와 같이 비형식적인 표현을 사용했기 때문에 이 명제를 논리적으로 증명하는 것은 불가능했다. 이후 수학자들은 모호한 말 대신 [[계산 가능 함수|계산 가능한 함수]]를 사용한다.