상위 문서: 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"로 같기 때문에 "존재한다"가 문제의 답이다.
PCP Formulation as a Language
[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] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]