편집
108
번
"튜링 머신"의 두 판 사이의 차이
주합루 오픈 위키
둘러보기로 이동검색으로 이동
편집 요약 없음
| (같은 사용자의 중간 판 3개는 보이지 않습니다) | |||
| 11번째 줄: | 11번째 줄: | ||
Non-computibility : 전산불가능이라는 말은 어떤 함수가 튜링머신으로 계산할 수 없을 때를 말한다. | Non-computibility : 전산불가능이라는 말은 어떤 함수가 튜링머신으로 계산할 수 없을 때를 말한다. | ||
Halting Problem | |||
임의의 튜링 머신과 인풋이 있을 때, 이것이 멈출 것인가를 결정할 수 있는 튜링 머신은 없다. | |||
Halting problem은 결정 또는 판정 문제의 하나이다. Decision problem | |||
튜링 머신에서 Circuit과의 관련성이 나오고 Computational complexity가 나온다. | |||
[[Computational Complexity]] | |||
