مسئله تناظر پست

مسئلهٔ تناظر پست (به انگلیسی: Post correspondence problem) یک مسالهٔ تصمیم‌ناپذیر بر روی رشته‌ها است که در سال ۱۹۴۶ میلادی به‌وسیلهٔ امیل پست معرفی و اثبات شد. با نگاشت این مسئله بر روی مسائل تصمیم‌ناپذیر دیگر می‌توانیم تصمیم‌ناپذیری آن‌ها را نیز اثبات کنیم (مانند تصمیم‌ناپذیری ماشین‌های تورینگ).

علاوه بر این که یکی از دلایل اهمیت این مسئله اثبات دیگر مسائل تصمیم‌ناپذیر به‌وسیلهٔ آن است، می‌توان به این موضوع نیز اشاره نمود که درک و اثبات این مسئله بسیار ساده‌تر از دیگر مسائل تصمیم‌ناپذیر، مانند مسالهٔ توقف در ماشین تورینگ است.

تعریف مسئله

یک نمونه از مسئلهٔ تناظر پست را این‌گونه تعریف می‌کنیم:

هر نمونه از این مسئله شامل دو لیست از رشته‌هایی است که بر روی الفبای $\Sigma$ تعریف شده‌اند. فرض کنید این دو لیست $A$ و $B$ نام دارند که برای یک مقدار $k$ این‌گونه تعریف می‌شوند:

$A=x_{1},x_{2},...,x_{k}$

$B=y_{1},y_{2},...,y_{k}$

برای هر $i$ جفت $(x_{i},y_{i})$ را یک جفت تناظر می‌گویند.

جواب مسئلهٔ تناظر پست را نیز این‌گونه تعریف می‌کنیم:

برای یک نمونه از مسئله جواب وجود دارد اگر دنباله‌ای از اعداد صحیح مانند $i_{1}$، $i_{2}$، … و $i_{n}$ وجود داشته باشد که شرط زیر را ارضاء کند:

$x_{i_{1}}x_{i_{2}}..x_{i_{n}}=y_{i_{1}}y_{i_{2}}..y_{i_{n}}$

پس به‌طور کلی مسئلهٔ تناظر پست این‌گونه تعریف می‌شود:

«آیا برای یک نمونه از مسئلهٔ تناظر پست جوابی وجود دارد یا خیر؟»

مثال

فرض کنید $\Sigma =\{a,b\}$ و دو لیست $A$ و $B$ را این‌گونه در نظر بگیرید:

list A	list B
$x_{i}$	$y_{i}$	$i$
a	aaa	۱
abaaa	ab	۲
ab	b	۳

یک جواب برای این نمونه با $n=4$، این‌گونه است: $i_{1}=2,i_{2}=1,i_{3}=1,i_{4}=3$؛ زیرا در این صورت:

$x_{i_{1}}x_{i_{2}}x_{i_{3}}x_{i_{4}}=x_{2}x_{1}x_{1}x_{3}=abaaaaaab$

$y_{i_{1}}y_{i_{2}}y_{i_{3}}y_{i_{4}}=y_{2}y_{1}y_{1}y_{3}=abaaaaaab$

که این دو شرط $x_{i_{1}}x_{i_{2}}x_{i_{3}}x_{i_{4}}=y_{i_{1}}y_{i_{2}}y_{i_{3}}y_{i_{4}}$ را ارضاء می‌کنند.

اثبات تصمیم ناپذیری مسئلهٔ تناظر پست

ایدهٔ کلی برای اثبات تصمیم ناپذیری مسئلهٔ تناظر پست این است که آن را بر روی یک مسئلهٔ تصمیم ناپذیر معروف دیگری نگاشت کنیم و بهترین گزینه مسالهٔ توقف است. این نگاشت را این‌گونه در نظر بگیرید: «یک مسئلهٔ تناظر پست می‌تواند یک ماشین تورینگ دلخواه را با یک ورودی خاص اجرا کند. مسئلهٔ تناظر پست در صورتی جواب دارد اگر و فقط اگر ماشین تورینگ ورودی‌اش را قبول و توقف کند.»

منابع