Post Correspondence Problem

상위 문서: Turing Machines

개요

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

Definition of PCP

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

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

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

$[\frac{a}{ab}],[\frac{b}{ca}],[\frac{ca}{a}],[\frac{a}{ab}],[\frac{abc}{c}]$

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

PCP Formulation as a Language

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

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

이때, 위와 같은 인스턴스를 문자열로 인코딩한 것은 $⟨P⟩$과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:

PCP $=\{⟨P⟩|P$는 매치가 존재하는 PCP 인스턴스이다.$\}$

이때, 위 튜링머신은 undecidable하다. ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$