Halting probelm
decidable과 undecidable의 차이이다
accept, reject는 따라할 수 있지만 look for에 대해서 예측할 수 있다면,
리젝트 하면 되지만 예측못하면 어쩔 수 없다.
어떤 프로그램이 멈출까 안멈출까를 미리 판단할 수 있는가?
현재로서 undecidable하다는 것을 보니,
이것에 대해 판단할 수 없다.
지난 시간에 Turing 머신이 인풋을 받았을 때
accept, reject 할것에 대해 그대로 따라하면 된다.
밑에 따라하는 튜링머신이 universal 튜링머신이고,
이것은 현대컴퓨터의 모델이다.
잠깐 한동한 수학얘기를 하였다.
그 수학 얘기는 Turing recognizable밖에도 무언가가 있다는 것이다.
무한 개의 집합의 크기를 어떻게 비교하나? 자연수와 짝수의 개수는 같다.
'같다' 라고 하는 것이 유한수가 아니라 대략 이정도는 '같다'고 하는 것이다.
자연수와 일대일 매핑이 되는 것은 같다고 정의하는 것이다 .
자연수에 F(2n)을 매핑하면 1대1 매핑이 정확히 일어난다.
조금 사기같긴 하지만 이정도는 같다고 친다.
이런 자연수와 1:1 매핑이되는 것을 'countable'이라고 한다.
유리수의 개수도 자연수의 개수와 같다고 친다.
얘도 일대일 매픙의 방법이 있다.
유리수도 자연수와 크기가 같다고 친다.
집합의 크기가무한대인것은 다 자연수와 매핑이 되는가?
실수는 자연수와 매핑되지 않는다.
누군가 매핑이 있다고 하자. 그런데도 빠지는 것이있다. [대각선법]
대각선법에 의해 실수는 자연수보다 크다는 것이 결론이다.
∑ = {0.1} ==== > ∑* = { ε , 0, 1 , 00 , 01, 10 , 11 , ,,, }
합법적이지 않은 튜링머신의 문법으로 나타낸 것이 더 맞다.
스트링의 아주 일부만이 튜링머신의 문법에 맞는 것이다.
튜링머신은 M이 하나 정해지면 Language하나를 정의한다.
Language란, 어떤 string을 accept하는 것을 다 모은 것이다.
M을 Language하나를 딱 정의하는 것이다.
튜링머신의 개수와 Language의 개수가 딱 같으면 Turing - recognizable하다.
Language가 더 많으면 밖에도 무언가가 있어야한다.
이제는 Language의개수를 세어보려고 한다.
infinite binary sequence
000000--------
111111--------
infinite binary sequence 들의 전체집합을 B라고 했을 때,
이 집합에서 원소의 개수가 자연수의 집합의 원소의 개수보다 더 많을까 적을까 생각해보려고한다.
아깐 자연수의 집합이 짝수의 개수 집합의 개수가 같다는 것을 알고있어서 증명한 것이다.
답은 infinite binary sequence 이다.
"이 자연수보다 더 집합이 크다"는 것이 결론이다.
이것 또한 대각화로 증명이 가능하다 .
어떻게 매핑쌍이 있다고 치자 .
그것이 어떤 것이라도 B에 속하는 어떤 x는 나오지 않는다.
X를 무한한 infinite binary sequence 라고 하자. 얘는 얘랑 달라요!라고 얘기하고싶다.
B가 자연수의 개수보다 큽니다. 라고만 얘기하고 Language의 개수는얘기하지않았다.
Language의 개수와 B의개수가 같다고 얘기하려고 한다.
∑* = { ε , 0, 1 , 00 , 01, 10 , 11 , ,,, }
A = { 0, 00, 0000, 0000, ....}
b = 01011011,,,,
A는 정확히 딱 하나의 Sequence와 매핑이 되고,
특정 S1 이 A에 속하면 그러면 1이고 속하지 않으면 0이다.
그렇게 하면 이 bit string을 쭉 정의할 수 있따. 얘를 특정화한다.
세상에 있는 랭기지의 개수는 uncountable인데,
우리가 나타낼 수 있는 튜링머신(Turing machine)은 countable하다.
Halting Problem is Undecidable
Turing recognizable문제 밖에 무언가가 있다.
Atm 이라는 것은 string의 집합이다.
저 language가 decidable하다는 것은 이 language를 판단하는 튜링머신이 존재한다는 것이다.
튜링머신의 헤더가 앞으로도 가고 뒤로도 갈 수 있기 때문에 loop forever이 있다.
뒤로 못오게 막으면 헤더를 마음대로 못움직이기 때문에 CFL밖에 계산할 수 없다 .
w -> 멈출게 / loop forever.
halt(a, i) -> 어떤 튜링머신이 끝날지 안끝날 지 판단할 수 있어
- a가 i를 입력으로 받아서 끝나면 true
- a가 i이면 끝 X/ loop forever == > false
trouble (string s)
if halt(s,s ) == false
string t = return true
else
loop forever
trouble (t)
halt (t,t)
①
trouble(t) 끝나면 true
loop forever
②
trouble(t) 끝나지 않으면 false
담당교수가 남자인 가정인데 결론이 여자입니다. 라고 결론을 내면 가정이 잘못된 것이다.
halt가 false를 리턴하겠지 halt가 거짓을 리턴하려면 a가 의미하는 프로그램이 i를 입력으로 받아서 무한루프를 돈다는 의미이다.
loop forever해야된다. 라는 가정으로 바꿔보자.
반드시 trouble (t) 는 loop forever해야 된다.
가정하고 조금 더 풀어보았더니 trouble(t)가 return true로 끝난다. 라고 나와버렸다.
여기도 모순이다.
아래의 가정이 잘못되었다.
halt(a, i) -> 어떤 튜링머신이 끝날지 안끝날 지 판단할 수 있어
- a가 i를 입력으로 받아서 끝나면 true
- a가 i이면 끝 X/ loop forever == > false
halting이 존재하지 않습니다.라는 뜻이다.
꼼꼼히 한번 생각해보거라!! 물론 오픈북이기 떄문에 구멍 뜷어놓는 문제는 나오지 않는다.
그래서 더어려워요 교수님 책이 필요없는 문제들,,
