ماشین های خواندنی تورینگ یا ماشین های تعیین پذیر حالات متناهی ۲مسیره (به انگلیسی: Read-only Turing machine یا Two-way deterministic finite-state automaton) (مخفف انگلیسی: 2DFA) رده ای از مدل های محاسبه پذیری هستند که مانند یک ماشین تورینگ استاندارد عمل می کنند و می توانند در هر ۲ جهت روی نوار حرکت کنند اما نمی توانند چیزی بنویسند.
Q {\displaystyle Q} مجموعهٔ متناهی حالات است.
Σ {\displaystyle \Sigma } مجموعهٔ متناهی الفبای ورودی است.
Γ {\displaystyle \Gamma } مجموعهٔ متناهی الفبای نوار است.
⊢∈ Γ − Σ {\displaystyle \vdash \in \Gamma -\Sigma } نشانگر پایان از سمت چپ است.
_ ∈ Γ − Σ {\displaystyle \_\in \Gamma -\Sigma } نمایشگر یک فاصلهٔ خالی روی نوار است.
δ : Q × Γ → Q × Γ × { L , R } {\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}} تابع انتقال است.
s ∈ Q {\displaystyle s\in Q} حالت شروع است.
t ∈ Q {\displaystyle t\in Q} حالت پذیرش است.
r ∈ Q , r ≠ t {\displaystyle r\in Q,
r\neq t} حالت عدم پذیرش است
در حقیقت این ماشین ها از نظر قدرت محاسباتی معادل یک ماشین تعیین پذیر حالات متناهی هستند که فقط می توانند عمل تجزیه و تحلیل را روی یک زبان منظم انجام دهند.
یک ماشین تورینگ استاندارد توسط یک ۹ تائی به صورت M = (Q, \Sigma, \Gamma, \vdash, \_, \delta, s, t, r) تعریف می شود که در آن:
اگر حالت ابتدایی q {\displaystyle q} باشد، با خواندن نماد a {\displaystyle a} ، یک انتقال به صورت δ ( q , a ) = ( q 2 , a 2 , d ) {\displaystyle \delta (q,a)=(q_{2},a_{2},d)} تعریف می شود که در آن a 2 {\displaystyle a_{2}} به جای a {\displaystyle a} قرار می گیرد و حالت ماشین به q 2 {\displaystyle q_{2}} منتقل می شود و کلاهک خواندن در جهت d {\displaystyle d} (چپ یا راست) برای خواندن ورودی بعدی حرکت می کند. در2DFA، a 2 {\displaystyle a_{2}} همیشه با a {\displaystyle a} برابر است.این مدل معادل با DFA است. اثبات آن شامل ساخت جدولی است که نتایج حاصل از پیمایش معکوس با شرایط خاص را برای هر وضعیت داده شده فهرست می کند. در آغاز محاسبه، پیمایش معکوس برابر با تلاش برای گذشتن از نشانگر پایان است.
Q {\displaystyle Q} مجموعهٔ متناهی حالات است.
Σ {\displaystyle \Sigma } مجموعهٔ متناهی الفبای ورودی است.
Γ {\displaystyle \Gamma } مجموعهٔ متناهی الفبای نوار است.
⊢∈ Γ − Σ {\displaystyle \vdash \in \Gamma -\Sigma } نشانگر پایان از سمت چپ است.
_ ∈ Γ − Σ {\displaystyle \_\in \Gamma -\Sigma } نمایشگر یک فاصلهٔ خالی روی نوار است.
δ : Q × Γ → Q × Γ × { L , R } {\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}} تابع انتقال است.
s ∈ Q {\displaystyle s\in Q} حالت شروع است.
t ∈ Q {\displaystyle t\in Q} حالت پذیرش است.
r ∈ Q , r ≠ t {\displaystyle r\in Q,
r\neq t} حالت عدم پذیرش است
در حقیقت این ماشین ها از نظر قدرت محاسباتی معادل یک ماشین تعیین پذیر حالات متناهی هستند که فقط می توانند عمل تجزیه و تحلیل را روی یک زبان منظم انجام دهند.
یک ماشین تورینگ استاندارد توسط یک ۹ تائی به صورت M = (Q, \Sigma, \Gamma, \vdash, \_, \delta, s, t, r) تعریف می شود که در آن:
اگر حالت ابتدایی q {\displaystyle q} باشد، با خواندن نماد a {\displaystyle a} ، یک انتقال به صورت δ ( q , a ) = ( q 2 , a 2 , d ) {\displaystyle \delta (q,a)=(q_{2},a_{2},d)} تعریف می شود که در آن a 2 {\displaystyle a_{2}} به جای a {\displaystyle a} قرار می گیرد و حالت ماشین به q 2 {\displaystyle q_{2}} منتقل می شود و کلاهک خواندن در جهت d {\displaystyle d} (چپ یا راست) برای خواندن ورودی بعدی حرکت می کند. در2DFA، a 2 {\displaystyle a_{2}} همیشه با a {\displaystyle a} برابر است.این مدل معادل با DFA است. اثبات آن شامل ساخت جدولی است که نتایج حاصل از پیمایش معکوس با شرایط خاص را برای هر وضعیت داده شده فهرست می کند. در آغاز محاسبه، پیمایش معکوس برابر با تلاش برای گذشتن از نشانگر پایان است.
wiki: ماشین خواندنی تورینگ