학습목표 Turing Machine의 작동원리와 일반적인 계산모형으로서의 가능성 이해 제 9장. Turing Machines 학습목표 Turing Machine의 작동원리와 일반적인 계산모형으로서의 가능성 이해  Welcome to 현실세계의 계산모형

개요 철저한 증명보다는 개념적인 이해 및 응용 예 숙지 필요  왜? 너무 자세히 하기에 너무 복잡해서리… 하지만, 기본 방법은 이미 알고있는… 표준 튜링 머신 가장 강력한 오토메타 계산 한계 규명의 도구 튜링 머신의 결합 Turing Thesis 기본 구성 및 왔다리 갔다리 방식의 작동원리 이해 실제 컴퓨터 언어에서 처럼 복잡한 문제를 해결하는데는 단순한 모듈의 결합이 제격! 튜링 머신의 power를 보여주는 명제

Standard TM 여러 가지 정의의 TM에 대한 표준정의 cu R/W head Tape

TM의 정의: Halt Standard TM Def A TM is to halt iff it reaches a configuration for which δ is not defined  infinite loop 이제까지 우리가 알고 있는 계산기의 프로그래밍과 유사하지요.

Standard TM TM의 정의: 기계의 상태 표현 Def instantaneous description

TM의 정의: Computation Standard TM Def computation = sequence of configurations leading to a halt state cf infinite loop

TM as Language Accepters cf. if w L(M) 1. machine can halt in a nonfinal state 2. it can enter an infinite loop & never halt

TM as Language Accepters: 예 좀 복잡해 보이지만 상식적인 문제해결 방식과 같죠!

TM as Language Accepters: 예2

TM as Transducers purpose of computation = transform input into output

TM as Transducers: 예 Ex design a TM to copy strings of 1’s

TM as Transducers: 예2

Standard TM: Exercises 9.1 5 : 간단한 문제로 답도 간단합니다. 8 : 좀 지루한 작업을 필요로 합니다. 만, 대부분의 TM과 관련된 문제가 이와 같은 작업을 필요로 하기 때문에 한번 해봅시다. 어쨌든, pda가 할 수 없는 일을 TM이 한다는 사실에 유의할 것.

Combining TM for Complicated Tasks Adder A x + y x≥y f(x, y) Comparer C x, y x<y Eraser E

Combining TM for Complicated Tasks: 예 Ex

Combining TM for Complicated Tasks: 예2 Subprogram manipulation in TM divide the tape into several regions Region separator # Workspace for A Workspace for B T Ex design a TM to multiply two positive integers Idea : repeated copying of the multiplicand y for each 1 in the multiplier x 1. Repeat the following steps until x contains no more 1’s Find a 1 in x and replace it with another symbol a Replace the leftmost 0 by 0y 2. Replace all a’s with 1’s

Combining TM: Exercises 9.2 개념적으로는 어려운 문제가 아니지만, 대부분 일반적인 프로그래밍과 관련된 지루한 코딩이 필요합니다. 2번과 4번 정도를 한번 시도해 봅시다.

Turing’s Thesis TM > pda TM ? = digital computer Any computation by mechanical means by some TM 1. Anything that can be done on any existing digital computer can also by a TM No one has yet been able to suggest a problem, solvable by what we consider an algorithm, for which a TM cannot be written Alternative models have been proposed, but none of them are more powerful than TM model 2. 3.

Turing’s Thesis: Exercises 9.3 따로 연습하기 어려운 부분이기는 한데… 3문제 모두 한번 생각은 해봅시다.