حساب کاربری
​
زمان تقریبی مطالعه: 6 دقیقه
لینک کوتاه

کاهش‌پذیری تورینگ

عمل کاهش تورینگ در نظریهٔ زبان‌ها و ماشین‌ها، فرایندی است که در آن یک مسئله مانند A {\displaystyle A}

به مسئله‌ای مانند B {\displaystyle B}
تبدیل می‌شود به‌طوری‌که حل مسئلهٔ B {\displaystyle B}
منجر به حل مسئلهٔ A {\displaystyle A}
خواهد شد. این فرایند را کاهش مسئلهٔ A {\displaystyle A}
به مسئلهٔ B {\displaystyle B}
می‌نامند. فرایند کاهش را به صورت تئوری با تابعی تعریف می‌کنند که در ورودی مسئله‌ای در قالب مسئلهٔ A {\displaystyle A}
را می‌خواند و در خروجی مسئله‌ای در قالب مسئلهٔ B {\displaystyle B}
را تولید می‌کند. در این صورت مسائل ورودی و خروجی تابع معادل شده و اگر مسئله حاصل در قالب B {\displaystyle B}
حل شود، پاسخ آن پاسخی بر مسئلهٔ A {\displaystyle A}
نیز خواهد بود.

لازم به ذکر است که عمل کاهش تنها وجود تابع معادل‌سازی یک مسئله با مسئله دیگر را تضمین می‌کند و حرفی از حل‌پذیری، تشخیص‌پذیری و تصمیم‌پذیری هر یک از مسائل درگیر به‌طور مستقل به میان نمی‌آورد. در واقع کاهش مسئلهٔ A {\displaystyle A}

به مسئلهٔ B {\displaystyle B}
، وابستگی دو مسئله به یکدیگر را بیان می‌کند و نشان‌دهندهٔ آن است که سختی حل مسئلهٔ A {\displaystyle A}
به میزان سختی حل مسئلهٔ B {\displaystyle B}
است.

فهرست

  • ۱ تاریخچه
  • ۲ کاربرد
  • ۳ تعریف
    • ۳.۱ دیدگاه الگوریتمی
    • ۳.۲ دیدگاه تئوری و ریاضیاتی
    • ۳.۳ دیدگاه ماشین‌های اوراکل
    • ۳.۴ هم‌ارزی تورینگ
  • ۴ مثال و مسائل معروف
  • ۵ ویژگی‌ها
  • ۶ منابع

تاریخچه

اولین بار وجود ارتباط میان حل مسائل با عنوان حل وابسته یا محاسبهٔ نسبی توسط آلن تورینگ در سال ۱۹۳۹ از دیدگاه ماشین‌های اوراکل مطرح شد. بعدتر آن را کاهش وابسته یا کاهش نسبی نیز نامیدند. پس از آن استیون کول کلینی در سال‌های ۱۹۴۳ و ۱۹۵۲ مفهومی مشابه را از دیدگاه توابع بازگشتی مطرح کرد. در سال ۱۹۴۴ امیل لئون پست عنوان «کاهش تورینگ» را برای تعریف این مفهوم به کار گرفت. کاهش تورینگ در زمان خطی نیز به نام استیون کوک، کاهش کوک نام گرفت.

کاربرد

ما در عمل، به‌طور معمول روزانه بارها و بارها از فرایند کاهش استفاده می‌کنیم. برای مثال فرض کنید می‌خواهید از شهری به شهر دیگری سفر کنید. برای این کار نیاز به تهیهٔ بلیت برای سفر دارید. برای تهیهٔ بلیت به تهیهٔ پول نیاز دارید و برای تهیهٔ پول باید کار کنید. در همین فرایند چند مرحله‌ای معمول، مسئلهٔ سفر به مسئلهٔ خرید بلیت، مسئلهٔ خرید بلیت به مسئلهٔ تهیهٔ پول و مسئلهٔ تهیهٔ پول به مسئلهٔ کار کردن کاهش یافت. بنابراین عمل کاهش به صورت کلی بخشی از ساده‌ترین اعمال زندگی روزمرهٔ ما می‌باشد.

کاربرد فنی‌تر عمل کاهش، در مسائل ریاضی می‌باشد. یکی از این کاربردها دسته‌بندی مسائل ریاضی است. این دسته‌بندی، مسائل مختلف را از نظر تشخیص‌پذیری، تصمیم‌پذیری، زمان و حافظه به هم مربوط می‌کند و تلاش‌های دنیای علم را در راستای حل مسائل سامان می‌بخشد.

تعریف

دیدگاه الگوریتمی

از دیدگاه الگوریتمی، شرح عمل کاهش به این صورت است که الگوریتمی برای حل مسئلهٔ A {\displaystyle A}

تعریف می‌شود به‌طوری‌که در آن بخش اصلی حل مسئله بر دوش زیرروالی است که خود شامل الگوریتم حل مسئلهٔ B {\displaystyle B}
است. این پیاده‌سازی را می‌توان به کمک ماشین‌های اوراکل به انجام رساند.

دیدگاه تئوری و ریاضیاتی

دو مجموعهٔ A {\displaystyle A}

و B {\displaystyle B}
متشکل از اعداد طبیعی را در نظر بگیرید. کاهش‌پذیری A {\displaystyle A}
به B {\displaystyle B}
به معنای وجود تابعی است که دامنهٔ آن مجموعهٔ A {\displaystyle A}
و تابع هدف آن مجموعهٔ B {\displaystyle B}
باشد و به صورت زیر نمایش داده می‌شود:

A ≤ T B {\displaystyle A\leq _{T}B}

دیدگاه ماشین‌های اوراکل

از دیدگاه ماشین‌های اوراکل، هرگاه مسئله‌ای مانند A {\displaystyle A}

به مسئله‌ای مانند B {\displaystyle B}
کاهش‌پذیر باشد، به ازای هر الگوریتمی برای B {\displaystyle B}
می‌توان الگوریتمی برای A {\displaystyle A}
تعبیه کرد به این صورت که به ازای هر فراخوانی اوراکل B {\displaystyle B}
در ماشین اوراکل A {\displaystyle A}
الگوریتم مربوط به B {\displaystyle B}
را قرار داد. از آنجایی که ممکن است ماشین اوراکل A {\displaystyle A}
چندین بار ماشین اوراکل B {\displaystyle B}
را فراخوانی کند، زمان و حافظهٔ مورد نیاز این الگوریتم ممکن است به صورت چشم‌گیری از زمان و حافظهٔ مورد نیاز ماشین اوراکل B {\displaystyle B}
و یا ماشین‌های اوراکل دیگر مربوط به A {\displaystyle A}
بیشتر باشد. به همین علت تبدیل مسئلهٔ A {\displaystyle A}
به مسئلهٔ B {\displaystyle B}
از نظر زمانی و حافظه مورد توجه و اهمیت قرار گرفته‌است.

هم‌ارزی تورینگ

اگر A {\displaystyle A}

و B {\displaystyle B}
هر دو به یکدیگر کاهش‌پذیر باشند، A {\displaystyle A}
و B {\displaystyle B}
را هم‌ارز تورینگ می‌نامند. به این صورت تمامی مسائل به کلاس‌های هم‌ارزی تورینگ تقسیم خواهد شد که عضویت در هر یک از این کلاس‌ها درجه تورینگ مسائل را نشان می‌دهد.

در یک مجموعه از مسائل مانند مجموعهٔ S {\displaystyle S}

، اگر هر مسئله مانند X {\displaystyle X}
در مجموعهٔ S {\displaystyle S}
، به مسئلهٔ مشخصی مانند Y {\displaystyle Y}
کاهش‌پذیر باشد، Y {\displaystyle Y}
را تورینگ-سخت برای مجموعهٔ S {\displaystyle S}
می‌نامند. همچنین در صورتی که Y {\displaystyle Y}
خود عضوی از مجموعهٔ S {\displaystyle S}
باشد، آن را تورینگ-تمام برای مجموعهٔ S {\displaystyle S}
تعریف می‌کنند.

مثال و مسائل معروف

عمل کاهش را در اثبات تصمیم‌ناپذیری یکی از مسائل معروف ریاضی شرح می‌دهیم. مجموعهٔ E Q T M {\displaystyle EQ_{TM}}

را مجموعه جفت ماشین تورینگ‌هایی تعریف می‌کنیم که تولیدکننده یک زبان مساوی هستند. مجموعهٔ E T M {\displaystyle E_{TM}}
را نیز مجموعه ماشین تورینگ‌هایی تعریف می‌کنیم که زبانشان تهی است. می‌دانیم مسئلهٔ E T M {\displaystyle E_{TM}}
تصمیم‌ناپذیر است. با کاهش مسئلهٔ E T M {\displaystyle E_{TM}}
به مسئلهٔ E Q T M {\displaystyle EQ_{TM}}
می‌توان نتیجه گرفت که E Q T M {\displaystyle EQ_{TM}}
نیز تصمیم‌ناپذیر است. زیرا در صورتی که تصمیم‌پذیر باشد، با توجه به این که E T M {\displaystyle E_{TM}}
به این مسئله کاهش یافته، E T M {\displaystyle E_{TM}}
نیز تصمیم‌پذیر خواهد شد که یک تناقض را نتیجه می‌دهد. برای کاهش مسئلهٔ E T M {\displaystyle E_{TM}}
به مسئلهٔ E Q T M {\displaystyle EQ_{TM}}
، خاصیت تهی بودن یک زبان را می‌توان با خاصیت تساوی آن زبان با یک زبان تهی معادل کرد. بنابراین در صورتی که ورودی مسئلهٔ E T M {\displaystyle E_{TM}}
را با ماشین یک زبان تهی به مسئلهٔ E Q T M {\displaystyle EQ_{TM}}
بدهیم، پاسخ آن برای E T M {\displaystyle E_{TM}}
نیز پاسخی صحیح است. بنابراین کاهشی از مسئلهٔ E T M {\displaystyle E_{TM}}
به E Q T M {\displaystyle EQ_{TM}}
وجود دارد و هر مسئله از E T M {\displaystyle E_{TM}}
را می‌توان با E Q T M {\displaystyle EQ_{TM}}
حل کرد.

به صورت مشابه تصمیم‌ناپذیری مسائلی همچون مجموعهٔ ماشین‌های زبان‌های منظم، ماشین‌های با نوار محدود و زبان تهی، مسئلهٔ معروف P C P {\displaystyle PCP}

و دیگر مسائل ثابت شده‌است.

ویژگی‌ها

  • هر مجموعه به متمم خود کاهش‌پذیر است.
  • هر مجموعهٔ بازگشتی به هر مجموعهٔ دیگر کاهش‌پذیر است.
  • کاهش‌پذیری تورینگ قابلیت تراگذری دارد. به بیان دیگر اگر A ≤ T B {\displaystyle A\leq _{T}B}
    و B ≤ T C {\displaystyle B\leq _{T}C}
    آنگاه داریم A ≤ T C {\displaystyle A\leq _{T}C}
    . در عمل می‌توان این قانون را به این صورت تفهیم کرد که تبدیل مسئلهٔ A {\displaystyle A}
    به C {\displaystyle C}
    با اعمال متوالی توابع تبدیل A {\displaystyle A}
    به B {\displaystyle B}
    و تبدیل B {\displaystyle B}
    به C {\displaystyle C}
    بر روی مسئله‌ای در قالب A {\displaystyle A}
    صورت می‌پذیرد.

منابع

  • S. C. Kleene, 1952. Introduction to Metamathematics. Amsterdam: North-Holland
  • Introduction to the Theory of Computation (second edition), by Michael. Sipser, Thomson Course Technology, Boston, 2006
  • Turing Computability: Theory and Applications by Robert Soare, Published by ACM 2016
  • ویکی‌پدیای انگلیسی
آخرین نظرات
کلیه حقوق این تارنما متعلق به فرا دانشنامه ویکی بین است.