모든 언어는 튜링-인식(Turing-recognizalbe)한가? 답은 "아니다". 전체적인 증명 과정을 먼저 소개하고, 하나하나 관련 개념을 설명해보도록 하겠다.$\{0,1\}$의 알파벳에서1. $\{0,1\}^*$, 혹은 가능한 모든 튜링머신들의 집합은 $\mathbb{N}$과 같은 크기를 같는다.2. $\{0,1\}$으로 만들 수 있는 모든 문자열의 집합, 혹은 가능한 모든 언어들의 집합은 $2^\mathbb{N}$과 같은 크기를 같는다.3. $2^\mathbb{N}$은 불가산집합(uncountable set)이지만, $\mathbb{N}$은 가산집합(countable set)이다.4. 따라서, 가능한 모든 언어가 가능한 모든 튜링머신보다 그 종류가 많다.5. 따라서, 튜링-인식기(Turing-re..

우리는 지금까지 특정 기능만 수행하는 튜링머신을 다뤘다. 이것을 고정 튜링머신(Hardwired TM)이라고 부른다. 어떤 1번 TM이 w에 대해서 수행하는 일도, 2번 TM이 y에 대해 수행하는 일도, 3번 TM이 z에 대해 수행하는 일도 다 해내는 범용 튜링머신(Universal TM)에 대해 알아본다. 범용 튜링머신(Universal TM)만약 어떤 튜링머신 M에 대한 정보와 M이 원래 입력으로 받는 문자열 w를 함께 입력으로 받아서 동작하는 프로그래머 TM(programmable TM)이 있다면, 그것이 곧 범용 튜링머신(UTM)이 될 것이다. UTM은 M이 하는일을 흉내내서 w에 대한 연산을 처리한다. 이 UTM의 동작 방식은 쿠르트 괴델(Kurt Friedrich Gödel)에 의해 제시되었다..

이번 글에서는 튜링머신에 변형을 가해서, 새로운 튜링머신을 만든다. 새로운 튜링머신들은 기존 튜링머신보다 좋아보이지만, 우리의 직관과 추론에 도움을 줄 뿐, 기존 튜링머신과 같은 언어를 인식한다. 달리 말하면, 동등하다.헤드를 움직이지 않아도 되는 튜링머신앞선 튜링머신은 매 전이마다 헤드를 왼쪽이나 오른쪽으로 움직여야했다. 하지만, 변형된 튜링머신은 헤드를 가만히 있어도 된다. 원래 튜링머신의 전이 함수는 $Q\times\Gamma \to Q\times\Gamma\times\{L, R\}$ 이었다면, $Q\times\Gamma \to Q\times\Gamma\times\{L, R, S\}$의 함수다.왜 $S$를 추가하고도 기존 튜링머신과 동등할까? $\delta(q, a) = (q',b,S)$를 기존 튜..

튜링머신은 DFA, PDA와는 다른 또 새로운 오토마타다. 1. 읽기-쓰기 테이프(Read-write tape)를 갖는다. 테이프는 오른쪽으로 무한하다. 테이프의 초깃값은 입력 문자열로 채워져 있으며, 나머지는 blank(⊔)로 채워져있다.2. 최초에 헤드(Head)는 가장 왼쪽 셀(cell)을 가리키고 있다.3. 이제 오토마타는 매 전이마다 아래의 행동을 해야한다.→ 헤드를 오른쪽 혹은 왼쪽으로 움직인다.→ 심볼(symbol)의 값을 다른 심볼로 바꾸거나 그대로 둔다.→ 상태를 옮긴다. 튜링머신(TM)의 엄격한 정의(Formal Definition)$\text{TM is a 7-tuple}(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{rej..

":)" 문제가 있다고 생각해보자. ":)" 문제는 어떤 프로그램이 :)를 출력하는지 아닌지를 확인하는 문제다. 결론부터 말하자면, 컴퓨터는 이 단순한 문제를 항상 해결하지 못한다. 만약 이런 프로그램이 입력으로 들어온다면 문제의 정답을 "yes"라는걸 쉽게 알 수 있다.int main() { printf(":)");}하지만, 이런 문제라면 어떨까? 코드의 내용을 간단히 요약하자면, n을 입력받고, 가능한 모든 정수쌍 (x,y,z)를 순회하면서 $x^n+y^n=z^n$가 성립하면 ":)"를 출력하는 코드다. 가령 $n=2$라면, $3^2+4^2=5^2$에서 ":)"가 출력될 가능성이 있다.int main() { int n, tot, x, y; scanf("%d", &n); while(1) { ..

기본 정규 연산우리는 지금까지, 결정적/비결정적 유한 오토마타의 정의를 배웠다. 앞으로는 오토마타와 정규언어들의 속성들에 대해 다룰 것이다. 그 이전에, 이 속성들을 익히거나 증명하는데에 유용한 도구상자들을 준비했다. 아래의 3가지 연산은 정규 연산(regular operation)이라 불리는 기본적인 언어들 간의 연산이다. 어떤 언어 A,B에 대하여 아래처럼 정의된다. Kleene는 클레이니, 클리네 등으로 발음하는 듯 하다. 우리는 자연수 $\times$ 자연수가 자연수라는 사실을 알고 있다. 이것을 수학에서는 자연수가 곱셈에 대하여 닫혀있다(closed)고 말한다. 마찬가지로, 정규언어는 위 3가지 기본 정규 연산에 대하여 닫혀있다. 예를 들어, 정규언어와 정규언어의 union은 정규언어다. 달리 ..

카이스트 CS322 형식언어 및 오토마타 공부 내용입니다.정규언어1. 유한 결정적 오토마타(DFA, Deterministic Finite Automata)2. 유한 비결정적 오토마타(NFA, Non-deterministic Finite Automata)3. DFA와 NFA의 동등성4. 정규표현식과 NFA의 동등성5. Pumping Lemma6. 정규언어의 폐쇄성(Closure)과 동등성7. 정규언어의 최소화8. 마이힐-네로드 정리(Myhill-Nerode Theorem)9. Monadic Second-Order Logic(MSO) 문맥 자유 언어10. 문맥 자유 언어(Context Free Language) 11. 푸쉬다운 오토마타(PDA, Pushdown Automata)12. PDA와 CFG의 동등성..

Firebase Hosting에 도메인 주소를 추가했는데 아래와 같은 화면이 뜨면 당황스럽다.위 내용대로 3가지 가능성이 있다.1. 아직 배포를 안함(You haven't deployed an app yet)- 그렇지만 website-xxx.web.app 주소는 정상적으로 동작하고 있었기에, 이것은 배제할수 있었다.2. 빈 폴더를 배포함(You may have deployed an empty directory)- 역시 그럴리가 없다.3. 커스텀 도메인이지? 우리가 아직 설정을 덜 끝냄.(This is a custom domain, but we haven't finished setting it up yet.)- 무슨 설정을 덜 끝냈다는 걸까? 아마도 저 페이지는 서빙에 뭔가 문제가 있을 때 땜빵으로 서빙하..