Post Correspondence Problem 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[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>

==각주==