CS/Computation Theory (2023-2)3 [계산 이론] The Halting Problem 컴퓨터를 전공 배우고 있는 사람 입장에서, Halting Problem정도는 한번 증명해 보고 정리해 두면 좋을 것 같다 생각하여 글을 남겨봅니다! 1. Halting Problem 이란? 우선 정의부터 살펴보자! There’s no algorithm that can look at a program’s source code and always correctly determine if the program will run forever or not. 사람의 언어로 조금 바꿔보면, 유한시간안에 프로그램을 실행해보지 않고 정지할지 말지를 결정하는 알고리즘은 존재하지 않는다는 의미이다! 2. Proof by contradiction 다음과 같이 "input과 output을 갖는 halt라는 프로그램(알고리즘)이.. CS/Computation Theory (2023-2) 2023. 12. 12. [계산 이론] Some languages are not Turing-recognizable 이번 증명을 통하여 Turing Machine이 recognize하지 못하는 Language가 있음을 보일 것 이다. 1. 모든 Turing Machine은 countable 하다 모든 튜링머신이 Countable함을 보이기 전에, 우선 모든 String의 집합(∑*)이 모든 alphabet ∑에 대하여 count할 수 있음을 보일것 입니다. ∑* 의 list를 길이가 0, 길이가 1, 길이가 2 ... 순으로 아래로 적어내려 갈 수 있습니다. 또한 각 lenght마다 finite한 수의 String이 있습니다. 이를 그림으로 살펴보면 다음과 같은데, 길이가 0인 String에는 입실론이, 1에는 0과 1, 등등 이 존재합니다. 모든 자연수 1, 2, 3, ... N에 대하여 mapping가능한 하나의 .. CS/Computation Theory (2023-2) 2023. 12. 12. [계산 이론] Non-Context-Free Languages 1. The Pumping Lemma for Context-Free-Languages(CFL) 우리는 보조 정리인 Pumping Lemma를 활용하여 CFL이 아님을 보일 것 이다. 만약 A가 Context-free-lenaguage라면, pumping length p가 존재하며, A의 어떤 String S라도 최소 p만큼의 길이를 갖는다. 또한 그러한 S는 5조각, 즉 S = uvxyz로 나눌 수 있으며, 다음 조건을 만족한다. 조건 2에 의하여 v 또는 y 가 동시에 empty string일수는 없다. 조건 3에 의하여 v,x,y의 길이는 최대 p이다. 2. Proof G를 CFL A의 Context-Free-Grammer(CFG)라 하자. b를 symbol의 최대 수 라고 하자. 예를 들면 다음 C.. CS/Computation Theory (2023-2) 2023. 12. 10. 이전 1 다음
