Post Correspondence Problem

상위 문서: Turing Machines

개요

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

Definition of PCP

PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다:

[math]\displaystyle{ [\frac{b}{ca}] }[/math]: 위 문자열은  "b", 아래 문자열은 "ca"

PCP는 도미노를 원하는 순서로 반복을 허용하여 나열했을 때, 위 문자열 전체가 아래 문자열 전체와 같은지(매치되는지) 확인하는 문제이다. 예를 들어:

[math]\displaystyle{ [\frac{a}{ab}], [\frac{b}{ca}], [\frac{ca}{a}], [\frac{a}{ab}], [\frac{abc}{c}] }[/math]

와 같은 도미노의 나열은 위, 아래 문자열이 "abcaaabc"로 같기 때문에 "매치(match)가 존재한다"가 문제의 답이다.

PCP Formulation as a Language

PCP의 인스턴스는 도미노들의 리스트이며, 아래와 같이 나타내어 진다:

[math]\displaystyle{ P=\{[\frac{t_1}{b_1}], [\frac{t_2}{b_2}], \cdots, [\frac{t_n}{b_n}]\} }[/math]

이때, 위와 같은 인스턴스를 문자열로 인코딩한 것은 [math]\displaystyle{ \langle P \rangle }[/math]과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:

PCP [math]\displaystyle{ = \{\langle P \rangle|P }[/math]는 매치가 존재하는 PCP 인스턴스이다.[math]\displaystyle{ \} }[/math]

이때, 위 튜링머신은 undecidable하다. [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]