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

ماشین راستگردخواندنی توریگ (به انگلیسی: 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 (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. Unknown parameter |coauthors= ignored (|author= suggested) (help)