ماشین تورینگ ( به انگلیسی: Turing machine ) یک دستگاه فرضی است که روی نشان های یک قطعه نوار ، بر اساس جدول قوانین دست کاری انجام می دهد. با وجود اینکه مکانیزم ماشین تورینگ مقدماتی است، مفهومش برای پوشش عملکردهای بسیار پیچیده کافی و گسترده است. ماشین تورینگ می تواند برای شبیه سازی هر الگوریتم کامپیوتری و توضیح نحوه عملکرد یک واحد پردازشگر مرکزی به کار آید. حافظه این ماشین ساختاری بسیار ساده دارد. یعنی می تواند به صورت یک آرایه یک بعدی از عناصر ( سلولها ) باشد که هر یک می توانند حافظ تنها یک نماد باشند. این آرایه از هر دو طرف باز و نامحدود است ( حافظه بینهایت ) و اطلاعات آن می توانند به هر ترتیبی فراخوانی شوند.
معرفی ماشین تورینگ توسط دانشمند انگلیسی آلن تورینگ در سال ۱۹۳۶ میلادی، گام دیگری را در مسیر ایجاد و پیدایش ماشین های محاسباتی حالات متناهی به نمایش می گذارد. رابین گندی یکی از دانشجویان آلن تورینگ و دوست صمیمی تمام عمرش، ریشه های نظریه ماشین محاسباتی بابیج ( ۱۸۳۴ ) را کاوش کرد و در حقیقت نظریه بابیج را دوباره ارائه کرد:
آنالیز گندی در مورد ماشین تحلیلی بابیج پنج عملیات زیر را توضیح می دهد:
۱ - عملگرهای ریاضی + و - و *و%
۲ - هر ترتیبی از عملگرها قابل قبول است.
۳ - تکرار عملگر
۴ - تکرار شرطی
۵ - انتقال شرطی
ماشین تورینگ عبارت است از یک پنج - تاپل ( پنج تایی ) به صورت M = ( Q , Σ , Γ , δ , q 0 ) ، که در اینجا:
• M {\displaystyle M\!} برای نمایش مفهوم ماشین انتخاب شده است.
• Q {\displaystyle Q\!} مجموعه ای است متناهی، از حالات داخلی. [ ۱]
• Γ {\displaystyle \Gamma \!} مجموعه ای متناهی موسوم به الفبای نوار[ ۲] و حاوی نمادی مخصوص B {\displaystyle B\!} برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
• Σ {\displaystyle \Sigma \!} زیرمجموعه ای است از Γ − { B } {\displaystyle \Gamma - \{B\}\!} و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی توانند به عنوان ورودی استفاده شوند.
• δ {\displaystyle \delta \!} عبارت است از یک تابع جزئی، [ ۳] موسوم به تابع انتقال[ ۴] از دامنهٔ Q × Γ {\displaystyle Q\times \Gamma \!} به برد Q × Γ × { L , R } {\displaystyle Q\times \Gamma \times \{L, R\}\!} .
• q 0 {\displaystyle q_{0}\!} حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را در آن آغاز می کنیم.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمعرفی ماشین تورینگ توسط دانشمند انگلیسی آلن تورینگ در سال ۱۹۳۶ میلادی، گام دیگری را در مسیر ایجاد و پیدایش ماشین های محاسباتی حالات متناهی به نمایش می گذارد. رابین گندی یکی از دانشجویان آلن تورینگ و دوست صمیمی تمام عمرش، ریشه های نظریه ماشین محاسباتی بابیج ( ۱۸۳۴ ) را کاوش کرد و در حقیقت نظریه بابیج را دوباره ارائه کرد:
آنالیز گندی در مورد ماشین تحلیلی بابیج پنج عملیات زیر را توضیح می دهد:
۱ - عملگرهای ریاضی + و - و *و%
۲ - هر ترتیبی از عملگرها قابل قبول است.
۳ - تکرار عملگر
۴ - تکرار شرطی
۵ - انتقال شرطی
ماشین تورینگ عبارت است از یک پنج - تاپل ( پنج تایی ) به صورت M = ( Q , Σ , Γ , δ , q 0 ) ، که در اینجا:
• M {\displaystyle M\!} برای نمایش مفهوم ماشین انتخاب شده است.
• Q {\displaystyle Q\!} مجموعه ای است متناهی، از حالات داخلی. [ ۱]
• Γ {\displaystyle \Gamma \!} مجموعه ای متناهی موسوم به الفبای نوار[ ۲] و حاوی نمادی مخصوص B {\displaystyle B\!} برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
• Σ {\displaystyle \Sigma \!} زیرمجموعه ای است از Γ − { B } {\displaystyle \Gamma - \{B\}\!} و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی توانند به عنوان ورودی استفاده شوند.
• δ {\displaystyle \delta \!} عبارت است از یک تابع جزئی، [ ۳] موسوم به تابع انتقال[ ۴] از دامنهٔ Q × Γ {\displaystyle Q\times \Gamma \!} به برد Q × Γ × { L , R } {\displaystyle Q\times \Gamma \times \{L, R\}\!} .
• q 0 {\displaystyle q_{0}\!} حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را در آن آغاز می کنیم.
wiki: ماشین تورینگ