Turing Machines - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:25:55Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:25 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[계산 이론 개론# Turing Machines\|계산 이론 개론]]		상위 문서: [[계산 이론 개론# Turing Machines\|계산 이론 개론]]

Pinkgo: /* Theorems about Undecidablity */

2025-12-03T23:51:47Z

Theorems about Undecidablity

@@ 233번째 줄: / 233번째 줄: @@
 위 튜링머신은 주어진 문법 G, H가 완전히 같은 언어를 만드는지 판별하는 튜링머신이며, undecidable하다.
+==[[Post Correspondence Problem]]==
-<math></math>
+[[Post Correspondence Problem|Post Correspondence Problem(PCP)]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.
 ==각주==

Pinkgo: /* Theorems about Undecidablity */

2025-12-01T19:04:44Z

Theorems about Undecidablity

← 이전 판		2025년 12월 1일 (월) 19:04 판
226번째 줄:		226번째 줄:

	또한 ALL_CFG 튜링 머신은 아래와 같은 튜링머신을 의미한다:		또한 ALL_CFG 튜링 머신은 아래와 같은 튜링머신을 의미한다:
	<math>ALL_{CFG}=\{\langle G\rangle\|</math>CFG <math>G</math>가 <math>\Sigma&</math> 전체를 생성한다.<math>\}</math>		<math>ALL_{CFG}=\{\langle G\rangle\|</math>CFG <math>G</math>가 <math>\Sigma*</math> 전체를 생성한다.<math>\}</math>
	위 튜링머신은 입력으로 주어진 문법이 가능한 모든 문자열을 모두 만드는지를 판단하는 튜링머신이며, undecidable하다.		위 튜링머신은 입력으로 주어진 문법이 가능한 모든 문자열을 모두 만드는지를 판단하는 튜링머신이며, undecidable하다.

Pinkgo: /* Undecidablity of Universal TM */

2025-12-01T19:04:28Z

Undecidablity of Universal TM

← 이전 판		2025년 12월 1일 (월) 19:04 판
215번째 줄:		215번째 줄:

	이때 <math>D</math>가 decidable하기 위해서는 <math>L(D)</math>와 <math>L(D)</math>의 여집합이 모두 recognizable해야 한다. 이때 <math>A_{TM}</math>은 recognizable하므로, <math>A_{TM}</math>의 여집합은 unrecognizable하다.		이때 <math>D</math>가 decidable하기 위해서는 <math>L(D)</math>와 <math>L(D)</math>의 여집합이 모두 recognizable해야 한다. 이때 <math>A_{TM}</math>은 recognizable하므로, <math>A_{TM}</math>의 여집합은 unrecognizable하다.

			===Theorems about Undecidablity===
			먼저, Halting 튜링 머신은 아래와 같은 튜링 머신을 의미한다.
			<math>HALT_{TM}=\{\langle M,m\rangle\|M</math>이 <math>w</math>에서 정지하는 모든 쌍<math>\}</math>
			위 튜링머신은 주어진 입력에 대해 튜링머신이 정지하는지를 판단하는 튜링머신이며, undecidable하다.

			다음으로 Emptiness 튜링 머신은 아래와 같은 튜링 머신을 의미한다:
			<math>E_{TM}=\{\langle M\rangle\|M</math>의 언어 <math>L(M)=\empty\}</math>
			위 튜링머신은 입력으로 주어진 M이 만드는 언어가 공집합인지를 판단하는 튜링머신이며, undecidable하다.

			또한 ALL_CFG 튜링 머신은 아래와 같은 튜링머신을 의미한다:
			<math>ALL_{CFG}=\{\langle G\rangle\|</math>CFG <math>G</math>가 <math>\Sigma&</math> 전체를 생성한다.<math>\}</math>
			위 튜링머신은 입력으로 주어진 문법이 가능한 모든 문자열을 모두 만드는지를 판단하는 튜링머신이며, undecidable하다.

			마지막으로, EQ_CFG 튜링 머신은 아래와 같은 튜링머신을 의미한다:
			<math>EQ_{CFG}=\{\langle G, H\rangle\|</math> 두 CFG <math>G, H</math>가 같은 언어를 생성한다.<math>\}</math>
			위 튜링머신은 주어진 문법 G, H가 완전히 같은 언어를 만드는지 판별하는 튜링머신이며, undecidable하다.


			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>

	==각주==		==각주==

Pinkgo: /* Universal Turing Machine */

2025-11-24T20:23:43Z

Universal Turing Machine

← 이전 판		2025년 11월 24일 (월) 20:23 판
194번째 줄:		194번째 줄:

	==Universal Turing Machine==		==Universal Turing Machine==
	아래와 같은 ~~튜링 머신을~~ 고려해보자:		아래와 같은 언어 <math>A_{TM}</math>을 고려해보자:
	<math>A_{TM}=\{\langle M, w\rangle\|M\,\,\, acept \,\,\, w\}</math>		<math>A_{TM}=\{\langle M, w\rangle\|M\,\,\, acept \,\,\, w\}</math>
	이러한 ~~튜링머신~~ <math>A_{TM}</math>은 입력으로 받은 <math>\langle M, w\rangle</math> 튜링 머신 <math>U</math>를 재구성한다. <math>U</math>는 <math>M</math>을 <math>w</math>에 대해 시뮬레이션하며, <math>M</math>이 accept/reject하면 <math>U</math>도 이에 따라 accept/reject한다. 물론 <math>M</math>이 무한 루프면 <math>U</math>도 멈추지 않고 무한 루프를 돈다.		이러한 언어 <math>A_{TM}</math>은 입력으로 받은 <math>\langle M, w\rangle</math> 튜링 머신 <math>U</math>를 재구성한다. 튜링 머신 <math>U</math>는 <math>M</math>을 <math>w</math>에 대해 시뮬레이션하며, <math>M</math>이 accept/reject하면 <math>U</math>도 이에 따라 accept/reject한다. 물론 <math>M</math>이 무한 루프면 <math>U</math>도 멈추지 않고 무한 루프를 돈다.
	이때, 다른 모든 튜링 머신 <math>M</math>을 입력받아 <math>w</math>에 대해 시뮬레이션하는 튜링 머신 <math>U</math>를 Universal ~~TM이라고~~ 한다.		이때, 다른 모든 튜링 머신 <math>M</math>을 입력받아 <math>w</math>에 대해 시뮬레이션하는 튜링 머신 <math>U</math>를 Universal 튜링 머신이라고 한다.

	===Undecidablity of Universal TM===		===Undecidablity of Universal TM===
214번째 줄:		214번째 줄:
	즉, <math>D</math>는 "M 자기 자신에 대해 M이 무엇을 하는지"를 무조건 반대로 따라 한다. 이때 <math>D(\langle D \rangle)</math>을 실행하면, 이는 모순을 일으킨다. 먼저 <math>D(\langle D \rangle)=accept</math>이면, <math>H(\langle M, \langle M \rangle \rangle)</math>은 D가 자기 자신을 accept한다고 판단하였으므로, <math>D</math>는 이를 뒤집어 reject해야 하기 때문이다. 이는 모순을 일으키며, <math>D(\langle D \rangle)=reject</math>일 때에도 마찬가지로 모순을 일으킨다. 따라서 <math>H</math>는 실제로 존재할 수 없으며, <math>A_{TM}</math>은 undecidable하다.		즉, <math>D</math>는 "M 자기 자신에 대해 M이 무엇을 하는지"를 무조건 반대로 따라 한다. 이때 <math>D(\langle D \rangle)</math>을 실행하면, 이는 모순을 일으킨다. 먼저 <math>D(\langle D \rangle)=accept</math>이면, <math>H(\langle M, \langle M \rangle \rangle)</math>은 D가 자기 자신을 accept한다고 판단하였으므로, <math>D</math>는 이를 뒤집어 reject해야 하기 때문이다. 이는 모순을 일으키며, <math>D(\langle D \rangle)=reject</math>일 때에도 마찬가지로 모순을 일으킨다. 따라서 <math>H</math>는 실제로 존재할 수 없으며, <math>A_{TM}</math>은 undecidable하다.

	이때 <math>D</math>가 decidable하기 위해서는 <math>L(D)</math>와 <math>L(D)</math>의 여집합이 모두 recognizable해야 한다. 이때 <math>A_{TM}</math>은 recognizable하므로, <math>A_{TM}</math>의 여집합은 unrecognizable하다.		이때 <math>D</math>가 decidable하기 위해서는 <math>L(D)</math>와 <math>L(D)</math>의 여집합이 모두 recognizable해야 한다. 이때 <math>A_{TM}</math>은 recognizable하므로, <math>A_{TM}</math>의 여집합은 unrecognizable하다.


	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~

	==각주==		==각주==

Pinkgo: /* Undecidablity of Universal TM */

2025-11-24T20:18:37Z

Undecidablity of Universal TM

← 이전 판		2025년 11월 24일 (월) 20:18 판
205번째 줄:		205번째 줄:
	<math>M</math>이 <math>w</math>를 reject하면 → H rejects		<math>M</math>이 <math>w</math>를 reject하면 → H rejects
	<math>M</math>이 loop해도 <math>H</math>는 반드시 accept/reject 중 하나를 출력한다.		<math>M</math>이 loop해도 <math>H</math>는 반드시 accept/reject 중 하나를 출력한다.
	하지만 이는 모순을 일으킨다. 또한 아래와 같은 튜링머신 <math>D</math>를 만들어야 한다:		하지만 이는 모순을 일으킨다. 또한 아래와 같은 universal 튜링머신 <math>D</math>를 만들어야 한다:
	입력: <math>\langle M \rangle</math>		입력: <math>\langle M \rangle</math>
	동작: <math>H(\langle M, \langle M\rangle \rangle)</math>을 실행한다.<ref>“M은 자기 자신을 문자열로 인코딩한 입력을 accept하는가?”를 H에게 물어본 것이다.</ref>		동작: <math>H(\langle M, \langle M\rangle \rangle)</math>을 실행한다.<ref>“M은 자기 자신을 문자열로 인코딩한 입력을 accept하는가?”를 H에게 물어본 것이다.</ref>
212번째 줄:		212번째 줄:
	H가 reject → D는 accept		H가 reject → D는 accept
	<math>\therefore\,\,\, D(M)=not \,\,\, H(\langle M, \langle M \rangle \rangle)</math>		<math>\therefore\,\,\, D(M)=not \,\,\, H(\langle M, \langle M \rangle \rangle)</math>
	즉, <math>D</math>는 "M 자기 자신에 대해 M이 무엇을 하는지"를 무조건 반대로 따라 한다. 이때 <math>D(\langle D \rangle)</math>을 실행하면, 이는 모순을 일으킨다. 먼저 <math>D(\langle D \rangle)=accept</math>이면, <math>H(\langle M, \langle M \rangle \rangle)</math>은 D가 자기 자신을 accept한다고 판단하였으므로, <math>D</math>는 이를 뒤집어 reject해야 하기 때문이다. 이는 모순을 일으키며, <math>D(\langle D \rangle)=reject</math>일 때에도 마찬가지로 모순을 일으킨다.		즉, <math>D</math>는 "M 자기 자신에 대해 M이 무엇을 하는지"를 무조건 반대로 따라 한다. 이때 <math>D(\langle D \rangle)</math>을 실행하면, 이는 모순을 일으킨다. 먼저 <math>D(\langle D \rangle)=accept</math>이면, <math>H(\langle M, \langle M \rangle \rangle)</math>은 D가 자기 자신을 accept한다고 판단하였으므로, <math>D</math>는 이를 뒤집어 reject해야 하기 때문이다. 이는 모순을 일으키며, <math>D(\langle D \rangle)=reject</math>일 때에도 마찬가지로 모순을 일으킨다. 따라서 <math>H</math>는 실제로 존재할 수 없으며, <math>A_{TM}</math>은 undecidable하다.
	<math></math>
	<math></math>		이때 <math>D</math>가 decidable하기 위해서는 <math>L(D)</math>와 <math>L(D)</math>의 여집합이 모두 recognizable해야 한다. 이때 <math>A_{TM}</math>은 recognizable하므로, <math>A_{TM}</math>의 여집합은 unrecognizable하다.
	<math></math>
	<math></math>
	<math></math>
	<math></math>		<math></math>
	<math></math>		<math></math>

Pinkgo: /* Undecidability */

2025-11-24T19:48:53Z

Undecidability

← 이전 판		2025년 11월 24일 (월) 19:48 판
191번째 줄:		191번째 줄:
	# 언어는 <math>\Sigma</math>의 부분집합이므로, 부분집합 전체는 <math>\mathcal{P}(\Sigma)</math>이므로 uncountable하다.		# 언어는 <math>\Sigma</math>의 부분집합이므로, 부분집합 전체는 <math>\mathcal{P}(\Sigma)</math>이므로 uncountable하다.
	# 따라서 모든 언어 중 대다수는 튜링 머신으로 인식(recognize)조차 할 수 없다.		# 따라서 모든 언어 중 대다수는 튜링 머신으로 인식(recognize)조차 할 수 없다.
	또한 recognizable이지만 decidable은 아닌 언어들이 존재한다는 것은 계산할 수 있는 것에는 본질적 한계가 있다는 것을 의미한다.		또한 recognizable이지만 decidable은 아닌 언어들이 존재한다는 것은 계산할 수 있는 것에는 본질적 한계가 있다는 것을 의미한다.

	==Universal Turing Machine==		==Universal Turing Machine==

Pinkgo: /* Undecidability */

2025-11-24T19:48:22Z

Undecidability

@@ 191번째 줄: / 191번째 줄: @@
 # 언어는 <math>\Sigma*</math>의 부분집합이므로, 부분집합 전체는 <math>\mathcal{P}(\Sigma*)</math>이므로 uncountable하다.
 # 따라서 모든 언어 중 대다수는 튜링 머신으로 인식(recognize)조차 할 수 없다.
 또한 recognizable이지만 decidable은 아닌 언어들이 존재한다는 것은 계산할 수 있는 것에는 본질적 한계가 있다는 것을 의미한다.
 ==각주==

Pinkgo: /* Relationship between Classes of Languages */

2025-11-24T16:45:30Z

Relationship between Classes of Languages

← 이전 판		2025년 11월 24일 (월) 16:45 판
185번째 줄:		185번째 줄:
	# Turing-recognizable 언어: 어떤 입력에 대해 halt하지 않고 무한 loop를 돌 수도 있다.		# Turing-recognizable 언어: 어떤 입력에 대해 halt하지 않고 무한 loop를 돌 수도 있다.
	# Recognizable 바깥의 언어들: 이는 더 심각한 수준의 undecidable 언어들이며, 어떤 알고리즘도 해당 언어를 인식조차 못한다.		# Recognizable 바깥의 언어들: 이는 더 심각한 수준의 undecidable 언어들이며, 어떤 알고리즘도 해당 언어를 인식조차 못한다.

			===Undecidability===
			위에서 언급하였듯이, 어떤 언어들은 Turing-recognizable조차 될 수 없는 undeterministic 언어이다. 이는 아래와 같은 논증을 통해 증명될 수 있다:
			# 모든 튜링 머신은 유한한 문자열로 인코딩할 수 있는데, 유한 문자열 집합 <math>\Sigma*</math>은 countable이다.
			# 언어는 <math>\Sigma</math>의 부분집합이므로, 부분집합 전체는 <math>\mathcal{P}(\Sigma)</math>이므로 uncountable하다.
			# 따라서 모든 언어 중 대다수는 튜링 머신으로 인식(recognize)조차 할 수 없다.
			또한 recognizable이지만 decidable은 아닌 언어들이 존재한다는 것은 계산할 수 있는 것에는 본질적 한계가 있다는 것을 의미한다.

	==각주==		==각주==

Pinkgo: /* Encoding Objects as Strings */

2025-11-20T03:43:10Z

Encoding Objects as Strings

← 이전 판		2025년 11월 20일 (목) 03:43 판
171번째 줄:		171번째 줄:
	이때 기계, 그래프, 정수 등의 어떤 객체 <math>x</math>를 문자열로 나타낸 것을 <math>\langle x\rangle</math>과 같이 표현할 수 있다. 예를 들어, <math>\langle DFA\rangle</math>는 DFA를 문자열로 encode한 것이고, <math>\langle G\rangle</math>은 그래프를 문자열 형태로 나타낸 것이다.		이때 기계, 그래프, 정수 등의 어떤 객체 <math>x</math>를 문자열로 나타낸 것을 <math>\langle x\rangle</math>과 같이 표현할 수 있다. 예를 들어, <math>\langle DFA\rangle</math>는 DFA를 문자열로 encode한 것이고, <math>\langle G\rangle</math>은 그래프를 문자열 형태로 나타낸 것이다.

	이때 문제의 결정가능성(decidability)<ref>문제가 이론적으로 해결 가능한지의 여부를 의미한다.</ref>에 대해서 고려할 때에는 인코딩의 길이와 방식같은 세부적인 사항이 문제되지 않는다. 이는 입력의 길이와 형식이 문제 풀이의 가능 여부에 영향을 미치지 않기 때문이다. 하지만 문제의 복잡도(complexity)를 고려할 때에는 인코딩의 길이가 큰 영향을 끼친다. 이는 인코딩의 길이가 입력 크기 n에 대해 직접적으로 영향을 미치기 때문이다. 따라서 이 경우에는 엄격하게 binary encoding을 규정해야 한다.		==Decidability and Complexity==
			문제의 결정가능성(decidability)<ref>문제가 이론적으로 해결 가능한지의 여부를 의미한다.</ref>에 대해서 고려할 때에는 인코딩의 길이와 방식같은 세부적인 사항이 문제되지 않는다. 이는 입력의 길이와 형식이 문제 풀이의 가능 여부에 영향을 미치지 않기 때문이다. 하지만 문제의 복잡도(complexity)를 고려할 때에는 인코딩의 길이가 큰 영향을 끼친다. 이는 인코딩의 길이가 입력 크기 n에 대해 직접적으로 영향을 미치기 때문이다. 따라서 이 경우에는 엄격하게 binary encoding을 규정해야 한다.

	===Relationship between Classes of Languages===		===Relationship between Classes of Languages===