در علوم رایانه ای، ماشین محاسبه تورینگ (به انگلیسی: Universal Turing machine) (مخفف انگلیسی: UTM) نوعی ماشین محاسباتی است که می تواند براساس یک داده تصادفی یک محاسبه تورینگ تصادفی را شبیه سازی نماید. این ماشین محاسباتی اساساً با خواندن توضیح ماشین و نیز داده مربوطه از روی نوار موجود در خود ماشین این کار را انجام می دهد. آلن تورینگ این ماشین را بین سال های ۱۹۳۷–۱۹۳۶ معرفی نمود. این الگو از نظر بعضی (مانند مارتین دیویس) منشأ ساخت قطعه «ذخیره کننده دستورهای برنامه های کامپیوتری» می باشد که توسط جان فون نویمان در ابزار محاسباتی الکترونیکی بکار می رفت و اکنون در علم رایانه «ساختار فون نویمان» نام دارد. این ماشین همچنین ماشین محاسبه جامع، ماشین جامع (UM) و ماشین (U) نامیده می شود.
ماشین تورینگ
تز چرچ-تورینگ
با توجه به پیچیدگی برنامه های رایانه ای، ماشین محاسبه تورینگ چند نواری در مقایسه با ماشین هایی که آن ها را شبیه سازی می کند، فقط دارای عامل لگاریتمی است که عملکرد آن را آهسته تر می نماید.
یک ماشین محاسبه تورینگ یک متغیر محاسباتی خاص را با استفاده از رشته ای از داده ها از طریق الفبای (صفر و یک) آن محاسبه می کند. از این لحاظ، این ماشین مانند یک کامپیوتر با برنامه ثابت عمل می نماید؛ ولیکن، می توان جدول عملگرهای هر ماشین تورینگی را به صورت رشته ای از داده ها رمزگذاری نمود. بنابراین می توان ماشین محاسبه تورینگی ساخت که بر روی نوار ذخیره اطلاعات آن رشته ای از داده ها برای توصیف جدول عملگرها به همراه رشته ای برای توصیف نوار ورودی وجود داشته باشد و نواری را که ماشین تورینگ رمزگذاری کرده است، محاسبه نماید. تورینگ در مقاله سال ۱۹۳۶ خود این ساختار را با جزئیات کامل توصیف نمود: "این امکان وجود دارد که ماشینی را اختراع نمود تا بتواند هر تابع قابل محاسبه ای را محاسبه نماید. اگر این ماشین (U) دارای نواری باشد که در ابتدای آن توضیحات استاندارد (S.D) از جدول عملگرهای بعضی از ماشینهای محاسبه M نوشته شده باشد بنابراین U یعنی ماشین می تواند همان تابع را به عنوان M محاسبه نماید.
"دیویس" استدلال قانع کننده ای ارائه می دهد که تعریف تورینگ از آنچه که اکنون "کامپیوتر ذخیره دستورهای برنامه نویسی"، نامیده می شود و نیز قرار دادن "جدول عملگرهاً یعنی دستورهای موجود در ماشین را که در همان حافظه ای ذخیره می شوند که داده ها در آن وجود دارند، تعریف اولیه جان وون نیومن از نماد گسسته (در مقابل نماد متشابه) را تحت تأثیر خود قرار داد، یعنی EDVAC. دیویس در این زمینه در مجله "تایم" بیان می کند که "هر فردی که بر روی کیبورد ضربه وارد می کند به نوعی در حال تجسم بخشیدن به ماشین محاسبه تورینگ است" و اینکه " نظریه آلن تورینگ اساس نظریه جان وون نیومن بوده است."دیویس بیان می کند که موتور محاسبه خودکار تورینگ (ACE) مفاهیم کوچکترین دستورهای برنامه های کامپیوتری و پردازنده های RISC را پیش بینی کرده بود. "ناچ" نیز از موتور محاسبه خودکار تورینگ به عنوان طراحی "سخت افزاری برای تسهیل عملگرهای توابع به هم پیوسته" یاد می کند، دیویس همچنین از موتور محاسبه خودکار تورینگ به عنوان سخت افزار "حافظه کوتاه مدت" نام می برد.از آنجا که ماشین محاسبه تیورینگ منشأ ساخت کامپیوترها بوده است، بنابراین ماشین محاسبه تورینگ را می توان نسل کامپیوترهای اولیه دانست. به گفته دیویس یکی از اولین برنامه های کامپیوتری توسط یک برنامه نویس برجسته جوان برای EDVAS ارائه شد. اولین برنامه جدی "وون نیومن" فقط داده های ساده ای بودند که به طور مؤثری نوشته شده بودند. "ناچ" بیان می کند که اجرای دستورهای تابع به جای ثبت در برنامه های خاص منتسب به "وون نیومان" و "گولد استین" در خود برنامه جاسازی شده است. "ناچ" همچنین بیان می دارد که "اولین برنامه های تفسیری شاید در ماشین محاسبه تورینگ آورده شده بودند." "جان ماکلی" در سخنرانی خود که در سال ۱۹۴۶ در دانشگاه "مور" برگزار نمود به برنامه های تفسیری اشاره کرد. تورینگ همچنین در توسعه و نوشتن و هدایت برنامه های تفسیری برای کامپیوتر آزمایشی ACE شرکت داشت. (ناچ) دیویس به اختصار به سیستم های نرم افزاری پشتیبان و کامپایلرها به عنوان خروجی و نتیجه مفهوم "برنامه به عنوان داده" اشاره می کند؛ ولیکن تاحدی شاید با این ارزیابی مشکلاتی را به وجود میاورد. در آن زمان (اواسط دهه ۱۹۴۰ تا اواسط دهه ۱۹۵۰) گروه نسبتاً کوچکی از محققان به طور محرمانه در ساخت "کامپیوترهای دیجیتال" جدید با یکدیگر همکاری داشتند. "هائو وانگ" که در آن زمان محقق جوانی بود مشاهدات خود را بدین گونه بیان نمود:تئوری تورینگ در مورد توابع قابل محاسبه از زمان خود بسیار جلوتر بوده است، اما تأثیر چندانی بر ساخت واقعی کامپیوترهای دیجیتال نداشته است. این دو جنبه تئوری و عملی بیشتر به طور مستقل از یکدیگر گسترش یافته اند. دلیل اصلی این امر بدون شک آن است که منطق گرایان اساساً به مسائلی علاقه مند هستند که با نظریات مورد علاقه ریاضی دانان و مهندسین برق تفاوت دارند؛ ولیکن جای تعجب نیست که اغلب، مفاهیم مشابه با اصطلاحات و روش های متفاوتی بیان می شوند."وانگ" امیدوار بود که مقاله وی موجب پیوند بین این دو روش و دیدگاه شود. درواقع، "مینسکی" تأیید می کند که "اولین فرمول نظریه ماشینهای محاسبه تورینگ در مدل های مشابه کامپیوتر در نظریه "وانگ" ظاهر شده است. مینسکی ماشین محاسبه تورینگ را به نوعی معادل ماشین های ابتدایی ذخیره اطلاعات می داند.با توجه به تبدیل کامپیوترها به مدل های ساده معادل تورینگ (و برعکس)، انتخاب "وانگ" از طرف "مینسکی" به عنوان اولین فردی که ماشین های محاسبه را قاعده مند ساخت، موجب به وجود آمدن مباحثی شد. درحالیکه "شِفِردسون" و "استورگیس" به مقاله "مینسکی" در سال ۱۹۶۱ و مقاله "وانگ" در سال ۱۹۵۷ اشاره کرده بودند، خلاصه ای از جزئیات بعضی آثار ریاضی دانان اروپایی از جمله "کافِنست"، "اِرشوو" و "پیتر" را نیز مطرح نمودند. نام ریاضی دانانی مانند "هِرمِس" و "کافِنست" در کتاب شناسی "شِفِردسون" و "استورگیس" و "اِلگوت رابینسون" آورده شده است. دو نام مهم دیگر نیز در این میان عبارتند از محققان کانادایی "مِلزاک" و "لامبِک".
ماشین تورینگ
تز چرچ-تورینگ
با توجه به پیچیدگی برنامه های رایانه ای، ماشین محاسبه تورینگ چند نواری در مقایسه با ماشین هایی که آن ها را شبیه سازی می کند، فقط دارای عامل لگاریتمی است که عملکرد آن را آهسته تر می نماید.
یک ماشین محاسبه تورینگ یک متغیر محاسباتی خاص را با استفاده از رشته ای از داده ها از طریق الفبای (صفر و یک) آن محاسبه می کند. از این لحاظ، این ماشین مانند یک کامپیوتر با برنامه ثابت عمل می نماید؛ ولیکن، می توان جدول عملگرهای هر ماشین تورینگی را به صورت رشته ای از داده ها رمزگذاری نمود. بنابراین می توان ماشین محاسبه تورینگی ساخت که بر روی نوار ذخیره اطلاعات آن رشته ای از داده ها برای توصیف جدول عملگرها به همراه رشته ای برای توصیف نوار ورودی وجود داشته باشد و نواری را که ماشین تورینگ رمزگذاری کرده است، محاسبه نماید. تورینگ در مقاله سال ۱۹۳۶ خود این ساختار را با جزئیات کامل توصیف نمود: "این امکان وجود دارد که ماشینی را اختراع نمود تا بتواند هر تابع قابل محاسبه ای را محاسبه نماید. اگر این ماشین (U) دارای نواری باشد که در ابتدای آن توضیحات استاندارد (S.D) از جدول عملگرهای بعضی از ماشینهای محاسبه M نوشته شده باشد بنابراین U یعنی ماشین می تواند همان تابع را به عنوان M محاسبه نماید.
"دیویس" استدلال قانع کننده ای ارائه می دهد که تعریف تورینگ از آنچه که اکنون "کامپیوتر ذخیره دستورهای برنامه نویسی"، نامیده می شود و نیز قرار دادن "جدول عملگرهاً یعنی دستورهای موجود در ماشین را که در همان حافظه ای ذخیره می شوند که داده ها در آن وجود دارند، تعریف اولیه جان وون نیومن از نماد گسسته (در مقابل نماد متشابه) را تحت تأثیر خود قرار داد، یعنی EDVAC. دیویس در این زمینه در مجله "تایم" بیان می کند که "هر فردی که بر روی کیبورد ضربه وارد می کند به نوعی در حال تجسم بخشیدن به ماشین محاسبه تورینگ است" و اینکه " نظریه آلن تورینگ اساس نظریه جان وون نیومن بوده است."دیویس بیان می کند که موتور محاسبه خودکار تورینگ (ACE) مفاهیم کوچکترین دستورهای برنامه های کامپیوتری و پردازنده های RISC را پیش بینی کرده بود. "ناچ" نیز از موتور محاسبه خودکار تورینگ به عنوان طراحی "سخت افزاری برای تسهیل عملگرهای توابع به هم پیوسته" یاد می کند، دیویس همچنین از موتور محاسبه خودکار تورینگ به عنوان سخت افزار "حافظه کوتاه مدت" نام می برد.از آنجا که ماشین محاسبه تیورینگ منشأ ساخت کامپیوترها بوده است، بنابراین ماشین محاسبه تورینگ را می توان نسل کامپیوترهای اولیه دانست. به گفته دیویس یکی از اولین برنامه های کامپیوتری توسط یک برنامه نویس برجسته جوان برای EDVAS ارائه شد. اولین برنامه جدی "وون نیومن" فقط داده های ساده ای بودند که به طور مؤثری نوشته شده بودند. "ناچ" بیان می کند که اجرای دستورهای تابع به جای ثبت در برنامه های خاص منتسب به "وون نیومان" و "گولد استین" در خود برنامه جاسازی شده است. "ناچ" همچنین بیان می دارد که "اولین برنامه های تفسیری شاید در ماشین محاسبه تورینگ آورده شده بودند." "جان ماکلی" در سخنرانی خود که در سال ۱۹۴۶ در دانشگاه "مور" برگزار نمود به برنامه های تفسیری اشاره کرد. تورینگ همچنین در توسعه و نوشتن و هدایت برنامه های تفسیری برای کامپیوتر آزمایشی ACE شرکت داشت. (ناچ) دیویس به اختصار به سیستم های نرم افزاری پشتیبان و کامپایلرها به عنوان خروجی و نتیجه مفهوم "برنامه به عنوان داده" اشاره می کند؛ ولیکن تاحدی شاید با این ارزیابی مشکلاتی را به وجود میاورد. در آن زمان (اواسط دهه ۱۹۴۰ تا اواسط دهه ۱۹۵۰) گروه نسبتاً کوچکی از محققان به طور محرمانه در ساخت "کامپیوترهای دیجیتال" جدید با یکدیگر همکاری داشتند. "هائو وانگ" که در آن زمان محقق جوانی بود مشاهدات خود را بدین گونه بیان نمود:تئوری تورینگ در مورد توابع قابل محاسبه از زمان خود بسیار جلوتر بوده است، اما تأثیر چندانی بر ساخت واقعی کامپیوترهای دیجیتال نداشته است. این دو جنبه تئوری و عملی بیشتر به طور مستقل از یکدیگر گسترش یافته اند. دلیل اصلی این امر بدون شک آن است که منطق گرایان اساساً به مسائلی علاقه مند هستند که با نظریات مورد علاقه ریاضی دانان و مهندسین برق تفاوت دارند؛ ولیکن جای تعجب نیست که اغلب، مفاهیم مشابه با اصطلاحات و روش های متفاوتی بیان می شوند."وانگ" امیدوار بود که مقاله وی موجب پیوند بین این دو روش و دیدگاه شود. درواقع، "مینسکی" تأیید می کند که "اولین فرمول نظریه ماشینهای محاسبه تورینگ در مدل های مشابه کامپیوتر در نظریه "وانگ" ظاهر شده است. مینسکی ماشین محاسبه تورینگ را به نوعی معادل ماشین های ابتدایی ذخیره اطلاعات می داند.با توجه به تبدیل کامپیوترها به مدل های ساده معادل تورینگ (و برعکس)، انتخاب "وانگ" از طرف "مینسکی" به عنوان اولین فردی که ماشین های محاسبه را قاعده مند ساخت، موجب به وجود آمدن مباحثی شد. درحالیکه "شِفِردسون" و "استورگیس" به مقاله "مینسکی" در سال ۱۹۶۱ و مقاله "وانگ" در سال ۱۹۵۷ اشاره کرده بودند، خلاصه ای از جزئیات بعضی آثار ریاضی دانان اروپایی از جمله "کافِنست"، "اِرشوو" و "پیتر" را نیز مطرح نمودند. نام ریاضی دانانی مانند "هِرمِس" و "کافِنست" در کتاب شناسی "شِفِردسون" و "استورگیس" و "اِلگوت رابینسون" آورده شده است. دو نام مهم دیگر نیز در این میان عبارتند از محققان کانادایی "مِلزاک" و "لامبِک".
wiki: ماشین محاسبه تورینگ