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

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

ماشین راستگردخواندنی توریگ (به انگلیسی: Read-only right moving Turing machines) نوعی خاص از ماشین تورینگ است.

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

برای تعریف باید از ۷فاکتور نامحدود استفاده میکنیم. که در آن:

  • حالتی محدودی از وضیعت هاست.
  • مجموعه متناهی از سمبل ها و نمادهاست.
  • نماد صفر(تنها نمادی که امکان اتفاق افتادنش به طور نامحدود حتی طی محاسبات هست. )
  • یک زیر مجموعه از که شامل نماد های ورودی جز b هست.
  • تابعی به نام تابع انتقال هست ،و R راستگرد است.
  • حالت اولیه است.
  • وضیعت نهایی یا حالت پذیرفته شده است.

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

{Q = { A، B، C، HALT

b = 0 = blank

Σ = , 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.