تورینگ کامل
در تئوری محاسباتی، سیستمی از قوانین تغییر داده‌ها (نظیر مجموعه دستورالعمل‌های کامپیوتر، زبان برنامه‌نویسی یا یک ماشین خودکار سلولی) درصورتی تورینگ کامل یا ازنظرمحاسباتی جامع نامیده می‌شود که بتوان برای شبیه‌سازی ماشین تورینگ تک نواری استفاده کرد. نمونه کلاسیکی، حساب لاندا است.
تئوری محاسباتی شامل مفاهیم مربوط به تناظر تورینگ است. دو کامپیوتر P,Q، درصورتی تناظر تورینگ نامیده می‌شوند که P بتواند Q را شبیه‌سازی نماید و Q بتواند P را شبیه‌سازی کند؛ بنابراین، یک سیستم کامل تورینگ، سیستمی می‌باشد که بتواند یک دستگاه تورینگ را شبیه‌سازی نماید و در تز چرچ-تورینگ، که هر کامپیوتر دنیای واقعی را بتوان با ماشین تورینگ شبیه‌سازی نمود، تناظر تورینگ برای یک دستگاه تورینگ می‌باشد.
در استفاده و کاربرد محاوره‌ای، اصطلاح " تورینگ کامل " یا " تناظر تورینگ " بدین معنا استفاده می‌شود که هر کامپیوتر با هدف عمومی دنیای واقعی یا زبان کامپیوتری بتواند به‌طور تقریبی هر کامپیوتر هدف عمومی دنیای واقعی یا زبان عمومی دیگر را شبیه‌سازی نماید. دلیل این که تقریبی است این است که در محدوده حافظه، آن‌ها تنها دستگاه‌های خودکار جامع و کامل خطی می‌باشند که به عنوان دستگاهی با یک مجموعه دستورالعمل‌های تورینگ کامل، حافظه نامحدود و یک طول عمر نامحدود تعیین می‌شود.
برای نشان دادن اینکه چه چیزی تورینگ کامل است، کافی است نشان دهیم که می‌تواند برای شبیه‌سازی سیستم تورینگ کامل استفاده شود. مثلاً، یک زبان ضروری و لازم، درصورتی تورینگ کامل می‌باشد که شاخه‌ها و انشعاب‌های مشروط و توانایی برای تغییر مکان‌های اختیاری حافظه دارد (یعنی توانایی برای حفظ شماره اختیاری متغیرها). چون این مسئله همیشه مورد نظر است، اکثراً هیچ‌کدام از زبان‌های ضروری و لازم، تورینگ کامل نمی‌باشند (اگر ما از هر محدودیتی از حافظه متناهی صرفنظر کنیم).
تعریف‌های رسمی
در تئوری محاسباتی، اصطلاحات و شرایط مربوطه برای توصیف قدرت محاسباتی یک سیستم محاسباتی (نظیر دستگاه تجرید یا زبان برنامه‌نویسی) استفاده می‌شوند.
کامل بودن تورینگ
یک سیستم محاسباتی که می‌تواند هر تابع قابل محاسبه با تورینگ را محاسبه نماید، تورینگ کامل نامیده می‌شود. چنین سیستمی، سیستمی می‌باشد که می‌تواند دستگاه جامع و کامل تورینگ را شبیه‌سازی نماید.
هم‌ارزی تورینگ
یک سیستم تورینگ کامل، درصورتی هم ارز تورینگ نامیده می‌شود که هر تابعی را که می‌تواند محاسبه نماید، قابل محاسبه با تورینگ باشد؛ یعنی، به‌طور دقیق کلاس مشابهی از توابع را به صورت انجام شده با دستگاه‌ها تورینگ محاسبه نماید. یک سیستم تناظر و هم‌ارزی تورینگ، سیستمی می‌باشد که می‌تواند یک دستگاه تورینگ کامل را شبیه‌سازی نماید و با ان شبیه‌سازی شود. (تمام سیستم‌های شناخته شده با تورینگ کامل، تناظر و هم ارز تورینگ می‌باشند که پشتیبانی از تز چرچ-تورینگ دارند)
جامعیت (محاسباتی)
یک سیستم، با توجه به کلاسی از سیستم‌ها درصورتی، جامع نامیده می‌شود که می‌تواند هر تابع قابل محاسبه با سیستم‌های موجود در ان کلاس را محاسبه نماید (یا می‌تواند هریک از ان سیستم‌ها را شبیه‌سازی نماید). معمولاً، اصطلاح جامعیت، با توجه به کلاس تورینگ کامل سیستم‌ها استفاده می‌شود. اصطلاح " جامعیت ضعیف " برای تمایز سیستمی استفاده می‌شود که جامعیت ان تنها با اصلاح تعریف استاندارد دستگاه تورینگ انجام می‌شود تا جریان‌های ورودی را با ۱ ثانیه دربرگیرد.
تاریخچه
تورینگ کامل درجایی مهم است که هر طراحی دنیای واقعی برای یک دستگاه محاسباتی را بتوان با یک دستگاه تورینگ کامل شبیه‌سازی نمود. تز چرچ-تورینگ بیان می‌کند که این مسئله، قانون ریاضی می‌باشد – که دستگاه تورینگ کامل می‌تواند هر محاسبه‌ای را انجام دهد که هر کامپیوتر قابل برنامه‌ریزی دیگر می‌تواند انجام دهد.
این مسئله، هیچ چیزی دربارهٔ تلاش‌های موردنیاز برای برنامه‌نویسی یا زمانی که برای انجام محاسبات، دستگاه صرف می‌کند یا هر توانایی که ممکن است دستگاهه داشته باشد که با انجام محاسباتی نمی‌تواند، انجام دهد، نمی‌گوید.
موتور تحلیل چارلز ببیج درصورتی اولین دستگاه تورینگ کامل می‌باشد که در زمان طراحی ان ساخته شده باشد. ببیج احساس کرد که این دستگاه می‌تواند محاسبات زیادی انجام دهد که شامل استدلال منطقی ابتدایی و اصلی می‌باشد ولی احساس نکرد که هیچ دستگاه دیگری بتواند بهتر انجام دهد.
از دهه ۱۸۳۰ تا دهه ۱۹۴۰، دستگاه‌های محاسباتی مکانیکی نظیر ضرب‌کننده و جمع‌کننده، ساخته می‌شوند و بهبود می‌یابند ولی آن‌ها نمی‌تواند بخش‌های شرطی را انجام دهند، بنابراین تورینگ کامل نمی‌باشند.
در اواخر قرن نوزدهم، لئوپولد کرونکر، تصورات محاسبات را تشکیل داد و توابع بازگشتی اصلی را تعریف کرد. این توابع را می‌توان با محاسبات تکراری محاسبه نمود ولی آن‌ها برای ایجاد و ساخت یک کامپیوتر جامع و کامل، کافی نمی‌باشند زیرا دستورالعمل‌هایی که آن‌ها را محاسبه می‌کنند، برای یک حلقه نامتناهی امکان‌پذیر نمی‌باشند.
در اوایل قرن بیستم، داوید هیلبرت، برنامه‌ای را برای بدیهی‌سازی تمام اصول ریاضی با اصول بدیهی دقیق و قوانین منطقی دقیق از قیاس و استناج ایجاد کرد که توانست با یک دستگاه انجام داد. مشخص شد که مجموعه کوچکی از قوانین استناج برای ایجاد پیامدهای هر مجموعه‌ای از اصول بدیهی، کافی می‌باشند.
این قوانین برای ایجاد هر قضیه با کورت گودل در سال ۱۹۳۰، اثبات شده‌است. قضیه تکامل گودل در سال ۱۹۳۰ شامل تعریفی از یک کامپیوتر جامع و کامل می‌باشد زیرا قوانین منطقی در برخی از اصول بدیهی ریاضی، به عنوان یک قضیه، نتیجه هر محاسبه‌ای ثابت می‌شود.
تصور واقعی از محاسبات، بعد از آغاز قضیه عدم تکامل گودل تفکیک شد. این قضیه نشان داد که سیستم‌های اصول بدیهی در زمان استدلال دربارهٔ محاسباتی، محدود می‌شوند که قضایای آن‌ها را استناج می‌کنند.
چرچ و تورینگ به‌طور مستقل نشان دادند که مسئله توقف هیلبرت، غیرقابل حل بود بنابراین هسته محاسباتی قضیه عدم تکامل را مشخص می‌نماید. این کار همراه با کار گودل دربارهٔ توابع بازگشتی، بیان کرد که مجموعه‌هایی از دستورالعمل‌های ساده وجود دارند که وقتی باهم قرار می‌گیرند، می‌توانند هر محاسبه‌ای را تولید کنند. کار گودل نشان داد که تصور محاسبات، اساساً منحصربه‌فرد می‌باشد.
جان فون نویمان با این نتایج برای طراحی دستگاه‌های محاسباتی جامع نتیجه‌گیری کرد. اولین زبان برنامه‌نویسی رسمی دهه ۱۹۳۰ نشان دادند که چنین کامپیوتری، مفید است. اولین پیاده‌سازی واقعی یک دستگاه تورینگ کامل در سال ۱۹۴۱ آشکار شد: برنامه کنترل شده Z3 مربوط به کنراد تسوزه، ولین اولین دستگاه طراحی شده برای تورینگ کامل و مناسب برای جامعیت، ۱۹۴۶ ENIAC می‌باشد. این دستگاه می‌تواند محدوده زیادی از مشکلات مناسب و مؤثر را در دهه ۱۹۴۰ حل نماید که مربوط به طراحی بمب اتمی است.
تئوری قابلیت محاسبه
اولین نتیجه تئوری قابلیت محاسبه این است که برای پیش‌بینی اینکه یک برنامه تورینگ کامل چه چیزی را در بلندمدت به‌طور اختیاری انجام می‌دهد، غیرممکن است. مثلاً، تعیین ان برای هر جفت برنامه – ورودی، غیرممکن است که ایا برنامه‌ای که بر روی ورودی‌ها عمل می‌کند، به‌طور موقتی متوقف شده‌است یا برای همیشه ادامه دارد.
تعیین این مسئله، غیرممکن است که آیا برنامه «درست» را برمی‌گرداند یا «اشتباه» را. برای هر مشخصه‌ای از خروجی‌های احتمالی و مشروط برنامه، تعیین اینکه این مشخصه صادق است یا نه، غیرممکن می‌باشد. این مسئله می‌تواند باعث مشکلاتی در عمل در زمان آنالیز و تحلیل برنامه‌های کامپیوتری واقعی شود. یک روش برای اجتناب از این مسئله، باعث برنامه‌هایی برای توقف اجرا بعد از دوره زمانی ثابت یا محدود کردن قدرت دستورالعمل‌های کنترل جریان می‌باشد. چنین سیستم‌هایی، با طراحی، تورینگ کامل نمی‌باشند. قضیه دیگر نشان می‌دهد که مشکلات قابل حلی با زبان‌های تورینگ کامل وجود دارند که نمی‌توان با هر زبانی با تنها قابلیت حلقه زنی محدود حل نمود (یعنی هر زبانی که تضمین می‌کند که هر برنامه‌ای برای یک لحظه مکث می‌کند).
با تعیین زبان مکث ار محدود، تابع قابل محاسبه‌ای که با استدلال محاوره‌ای کانتور در تمام توابع قابل محاسبه در ان زبان ایجاد می‌شود، در ان زبان قابل محاسبه نمی‌باشد.
اوراکل‌های تورینگ
کامپیوتری با دستیابی به نوار نامتناهی به داده‌ها، قدرتمندتر از یک دستگاه تورینگ می‌باشد زیرا این نوار می‌تواند در اصل شامل راه حلی برای مشکلات مکث کردن یا هر مشکلا غیرقابل تصمیم‌گیری دیگری باشد. نوار نامتناهی داده‌ها، یک اوراکل تورینگ می‌باشد. حتی یک اوراکل تورینگ با داده‌های تصادفی، قابل محاسبه نمی‌باشد زیرا تنها محاسبات زیادی وجود دارند ولی اوراکل‌های زیادی وجود دارند. دستگاهی که به استثناء دستیابی به برخی از اوراکل‌های تورینگ، جامع است، جامع ضعیف نامیده می‌شود.
فیزیک دیجیتالی
تمام قوانین شناخته شده از فیزیک، پیامدهایی دارند که با مجموعه‌ای از تقریب‌ها در یک کامپیوتر دیجیتالی، قابل محاسبه می‌باشند. فرضیه‌ای به نام فیزیک دیجیتالی بیان می‌کند که این مسئله، تصادفی نیست که بدین علت است که خود جامعیت در دستگاه تورینگ جامع، قابل محاسبه می‌باشد. این مسئله بیان می‌کند که هیچ کامپیوتر قدرتمندتر از دستگاه تورینگ جامع را می‌توان به‌طور فیزیکی ساخت.
نمونه‌ها
سیستم‌های محاسباتی (الجبرا، حساب) که به عنوان سیستم‌های تورینگ کامل موردبحث قرار می‌گیرند، سیستم‌های موردنظر برای مطالعه علوم کامپیوتری تئوریکی می‌باشند. آن‌ها خیلی ساده هستند بنابراین درک محدودیت‌های محاسباتی، اسانتراست. دراینجا برخی از آن‌ها موجود می‌باشند:
- نظریه اتوماتا
- ماشین محاسبه تورینگ
- حساب لاندا
- گرامر رسمی (مولدهای زبان)
- زبان رسمی (شناسنده‌های زبان)
- سیستم بازنویسی
- دستگاه‌های بعدازتورینگ
اکثر زبان‌های برنامه‌نویسی، مرسوم و غیرمرسوم، تورینگ کامل می‌باشند. این زبان‌ها عبارتند از:
- زبان‌های چندمنظوره در کاربردهای گسترده.
- زبان‌های برنامه‌نویسی رویه‌ای نظیر پاسکال
- زبان‌های شیء گرا نظیر جاوا، Smalltalk.
- زبان‌های چندنمونه‌ای نظیر Ada، C++، Common Lisp, Object Pascal.
- اکثر زبان‌هایی که از نمونه‌های کم کاربردتر استفاده می‌کنند.
- زبان‌های تابعی نظیر Lisp، Haskell.
- زبان‌های برنامه‌نویسی منطقی نظیر Prolog.
- زبان‌های تشریحی نظیر XSLT
- زبان‌های برنامه‌نویسی رمزی، شکلی از خلاقیت ریاضی که دران برنامه‌نویس دربارهٔ نحوه انجام ساختارهای برنامه‌نویسی پایه‌ای در یک زبان مشکل ولی هم ارز با تورینگ کار می‌کند.
تورنیگ کامل، گزاره‌ای از توانایی می‌باشد به جای تجویزی از ویژگی‌های خاص زبان استفاده شده برای پیاده‌سازی ان توانایی. ویژگی‌های استفاده شده برای انجام تورینگ کامل می‌توانند کاملاً متفاوت باشند. سیستم‌های فرترن از ساختارهای حلقه‌ای حتی گزاره‌های goto برای انجام تکرار استفاده می‌کنند؛ Haskell ,Prolog، که فاقد حله می‌باشند از بازگشت استفاده می‌کنند.
تورینگ کامل در SQL، از طریق ویژگی‌های استاندارد پیشرفته پیاده‌سازی می‌شود، که دلیلی برای قدرتمندبودن زبان‌های غیراز تورینگ، نادر است. هرچقدر این زبان، قدرتمندتر باشد، وظایفی که برای ان انجام می‌شود، پیچیده‌تر می‌باشد و فقدان کامل بودن ان به صورت یک مانع و اشکال، زودتر می‌باشد و بسط والحاق ان را تشویق می‌کند تا اینکه تورینگ کامل شود.
حساب لاندا، تورینگ کامل می‌باشد ولی حساب‌های لاندای زیادی شامل سیستم F تورینگ کامل نمی‌باشند. ارزش سیستم‌های معلوم شده مبتنی بر توانایی آن‌ها برای نمایش معمولترین برنامه‌های کامپیوتری در حین شناسایی خطاهای بیشتر می‌باشد.
قانون ۱۱۰ و بازی زندگی Conway، تورینگ کامل می‌باشند.
زبان‌های غیر تورینگ کامل
زبان‌های محاسباتی زیادی وجود دارند که تورینگ کامل نمی‌باشند. یک چنین نمونه‌ای، مجموعه‌ای از زبان‌های قانونی می‌باشد که با دستگاه‌های خودکار متناهی تولید می‌شوند.
یک الحاق قدرتمندتر ولی غیرتورینگ کامل از دستگاه‌های خودکار متناهی، گروهی از ماشین‌های خودکار و گرامرهای بدون متن می‌باشد که برای ایجاد درخت‌های پویشی در مرحله ابتدایی برنامه استفاده می‌شوند. نمونه‌های بیشتر شامل برخی از نسخه‌های ابتدایی زبان‌های سایه زنی پیکسل جاسازی شده در Direct3D و OpenGL می‌باشند.
در زبان‌های برنامه‌نویسی تابعی کلی، تمام توابع، کلی می‌باشند و باید پایان یابند نظیر Charity, Epigram. Charity، از یک سیستم نوعی و ساختارهای کنترلی مبتنی بر تئوری گروهی استفاده می‌کند درحالیکه Epigram از نوع‌های وابسته استفاده می‌کند. زبان LOOP طراحی می‌شود بنابراین تنها توابعی را محاسبه نماید که بازگشتی ضروری می‌باشند. تمام اینها، زیرمجموعه‌های مناسب از توابع قابل محاسبه را محاسبه می‌کنند زیرا مجموعه کاملی از توابع قابل محاسبه، شمارش پذیر نمی‌باشند.
زبان داده‌ها
تصوری از تورینگ کامل به زبان‌هایی نظیر XML، JSON, YAML, S اعمال نمی‌شود زیرا آن‌ها برای نمایش داده‌های ساختاریافته‌استفاده می‌شوند ولی محاسبات را توصیف نمی‌کنند. اینها به عنوان زبان نشانه‌گذاری یا زبان‌های محفظه‌ای یا زبان‌های توصیف داده‌ها می‌باشند.
جستارهای وابسته
- تز چرچ-تورینگ
- نظریه رایانش‌پذیری
- نظریه الگوریتمی اطلاعات
- وراثت چامسکی
- کتاب یک نوع جدید علم از استیون ولفرم
منابع
مشارکت‌کنندگان ویکی‌پدیا. «Turing completeness». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۴ ژوئن ۲۰۱۳.