(김*혁, 정지 문제)

[kc937]

교수님 강의를 보면서 H라는 기계가 실존할 수 없다는 증명에 관해서 궁금증이 생겨서 질문 드립니다.

일단 H라는 기계에 대해서 다음과 같이 생각했습니다.

1. H는 테스트할 기계의 청사진과 청사진에 기반한 기계에 입력할 값을 받는다.

2. H는 청사진에 기반하여 주어진 값에 따라서 주어진 기계를 시뮬레이션하고 해당 기계가 멈출지 말지 결정한다.

3. H는 멈춘 문제를 완벽하게 풀며 언제나 올바른 답을 도출한다. (강의 4:28초)

하지만 이미 H가 항상 답을 도출한다는 전제가 성립할 수 없다고 생각합니다. H는 시뮬레이션을 진행하기 때문에 X 기계에 X의 청사진을 입력하는 무한 루프에 빠져 값을 반환하지 못할 것이라고 생각합니다.

그러면 H가 값을 도출하지 못하는 모순이 발생하여 H가 실존할 수 없음을 설명할 수 있는데 왜 증명에서는 귀류법을 활용하여 증명하는지 궁금합니다.

[liganega]

아래 주장의 근거는?

하지만 이미 H가 항상 답을 도출한다는 전제가 성립할 수 없다고 생각합니다. H는 시뮬레이션을 진행하기 때문에 X 기계에 X의 청사진을 입력하는 무한 루프에 빠져 값을 반환하지 못할 것이라고 생각합니다.

[kc937]

분명 강의 4분 20초대에서 H 기계는 항상 올바른 답을 도출한다는 내용이 있었습니다. 그렇다면 H 기계는 무슨 일이 있더라도 답을 도출해야합니다.

또한 H 기계를 설명할 때 청사진에 기반하여 시뮬레이션을 진행한다고 했습니다. 영상에서도 A의 청사진과 연산식을 입력 받는 과정을 시뮬레이션 하는 것을 보여주었습니다.

그렇다면 X의 청사진을 X 기계에 넣으면 P 기계가 이를 복사하여 H 기계에 X의 청사진 2개를 입력합니다.
그러면 H 기계는 X 기계에 X의 청사진을 넣는 시뮬레이션을 진행합니다. 그러면 X에 다시 X의 청사진을 넣는 과정을 다시 진행하게 됩니다.

여기에서 X에 X의 청사진을 넣는 무한 루프에 빠지게 된다고 생각하여 H 기계가 항상 답을 도출한다는 전제가 성립할 수 없다고 생각했습니다.

[liganega]

아래 문장에 오류가 있음.

그러면 H 기계는 X 기계에 X의 청사진을 넣는 시뮬레이션을 진행합니다. 그러면 X에 다시 X의 청사진을 넣는 과정을 다시 진행하게 됩니다.

[kc937]

1. Segmentation fault와 관련된 오류인가요?

2. 강의 영상 2번째를 확인했습니다.
   """
   check에 자기자신을 넣어서 성공적으로 출력했다고 가정하면 halting의 인자값으로 check와 check로 넣은 인자값이 false가 되어야함
   halting 함수의 정의에 따르면 check에 어떤 값을 넣는다면 무한루프에 빠진다는 소리임
   하지만 우리는 check가 방금 계산을 끝낸다고 가정했기 때문에 모순이 발생함
   """
   이게 제가 이해한 내용입니다. 이후 인공지능에게 물어본 결과 무한 루프에 빠진다는 주장은 빠지지 않게 만들면 되지 않냐는 반박이 나올 수 있다고 하여서 귀류법이 더 정교한 방식임을 알게되었습니다.

교수님이 발견하신 오류가 무한루프에 빠지지 않게 프로그램을 만들면 된다는 말씀이신가요?