[ho9457kr]

안녕하세요 정치외교학부 13학번 김정호입니다. id를 제 이름으로 할걸 그랬나봐요 ㅠㅠ.

8. Application of the diagonal process. 에서
이거 전에 쉽게 f(x) = if H(f, x) then loop else 1. 는 이해가 갔는데.

멈춤문제(Halting Problem)를 풀 수 있는 튜링기계는 없다는 것을 보임.

만약 있다고 하자 H. 그러면, 모든 튜링기계의 모든 출력들을 모을 수 있다.
-> 행렬(표)의 각 원소들이 튜링기계 하나하나에서 출력된 값인가요?
안 멈추면 0. -> 표가 두개 나오는데 첫번째 표에서 출력값이 0, 1이 아닌 경우는 어떤 경우인가요? (아니면 튜링기계의 값을 임의로 배열한 것에 지나지 않나요?) 그러니까 H(M subscript n, m) 가 뭘 뜻하는 지 모르겠습니다.

칸토르의 대각선 논법을 설명하실 떄도 | N | < |2^N |, | N | = |2^N | 2가지 경우를 S subscript n행, m열인 행렬로 표현했는데 x , o 의 기준을 모르겠네요 ㅠㅠ.

[유병준]

김정호님, 안녕하세요.
강의 조교 유병준입니다.

아이디는 실명으로 바꿔 주세요.
그럼 질문에 답변 드리겠습니다.

질문1) 행렬(표)의 각 원소들이 튜링기계 하나하나에서 출력된 값인가요?

답변) 네, 그렇습니다.




위의 표에서 는 각각 0, 1, 2로 인코딩된 튜링 기계를 의미합니다.
(모든 튜링 기계는 특정 수로 인코딩할 수 있습니다. 5. Enumeration of computable sequence 참고하세요.)
맨 윗줄의 0 1 2 3 각각은 튜링 기계에 입력되는 인풋(input)을 의미하고요.



그럼 위의 표의 의미를 해석해 봅시다.
튜링 기계 에 인풋 0을 넣으면 결과가 0이고,
1, 2, 3을 넣어도 결과가 0이란 뜻입니다.
즉, 이 튜링 기계는 인풋 0, 1, 2, 3에 대해 끝나지 않는다는 것을 알 수 있군요.




이번에도 마찬가지로 해석해 봅시다. 튜링 기계 에 인풋 0을 넣으면 결과가
0입니다. 1을 넣으면 그 결과가 2, 2를 넣으면 2, 3을 넣으면 끝나지 않습니다.



이젠 아시겠죠? 튜링 기계 에 인풋 0을 넣으면 계산 결과가 8이고,
1을 넣으면 1, 2를 넣으면 4, 3을 넣으면 2입니다.



질문2) 표가 두 개 나오는데 첫 번째 표에서 출력값이 0, 1이 아닌 경우는
어떤 경우인가요? (아니면 튜링기계의 값을 임의로 배열한 것에 지나지 않나요?)

답변) 표에 나타난 출력값은 단지 튜링 기계에 특정 인풋이 들어온 뒤
테잎에 쓰여지는 값일 뿐입니다. 그 값은 1이 될 수도 있고,
2나 4, 8이 될 수 있습니다. 질문 1의 답변을 참고하시면 이해하시기 쉬울 겁니다.
결론은 출력값이 0, 1이 아닌 게 특별한 경우가 아니라는 말입니다.



질문3) 가 뭘 뜻하는 지 모르겠습니다.

답변) 먼저 부품부터 각각 설명 드리겠습니다.
H는 멈춤 문제를 푸는 튜링 기계입니다.
은 자연수 n으로 인코딩된 튜링 기계입니다.
m은 튜링 기계의 인풋(input)입니다.

결국 은
튜링 기계 이 인풋 m을 받았을 때 최종적으로 멈출 것인지
멈추지 않을 것인지를 풀어주는 기계입니다.
(언듯 생각하면 m이 없어도 될 것 같지만, 튜링 기계는 인풋에 따라
행동이 달라지므로 m도 필요한 것입니다.)
멈추지 않으면 0을, 멈추면 1을 결과값으로 내놓습니다.




질문4) 칸토르의 대각선 논법을 설명하실 때 | N | < |2^N |, | N | = |2^N | 2가지 경우를 S subscript n행, m열인 행렬로 표현했는데 x , o 의 기준을 모르겠네요.

답변) 설명의 편의상 임의로 지정한 것뿐입니다.

질문에 충분한 답변이 되었으면 좋겠습니다.
혹시 이해가 안 가시는 것이 있으면 더 질문해 주시기 바랍니다.

그럼 월요일에 뵙겠습니다.
감사합니다.