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

مسئلهٔ تناظر پست (به انگلیسی: Post correspondence problem) یک مسالهٔ تصمیم‌ناپذیر بر روی رشته‌ها است که در سال ۱۹۴۶ میلادی به‌وسیلهٔ امیل پست معرفی و اثبات شد.Post, Emil L. "A variant of a recursively unsolvable problem." Bulletin of the American Mathematical Society 52.4 (1946): 264-268. با نگاشت این مسئله بر روی مسائل تصمیم‌ناپذیر دیگر می‌توانیم تصمیم‌ناپذیری آن‌ها را نیز اثبات کنیم (مانند تصمیم‌ناپذیری ماشین‌های تورینگ).

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

 تعریف مسئله 
یک نمونه از مسئلهٔ تناظر پست را این‌گونه تعریف می‌کنیم:Hopcroft, John E. , Rajeev Motwani, and Jeffrey D. Ullman. "Automata theory, languages, and computation." International Edition 24 (2006).

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

برای هر  جفت  را یک جفت تناظر می‌گویند.

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

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

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

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

 مثال 
فرض کنید  و دو لیست  و  را این‌گونه در نظر بگیرید:

 list A list B  aaaa۱abaaaab۲abb۳

یک جواب برای این نمونه با ، این‌گونه است: ؛ زیرا در این صورت:

که این دو شرط  را ارضاء می‌کنند.

 اثبات تصمیم ناپذیری مسئلهٔ تناظر پست 
ایدهٔ کلی برای اثبات تصمیم ناپذیری مسئلهٔ تناظر پست این است که آن را بر روی یک مسئلهٔ تصمیم ناپذیر معروف دیگری نگاشت کنیم و بهترین گزینه مسالهٔ توقف است.Sipser, Michael. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006. این نگاشت را این‌گونه در نظر بگیرید: «یک مسئلهٔ تناظر پست می‌تواند یک ماشین تورینگ دلخواه را با یک ورودی خاص اجرا کند. مسئلهٔ تناظر پست در صورتی جواب دارد اگر و فقط اگر ماشین تورینگ ورودی‌اش را قبول و توقف کند.»

 منابع 

رده:مسئله‌های تصمیم‌ناپذیر
رده:نظریه بازگشت
رده:نظریه محاسبات