Post Correspondence Problem - 편집 역사

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

2026-01-15T15:23:15Z

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

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

Pinkgo: /* Encoding Turing Machine Using PCP */

2025-12-04T02:40:22Z

Encoding Turing Machine Using PCP

@@ 23번째 줄: / 23번째 줄: @@
 PCP 도미노로 [[Turing Machines|튜링머신]] 계산을 인코딩하기 위해서 top을 항상 bottom보다 뒤처지게(lag) 만든다. 이는 튜링머신의 계산이 (tape의 내용, 상태)를 바탕으로 결과를 만들기 때문이다. 즉, Bottom은 “튜링머신이 실제로 생성해야 하는 올바른 다음 configuration(계산 기록)”을 의미하고, Top은 “그 bottom이 정말 올바른 계산을 통해 만들어졌는지 검증하기 위해 따라오는 줄”을 의미한다. 따라서 bottom이 먼저 확장되고, top이 그 확장을 ‘따라잡는’ 것이다. 예를 들어, 아래와 같은 PCP 도미노 나열은 튜링머신 계산 인코딩의 예를 보여준다:
   <math>[\frac{\#}{\#q_00100\#}]\,\,[\frac{q_0}{2q_7}]\,\,[\frac{1}{1}]\,\,[\frac{0}{0}]\,\,[\frac{0}{0}]\,\,[\frac{\#}{\#}]</math>
-위 예시에서 문자열들은 튜링머신의 계산 내용(현재 테이프, 상태 등)을 의미한다. 또한 위 예시는 매치를 이루기 위해서 추가적인 도미노를 요구한다. 이때 bottom이 accept 상태에 도달하여 "완성된 전체 계산 기록"을 포함한다면, top은 bottom을 마저 따라잡기 위해서 finalization 도미노를 사용한다.
+위 예시에서 문자열들은 튜링머신의 계산 내용(현재 테이프, 상태 등)을 의미한다. 또한 위 예시는 매치를 이루기 위해서 추가적인 도미노를 요구한다.
 ==각주==

Pinkgo: /* Encoding Turing Machine Using PCP */

2025-12-04T00:34:15Z

Encoding Turing Machine Using PCP

← 이전 판		2025년 12월 4일 (목) 00:34 판
23번째 줄:		23번째 줄:
	PCP 도미노로 [[Turing Machines\|튜링머신]] 계산을 인코딩하기 위해서 top을 항상 bottom보다 뒤처지게(lag) 만든다. 이는 튜링머신의 계산이 (tape의 내용, 상태)를 바탕으로 결과를 만들기 때문이다. 즉, Bottom은 “튜링머신이 실제로 생성해야 하는 올바른 다음 configuration(계산 기록)”을 의미하고, Top은 “그 bottom이 정말 올바른 계산을 통해 만들어졌는지 검증하기 위해 따라오는 줄”을 의미한다. 따라서 bottom이 먼저 확장되고, top이 그 확장을 ‘따라잡는’ 것이다. 예를 들어, 아래와 같은 PCP 도미노 나열은 튜링머신 계산 인코딩의 예를 보여준다:		PCP 도미노로 [[Turing Machines\|튜링머신]] 계산을 인코딩하기 위해서 top을 항상 bottom보다 뒤처지게(lag) 만든다. 이는 튜링머신의 계산이 (tape의 내용, 상태)를 바탕으로 결과를 만들기 때문이다. 즉, Bottom은 “튜링머신이 실제로 생성해야 하는 올바른 다음 configuration(계산 기록)”을 의미하고, Top은 “그 bottom이 정말 올바른 계산을 통해 만들어졌는지 검증하기 위해 따라오는 줄”을 의미한다. 따라서 bottom이 먼저 확장되고, top이 그 확장을 ‘따라잡는’ 것이다. 예를 들어, 아래와 같은 PCP 도미노 나열은 튜링머신 계산 인코딩의 예를 보여준다:
	<math>[\frac{\#}{\#q_00100\#}]\,\,[\frac{q_0}{2q_7}]\,\,[\frac{1}{1}]\,\,[\frac{0}{0}]\,\,[\frac{0}{0}]\,\,[\frac{\#}{\#}]</math>		<math>[\frac{\#}{\#q_00100\#}]\,\,[\frac{q_0}{2q_7}]\,\,[\frac{1}{1}]\,\,[\frac{0}{0}]\,\,[\frac{0}{0}]\,\,[\frac{\#}{\#}]</math>
	위 예시에서 문자열들은 튜링머신의 계산 내용(현재 테이프, 상태 등)을 의미한다. 또한 위 예시는 매치를 이루기 위해서 추가적인 도미노를 요구한다.		위 예시에서 문자열들은 튜링머신의 계산 내용(현재 테이프, 상태 등)을 의미한다. 또한 위 예시는 매치를 이루기 위해서 추가적인 도미노를 요구한다. 이때 bottom이 accept 상태에 도달하여 "완성된 전체 계산 기록"을 포함한다면, top은 bottom을 마저 따라잡기 위해서 finalization 도미노를 사용한다.


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

2025년 12월 4일 (목) 00:28에 Pinkgo님의 편집

2025-12-04T00:28:12Z

← 이전 판		2025년 12월 4일 (목) 00:28 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[Turing Machines/Post Correspondence Problem\|Turing Machines]]		상위 문서: [[Turing Machines#Post Correspondence Problem\|Turing Machines]]

	==개요==		==개요==

Pinkgo: /* PCP Formulation as a Language */

2025-12-04T00:27:58Z

PCP Formulation as a Language

← 이전 판		2025년 12월 4일 (목) 00:27 판
18번째 줄:		18번째 줄:
	이때, 위와 같은 인스턴스를 문자열로 [[Turing Machines#Encoding Objects as Strings\|인코딩]]한 것은 <math>\langle P \rangle</math>과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:		이때, 위와 같은 인스턴스를 문자열로 [[Turing Machines#Encoding Objects as Strings\|인코딩]]한 것은 <math>\langle P \rangle</math>과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:
	PCP <math>= \{\langle P \rangle\|P</math>는 매치가 존재하는 PCP 인스턴스이다.<math>\}</math>		PCP <math>= \{\langle P \rangle\|P</math>는 매치가 존재하는 PCP 인스턴스이다.<math>\}</math>
	이때, 위 튜링머신은 undecidable하다.		이때, 위 튜링머신은 undecidable하다.
	<math></math>
			==Encoding Turing Machine Using PCP==
			PCP 도미노로 [[Turing Machines\|튜링머신]] 계산을 인코딩하기 위해서 top을 항상 bottom보다 뒤처지게(lag) 만든다. 이는 튜링머신의 계산이 (tape의 내용, 상태)를 바탕으로 결과를 만들기 때문이다. 즉, Bottom은 “튜링머신이 실제로 생성해야 하는 올바른 다음 configuration(계산 기록)”을 의미하고, Top은 “그 bottom이 정말 올바른 계산을 통해 만들어졌는지 검증하기 위해 따라오는 줄”을 의미한다. 따라서 bottom이 먼저 확장되고, top이 그 확장을 ‘따라잡는’ 것이다. 예를 들어, 아래와 같은 PCP 도미노 나열은 튜링머신 계산 인코딩의 예를 보여준다:
			<math>[\frac{\#}{\#q_00100\#}]\,\,[\frac{q_0}{2q_7}]\,\,[\frac{1}{1}]\,\,[\frac{0}{0}]\,\,[\frac{0}{0}]\,\,[\frac{\#}{\#}]</math>
			위 예시에서 문자열들은 튜링머신의 계산 내용(현재 테이프, 상태 등)을 의미한다. 또한 위 예시는 매치를 이루기 위해서 추가적인 도미노를 요구한다.
	<math></math>		<math></math>
	<math></math>		<math></math>

Pinkgo: /* PCP Formulation as a Language */

2025-12-04T00:10:44Z

PCP Formulation as a Language

← 이전 판		2025년 12월 4일 (목) 00:10 판
15번째 줄:		15번째 줄:
	===PCP Formulation as a Language===		===PCP Formulation as a Language===
	PCP의 [[NP-Completeness#Problems\|인스턴스]]는 도미노들의 리스트이며, 아래와 같이 나타내어 진다:		PCP의 [[NP-Completeness#Problems\|인스턴스]]는 도미노들의 리스트이며, 아래와 같이 나타내어 진다:
	<math>P=\{[\frac{t_1}{b_1}], \frac{t_2}{b_2}], \cdots, \frac{t_n}{b_n}]\}</math>		<math>P=\{[\frac{t_1}{b_1}], [\frac{t_2}{b_2}], \cdots, [\frac{t_n}{b_n}]\}</math>
	이때, 위와 같은 인스턴스를 문자열로 [[Turing Machines#Encoding Objects as Strings\|인코딩]]한 것은 <math>\langle P \rangle</math>과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:		이때, 위와 같은 인스턴스를 문자열로 [[Turing Machines#Encoding Objects as Strings\|인코딩]]한 것은 <math>\langle P \rangle</math>과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:
	PCP <math>= \{\langle P \rangle\|P</math>는 매치가 존재하는 PCP 인스턴스이다.<math>\}</math>		PCP <math>= \{\langle P \rangle\|P</math>는 매치가 존재하는 PCP 인스턴스이다.<math>\}</math>

Pinkgo: /* Definition of PCP */

2025-12-04T00:08:43Z

Definition of PCP

← 이전 판		2025년 12월 4일 (목) 00:08 판
9번째 줄:		9번째 줄:
	PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다:		PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다:
	<math>[\frac{b}{ca}]</math>: 위 문자열은 "b", 아래 문자열은 "ca"		<math>[\frac{b}{ca}]</math>: 위 문자열은 "b", 아래 문자열은 "ca"
	PCP는 도미노를 원하는 순서로 반복을 허용하여 나열했을 때, 위 문자열 전체가 아래 문자열 전체와 같은지 확인하는 문제이다. 예를 들어:		PCP는 도미노를 원하는 순서로 반복을 허용하여 나열했을 때, 위 문자열 전체가 아래 문자열 전체와 같은지(매치되는지) 확인하는 문제이다. 예를 들어:
	<math>[\frac{a}{ab}], [\frac{b}{ca}], [\frac{ca}{a}], [\frac{a}{ab}], [\frac{abc}{c}]</math>		<math>[\frac{a}{ab}], [\frac{b}{ca}], [\frac{ca}{a}], [\frac{a}{ab}], [\frac{abc}{c}]</math>
	와 같은 도미노의 나열은 위, 아래 문자열이 "abcaaabc"로 같기 때문에 "존재한다"가 문제의 답이다.		와 같은 도미노의 나열은 위, 아래 문자열이 "abcaaabc"로 같기 때문에 "매치(match)가 존재한다"가 문제의 답이다.

	===PCP Formulation as a Language===		===PCP Formulation as a Language===

Pinkgo: /* PCP Formulation as a Language */

2025-12-04T00:08:08Z

PCP Formulation as a Language

← 이전 판		2025년 12월 4일 (목) 00:08 판
14번째 줄:		14번째 줄:

	===PCP Formulation as a Language===		===PCP Formulation as a Language===
			PCP의 [[NP-Completeness#Problems\|인스턴스]]는 도미노들의 리스트이며, 아래와 같이 나타내어 진다:
	<math></math>		<math>P=\{[\frac{t_1}{b_1}], \frac{t_2}{b_2}], \cdots, \frac{t_n}{b_n}]\}</math>
	<math></math>		이때, 위와 같은 인스턴스를 문자열로 [[Turing Machines#Encoding Objects as Strings\|인코딩]]한 것은 <math>\langle P \rangle</math>과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:
	<math></math>		PCP <math>= \{\langle P \rangle\|P</math>는 매치가 존재하는 PCP 인스턴스이다.<math>\}</math>
			이때, 위 튜링머신은 undecidable하다.
	<math></math>		<math></math>
	<math></math>		<math></math>

Pinkgo: 새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Turing Machines ==개요== 해당 문서에서는 Post Correspondence Problem(PCP)에 대해서 설명한다. ==Definition of PCP== PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다: $[\frac{b}{ca}]$ : 위 문...

2025-12-04T00:02:17Z

새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Turing Machines ==개요== 해당 문서에서는 Post Correspondence Problem(PCP)에 대해서 설명한다. ==Definition of PCP== PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다: <math>[\frac{b}{ca}]</math>: 위 문...

새 문서

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Turing Machines/Post Correspondence Problem|Turing Machines]]

==개요==
해당 문서에서는 Post Correspondence Problem(PCP)에 대해서 설명한다.

==Definition of PCP==
PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다:
<math>[\frac{b}{ca}]</math>: 위 문자열은 "b", 아래 문자열은 "ca"
PCP는 도미노를 원하는 순서로 반복을 허용하여 나열했을 때, 위 문자열 전체가 아래 문자열 전체와 같은지 확인하는 문제이다. 예를 들어:
<math>[\frac{a}{ab}], [\frac{b}{ca}], [\frac{ca}{a}], [\frac{a}{ab}], [\frac{abc}{c}]</math>
와 같은 도미노의 나열은 위, 아래 문자열이 "abcaaabc"로 같기 때문에 "존재한다"가 문제의 답이다.

===PCP Formulation as a Language===

<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>

==각주==