ماشین تورینگ

از ویکی‌پدیا، دانشنامهٔ آزاد

پرش به: ناوبری, جستجو

در تئوری محاسبات ماشین تورینگ (Turing machine) به یک ماشین حالات متناهی اطلاق می‌شود که درآن با وقوع هر عبور[۱] یک نماد[۲] برروی نوار چاپ می‌شود. با وجود اینکه مکانیزم ماشین تورینگ مقدماتی است مفهومش برای پوشش عملکردهای بسیار پیچیده کافی و گسترده‌است. حافظه این ماشین ساختاری بسیار ساده دارد. یعنی می‌تواند بصورت یک آرایه یک بعدی از عناصر (سلولها) که هر یک می‌توانند حافظ تنها یک نماد باشند، باشد. این آرایه از هر دو طرف باز و نامحدود است (حافظه بینهایت) است و اطلاعات آن می‌توانند به هر ترتیبی فراخوانی شوند.

فهرست مندرجات

[ویرایش] تاریخچه

معرفی ماشین تورینگ توسط دانشمند انگلیسی آلن تورینگ در سال ۱۹۳۶ میلادی، گام دیگری را در مسیر ایجاد و پیدايش ماشین‌های محاسباتی حالات متناهی به نمایش می‌گذارد.

[ویرایش] تعریف

ماشین تورینگ عبارت است از یک پنج‌تایی به‌صورت M = (Q, \Sigma, \Gamma, \delta, q_0) \!، که در اینجا:

  • M \! برای نمایش مفهوم ماشین انتخاب شده است.
  • Q \! مجموعه‌ای است متناهی، از حالات داخلی.[۳]
  • \Gamma \! مجموعه‌ای متناهی موسوم به الفبای نوار[۴] و حاوی نمادی مخصوص B \! برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
  • \Sigma \! زیرمجموعه‌ای است از \Gamma - \{B\} \! و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه‌ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی‌توانند بعنوان ورودی استفاده شوند.
  • \delta \! عبارت است از یک تابع جزئی[۵] موسوم به تابع انتقال[۶]، از دامنهٔ Q \times \Gamma \! به برد Q \times \Gamma \times \{L, R\} \!.
  • q_0 \! حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را درآن آغاز می‌کنیم.

بطور کلی \delta \! یک تابع جزئی روی Q \! \times \Gamma \! است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.

[ویرایش] پانویس

‎

  1. ↑ Transition
  2. ↑ Symbol
  3. ↑ Internal States
  4. ↑ Tape alphabet
  5. ↑ Partial function
  6. ↑ Transition function


[ویرایش] جستارهای وابسته

[ویرایش] منابع

‎

  • Sudkamp, T. A., An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed., Pearson Education, Inc., 2006. ISBN 0-321-32221-5
  • Johnsonbaugh, R., Discrete Mathematics, 4th ed., Prentice Hall, 1993. ISBN 0-13-518242-5
  • Jackson, Jr., Philip C., Introduction to Artificial Intelligence, 2nd enlarged and slightly corrected ed., Dover Publications, Inc., New York, 1985. ISBN 0-486-24864-X
  • پیتر لینز. «ماشین‌های تورینگ». مقدمه‌ای بر نظریه زبانها و ماشینها. ترجمهٔ مهدی صادق‌زاده. سوم. چاپ دوم، تهران: خراسان، 1387، ISBN 964-6342-49-3. ‏
برگرفته از «http://fa.wikipedia.org/wiki/%D9%85%D8%A7%D8%B4%DB%8C%D9%86_%D8%AA%D9%88%D8%B1%DB%8C%D9%86%DA%AF»