Halting problem은 파라독스와 같은 형태를 띕니다. 먼저 M_h라는 머신이 있어서 입력으로는 코딩이 된 임의의 다른 머신 M을 받고 출력으로는 만일 M이 halt하면 1을, 아니면 0을 출력한다고 합시다. (이게 바로 halting problem이죠. 임의의 turing 머신이 주어졌을때 그것이 halt하나 안하나 결정하는 문제) 이 M_h를 이용해서 새로운 머신 M_o를 만들어봅시다. M_o은 역시 코딩된 다른 머신을 입력으로 받아서 M_h를 사용해서 M_h의 결과가 0 이면 halt를 하고 1 이면 무한루프를 돌게 (즉 halt안하게) 합니다. 즉 M_o == code(M)===> M_h --> if 0 --> halt 1 --> 무한루프 (head를 무한히 계속 이동시킴) 그럼, 이 M_o역시 하나의 합법적인 머신이므로 halt할지 안할지를 M_h에 넣어서 돌려보면 0 또는 1의 값이 반환이 되겠죠. 그러나.. M_o에 code(M_o)를 줄때 아래의 두 경우가 있을 수 있습니다. 1. M_o가 halt안 할 경우 M_h가 code(M_o)를 입력으로 받아 1을 출력 했어야 함. 즉 M_o가 halt함을 의미함, 고로 모순. 2. M_o가 halt할 경우 M_h가 code(M_o)를 입력 받아 0을 출력 했어야 함. 즉 M_o가 halt안 함을 의미함. 고로 모순. 두 경우 모두 모순이므로.. halt할지 안할지 모르는 머신 M_o의 존재를 확인하게 된겁니다. 즉, M_h에 code(M_o)를 주면 M_h가 딱 부러지게 yes/no를 대답할 수 없는 반례가 있음이 입증 된것이죠. (혹시 틀린거 있으면 지적해주세요.. )