정지문제의 판별 가능성
-
게시물 수정 , 삭제는 로그인 필요
안녕하세요. 정지문제에 대한 설명을 듣던중 질문이 생겨 글을 적게 되었습니다.
정지문제에서 말하고자하는 바는 모든 프로그램과 입력에 대해 해당 프로그램을 해당 입력으로 실행 시 그 프로그램이 멈출 지 여부를 판별해주는 프로그램은 없다.. 라고 이해를 했는데
여기서 의문이 생겼습니다.
그렇다면 모든 프로그램을 입력 받아, 그 프로그램의 정지문제를 해결하는 프로그램을 만들 수 있는지, 그 여부를 출력해주는 프로그램은 존재할까요?
이제 정지문제와 달리 프로그램의 형태를 보고, 논리적 모순을 일으킨다고 판단되면 false를 내놓는 겁니다. 이렇게 되면 논리에도 큰 모순이 없어 보여서요.
예시로 input으로
While true:
None
같은 프로그램을 입력 받으면, 당연히 정지문제를 풀 수 있다는 답을 내놓게 되겠죠
그런데 input으로 정지문제에 모순을 주는 프로그램을 입력 받으면, 불가능하다고 출력하는 겁니다.
혹시 해당 내용과 관련이 있는 논문이 있다면, 논문의 이름을 알려주시면 감사하겠습니다.
정지문제에서 말하고자하는 바는 모든 프로그램과 입력에 대해 해당 프로그램을 해당 입력으로 실행 시 그 프로그램이 멈출 지 여부를 판별해주는 프로그램은 없다.. 라고 이해를 했는데
여기서 의문이 생겼습니다.
그렇다면 모든 프로그램을 입력 받아, 그 프로그램의 정지문제를 해결하는 프로그램을 만들 수 있는지, 그 여부를 출력해주는 프로그램은 존재할까요?
이제 정지문제와 달리 프로그램의 형태를 보고, 논리적 모순을 일으킨다고 판단되면 false를 내놓는 겁니다. 이렇게 되면 논리에도 큰 모순이 없어 보여서요.
예시로 input으로
While true:
None
같은 프로그램을 입력 받으면, 당연히 정지문제를 풀 수 있다는 답을 내놓게 되겠죠
그런데 input으로 정지문제에 모순을 주는 프로그램을 입력 받으면, 불가능하다고 출력하는 겁니다.
혹시 해당 내용과 관련이 있는 논문이 있다면, 논문의 이름을 알려주시면 감사하겠습니다.