ماشین راستگرد خواندنی تورینگ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

ماشین راستگردخواندنی توریگ نوعی خاص از ماشین تورینگ است.

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

برای تعریف باید از ۷فاکتور نامحدود استفاده میکنیم. M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle که در آن:

  • Q حالتی محدودی از وضیعت هاست.
  • \Gamma مجموعه متناهی از سمبل ها و نمادهاست.
  • b \in \Gamma نماد صفر(تنها نمادی که امکان اتفاق افتادنش به طور نامحدود حتی طی محاسبات هست. )
  • \Sigma یک زیر مجموعه از \Gamma که شامل نماد های ورودی جز b هست.
  • \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{R\} تابعی به نام تابع انتقال هست ،و R راستگرد است.
  • q_0 \in Q حالت اولیه است.
  • F \subseteq Q وضیعت نهایی یا حالت پذیرفته شده است.

مثالی از ماشین راستگرد خواندنی تورینگ[ویرایش]

{Q = { A، B، C، HALT

b = 0 = blank

Σ = \varphi, empty set
δ = see state-table below
F = the one element set of final states HALT
جدول وضیعت برای ماشین فقط خواندنی با 3 حالت و 2 نماد

Current state A: Current state B: Current state C:
Write symbol: Move tape: Next state: Write symbol: Move tape: Next state: Write symbol: Move tape: Next state:
tape symbol is 0: 1 R B 1 R A 1 R B
tape symbol is 1: 1 R C 1 R B 1 N HALT

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

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

  • Davis, Martin; Ron Sigal, Elaine J. Weyuker (1994). Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd ed. ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.