ماشین تورینگ چندمسیره (به انگلیسی: Multi-track Turing machine) یا چندمجرایی نوع خاصی از ماشین تورینگ چندنواره است.در یک ماشین تورینگ استاندارد با n نوار ،n کلاهک به صورت مستقل در امتداد n مسیر حرکت می کنند.در یک ماشین تورینگ چند مجرایی با n مجرا یک کلاهک روی تمام مجراها عمل خواندن و نوشتن را به صورت هم زمان انجام می دهد.هر موقعیت در این ماشین تورینگ شامل n نماد از حروف الفبا می باشد. این ماشین تورینگ، معادل ماشین تورینگ استاندارد است و زبان های شمارا را، که به صورت بازگشتی تعریف شده اند، می پذیرد.
Q {\displaystyle Q} مجموعه متناهی از حالت ها است.
Σ {\displaystyle \Sigma } مجموعهٔ متناهی از نمادها است که الفبای پشته نام دارد.
Γ ∈ Q {\displaystyle \Gamma \in Q}
q 0 ∈ Q {\displaystyle q_{0}\in Q} نشان دهنده حالت اولیه است.
F ⊆ Q {\displaystyle F\subseteq Q} مجموعه حالت های پایانی یا حالت های مورد پذیرش ماشین است.
δ ⊆ ( Q ∖ F × Σ ) × ( Q × Σ × d ) {\displaystyle \delta \subseteq \left(Q\backslash F\times \Sigma \right)\times \left(Q\times \Sigma \times d\right)} رابطه ای بین حالت های ماشین و نمادها است که انتقال نام دارد.
δ ( Q i , ) = ( Q j , , d ) {\displaystyle \delta \left(Q_{i},\right)=(Q_{j},,d)} که d ∈ { L , R } {\displaystyle d\in \{L,R\}} .
یک ماشین تورینگ چند مجرایی به صورت رسمی توسط یک ۶ تایی به صورت M = ⟨ Q , Σ , Γ , δ , q 0 , F ⟩ {\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle } تعریف می شود که در آن:
این اثبات معادل بودن ماشین تورینگ ۲مجرایی را با ماشین تورینگ استاندارد نشان می دهد و قابل تعمیم به ماشین تورینگ n مجرایی است.با در نظر گرفتن زبان شمارای L، ماشین استاندارد M را اینگونه تعریف می کنیم: M = ⟨ Q , Σ , Γ , δ , q 0 , F ⟩ {\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle } . این ماشین زبان L را می پذیرد.حال، 'M را یک ماشین تورینگ ۲-مجرایی فرض می کنیم. برای اثبات معادل بودن، باید ثابت شود M ⊆ {\displaystyle \subseteq } M و M' ⊆ {\displaystyle \subseteq } M.
اگر همهٔ مجراهای 'M، به جز اولین مجرای آن، حذف شوند، به وضوح دیده می شود که M' و M با هم معادل هستند.
Q {\displaystyle Q} مجموعه متناهی از حالت ها است.
Σ {\displaystyle \Sigma } مجموعهٔ متناهی از نمادها است که الفبای پشته نام دارد.
Γ ∈ Q {\displaystyle \Gamma \in Q}
q 0 ∈ Q {\displaystyle q_{0}\in Q} نشان دهنده حالت اولیه است.
F ⊆ Q {\displaystyle F\subseteq Q} مجموعه حالت های پایانی یا حالت های مورد پذیرش ماشین است.
δ ⊆ ( Q ∖ F × Σ ) × ( Q × Σ × d ) {\displaystyle \delta \subseteq \left(Q\backslash F\times \Sigma \right)\times \left(Q\times \Sigma \times d\right)} رابطه ای بین حالت های ماشین و نمادها است که انتقال نام دارد.
δ ( Q i , ) = ( Q j , , d ) {\displaystyle \delta \left(Q_{i},\right)=(Q_{j},,d)} که d ∈ { L , R } {\displaystyle d\in \{L,R\}} .
یک ماشین تورینگ چند مجرایی به صورت رسمی توسط یک ۶ تایی به صورت M = ⟨ Q , Σ , Γ , δ , q 0 , F ⟩ {\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle } تعریف می شود که در آن:
این اثبات معادل بودن ماشین تورینگ ۲مجرایی را با ماشین تورینگ استاندارد نشان می دهد و قابل تعمیم به ماشین تورینگ n مجرایی است.با در نظر گرفتن زبان شمارای L، ماشین استاندارد M را اینگونه تعریف می کنیم: M = ⟨ Q , Σ , Γ , δ , q 0 , F ⟩ {\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle } . این ماشین زبان L را می پذیرد.حال، 'M را یک ماشین تورینگ ۲-مجرایی فرض می کنیم. برای اثبات معادل بودن، باید ثابت شود M ⊆ {\displaystyle \subseteq } M و M' ⊆ {\displaystyle \subseteq } M.
اگر همهٔ مجراهای 'M، به جز اولین مجرای آن، حذف شوند، به وضوح دیده می شود که M' و M با هم معادل هستند.
wiki: ماشین تورینگ چندمسیره