전산학,compsci

Computer science





Misc: easy concepts



History

David Hilbert가 질문한 결정문제 혹은 수리명제자동판결문제(decision problem, Entscheidungsproblem)를 증명하기 위해
Alan_Turing이
튜링기계,Turing_machine AKA 튜링머신 를 고안함.

같은 시기에 프린스턴대의 Alonzo_Church도 독립적으로 람다대수,lambda_calculus(튜링머신과 equiv.) 연구.

처치-튜링 논제 Church-Turing thesis
: 수학 함수,function를 이용해 어떤 값을 구하는 방법이 있다면, 그 방법을 튜링머신으로도 구현할 수 있다.

중단문제,halting_problem
결론부터 말하면, 어떤 알고리즘,algorithm도 프로그램의 중단 여부를 판단할 수 없음. 결정불가능성,undecidability 문제임.