کامل بودن تورینگ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در تئوری محاسباتی، سیستمی از قوانین تغییر داده‌ها (نظیر مجموعه دستورالعمل‌های کامپیوتر، زبان برنامه نویسی یا یک ماشین خودکار سلولی) درصورتی تورینگ کامل یا ازنظرمحاسباتی جامع نامیده می‌شود که بتوان برای شبیه سازی ماشین تورینگ تک نواری استفاده کرد. نمونه کلاسیکی، حساب لاندا است.
تئوری محاسباتی شامل مفاهیم مربوط به تناظر تورینگ است. دو کامپیوتر P،Q، درصورتی تناظر تورینگ نامیده می‌شوند که P بتواند Q را شبیه سازی نماید و Q بتواند P را شبیه سازی کند. بنابراین، یک سیستم کامل تورینگ، سیستمی می‌باشد که بتواند یک دستگاه تورینگ را شبیه سازی نماید و در تز چرچ-تورینگ، که هر کامپیوتر دنیای واقعی را بتوان با ماشین تورینگ شبیه سازی نمود، تناظر تورینگ برای یک دستگاه تورینگ می‌باشد.
در استفاده و کاربرد محاوره‌ای، اصطلاح " تورینگ کامل " یا " تناظر تورینگ " بدین معنا استفاده می‌شود که هر کامپیوتر با هدف عمومی دنیای واقعی و یا زبان کامپیوتری بتواند به طور تقریبی هر کامپیوتر هدف عمومی دنیای واقعی و یا زبان عمومی دیگر را شبیه سازی نماید. دلیل این که تقریبی است این است که در محدوده حافظه، انها تنها دستگاه‌های خودکار جامع و کامل خطی می‌باشند که به عنوان دستگاهی با یک مجموعه دستورالعمل‌های تورینگ کامل، حافظه نامحدود و یک طول عمر نامحدود تعیین می‌شود.
برای نشان دادن اینکه چه چیزی تورینگ کامل است، کافی است نشان دهیم که می‌تواند برای شبیه سازی سیستم تورینگ کامل استفاده شود. مثلاً، یک زبان ضروری و لازم، درصورتی تورینگ کامل می‌باشد که شاخه‌ها و انشعاب‌های مشروط و توانایی برای تغییر مکان‌های اختیاری حافظه دارد (یعنی توانایی برای حفظ شماره اختیاری متغیرها). چون این مساله همیشه مورد نظر است، اکثراً هیچکدام از زبان‌های ضروری و لازم، تورینگ کامل نمی‌باشند (اگر ما از هر محدودیتی از حافظه متناهی صرفنظر کنیم).

تعریف‌های رسمی[ویرایش]

در تئوری محاسباتی، اصطلاحات و شرایط مربوطه برای توصیف قدرت محاسباتی یک سیستم محاسباتی (نظیر دستگاه تجرید و یا زبان برنامه نویسی) استفاده می‌شوند.
کامل بودن تورینگ
یک سیستم محاسباتی که می‌تواند هر تابع قابل محاسبه با تورینگ را محاسبه نماید، تورینگ کامل نامیده می‌شود. چنین سیستمی، سیستمی می‌باشد که می‌تواند دستگاه جامع و کامل تورینگ را شبیه سازی نماید.
هم ارزی تورینگ
یک سیستم تورینگ کامل، درصورتی هم ارز تورینگ نامیده می‌شود که هر تابعی را که می‌تواند محاسبه نماید، قابل محاسبه با تورینگ باشد؛ یعنی، به طور دقیق کلاس مشابهی از توابع را به صورت انجام شده با دستگاه‌ها تورینگ محاسبه نماید. یک سیستم تناظر و هم ارزی تورینگ، سیستمی می‌باشد که می‌تواند یک دستگاه تورینگ کامل را شبیه سازی نماید و با ان شبیه سازی شود. (تمام سیستم‌های شناخته شده با تورینگ کامل، تناظر و هم ارز تورینگ می‌باشند که پشتیبانی از تز چرچ-تورینگ دارند.)
جامعیت (محاسباتی)
یک سیستم، باتوجه به کلاسی از سیستم‌ها درصورتی، جامع نامیده می‌شود که می‌تواند هر تابع قابل محاسبه با سیستم‌های موجود در ان کلاس را محاسبه نماید (یا می‌تواند هریک از ان سیستم‌ها را شبیه سازی نماید). معمولاً، اصطلاح جامعیت، با توجه به کلاس تورینگ کامل سیستم‌ها استفاده می‌شود. اصطلاح " جامعیت ضعیف " برای تمایز سیستمی استفاده می‌شود که جامعیت ان تنها با اصلاح تعریف استاندارد دستگاه تورینگ انجام می‌شود تا جریان‌های ورودی را با ۱ ثانیه دربرگیرد.

تاریخچه[ویرایش]

تورینگ کامل درجایی مهم است که هر طراحی دنیای واقعی برای یک دستگاه محاسباتی را بتوان با یک دستگاه تورینگ کامل شبیه سازی نمود. تز چرچ-تورینگ بیان می‌کند که این مساله، قانون ریاضی می‌باشد – که دستگاه تورینگ کامل می‌تواند هر محاسبه‌ای را انجام دهد که هر کامپیوتر قابل برنامه ریزی دیگر می‌تواند انجام دهد.
این مساله، هیچ چیزی درباره تلاش‌های موردنیاز برای برنامه نویسی یا زمانی که برای انجام محاسبات، دستگاه صرف می‌کند یا هر توانایی که ممکن است دستگاهه داشته باشد که با انجام محاسباتی نمی‌تواند، انجام دهد، نمی‌گوید.
موتور تحلیل چارلز ببیج درصورتی اولین دستگاه تورینگ کامل می‌باشد که در زمان طراحی ان ساخته شده باشد. ببیج احساس کرد که این دستگاه می‌تواند محاسبات زیادی انجام دهد که شامل استدلال منطقی ابتدایی و اصلی می‌باشد ولی احساس نکرد که هیچ دستگاه دیگری بتواند بهتر انجام دهد.
از دهه ۱۸۳۰ تا دهه ۱۹۴۰، دستگاه‌های محاسباتی مکانیکی نظیر ضرب کننده و جمع کننده، ساخته می‌شوند و بهبود می‌یابند ولی انها نمی‌تواند بخشهای شرطی را انجام دهند، بنابراین تورینگ کامل نمی‌باشند.
در اواخر قرن نوزدهم، لئوپولد کرونکر، تصورات محاسبات را تشکیل داد و توابع بازگشتی اصلی را تعریف کرد. این توابع را می‌توان با محاسبات تکراری محاسبه نمود ولی انها برای ایجاد و ساخت یک کامپیوتر جامع و کامل، کافی نمی‌باشند زیرا دستورالعمل‌هایی که انها را محاسبه می‌کنند، برای یک حلقه نامتناهی امکان پذیر نمی‌باشند.
در اوایل قرن بیستم، داوید هیلبرت، برنامه‌ای را برای بدیهی سازی تمام اصول ریاضی با اصول بدیهی دقیق و قوانین منطقی دقیق از قیاس و استناج ایجاد کرد که توانست با یک دستگاه انجام داد. مشخص شد که مجموعه کوچکی از قوانین استناج برای ایجاد پیامدهای هر مجموعه‌ای از اصول بدیهی، کافی می‌باشند.
این قوانین برای ایجاد هر قضیه با کورت گودل در سال ۱۹۳۰، اثبات شده است. قضیه تکامل گودل در سال ۱۹۳۰ شامل تعریفی از یک کامپیوتر جامع و کامل می‌باشد زیرا قوانین منطقی در برخی از اصول بدیهی ریاضی، به عنوان یک قضیه، نتیجه هر محاسبه‌ای ثابت می‌شود. تصور واقعی از محاسبات، بعداز اغاز قضیه عدم تکامل گودل تفکیک شد. این قضیه نشان داد که سیستم‌های اصول بدیهی در زمان استدلال درباره محاسباتی، محدود می‌شوند که قضایای انها را استناج می‌کنند.
چرچ و تورینگ به طور مستقل نشان دادند که مسئله توقف هیلبرت، غیرقابل حل بود بنابراین هسته محاسباتی قضیه عدم تکامل را مشخص می‌نماید. این کار همراه با کار گودل درباره توابع بازگشتی، بیان کرد که مجموعه‌هایی از دستورالعمل‌های ساده وجود دارند که وقتی باهم قرار می‌گیرند، می‌توانند هر محاسبه‌ای را تولید کنند. کار گودل نشان داد که تصور محاسبات، اساساً منحصربه‌فرد می‌باشد.
جان فون نویمان با این نتایج برای طراحی دستگاه‌های محاسباتی جامع نتیجه گیری کرد. اولین زبان برنامه نویسی رسمی دهه ۱۹۳۰ نشان دادند که چنین کامپیوتری، مفید است. اولین پیاده سازی واقعی یک دستگاه تورینگ کامل در سال ۱۹۴۱ اشکار شد: برنامه کنترل شده Z3 مربوط به کنراد تسوزه، ولین اولین دستگاه طراحی شده برای تورینگ کامل و مناسب برای جامعیت، ۱۹۴۶ ENIAC می‌باشد. این دستگاه می‌تواند محدوده زیادی از مشکلات مناسب و موثر را در دهه ۱۹۴۰ حل نماید که مربوط به طراحی بمب اتمی است.

تئوری قابلیت محاسبه[ویرایش]

اولین نتیجه تئوری قابلیت محاسبه این است که برای پیش بینی اینکه یک برنامه تورینگ کامل چه چیزی را در بلندمدت به طور اختیاری انجام می‌دهد، غیرممکن است. مثلاً، تعیین ان برای هر جفت برنامه – ورودی، غیرممکن است که ایا برنامه‌ای که بر روی ورودی‌ها عمل می‌کند، به طور موقتی متوقف شده است یا برای همیشه ادامه دارد.
تعیین این مساله، غیرممکن است که آیا برنامه "درست" را برمی گرداند یا "اشتباه" را. برای هر مشخصه‌ای از خروجی‌های احتمالی و مشروط برنامه، تعیین اینکه این مشخصه صادق است یا نه، غیرممکن می‌باشد. این مساله می‌تواند باعث مشکلاتی در عمل در زمان انالیز و تحلیل برنامه‌های کامپیوتری واقعی شود. یک روش برای اجتناب از این مساله، باعث برنامه‌هایی برای توقف اجرا بعداز دوره زمانی ثابت یا محدود کردن قدرت دستورالعمل‌های کنترل جریان می‌باشد. چنین سیستم‌هایی، با طراحی، تورینگ کامل نمی‌باشند. قضیه دیگر نشان می‌دهد که مشکلات قابل حلی با زبان‌های تورینگ کامل وجود دارند که نمی‌توان با هر زبانی با تنها قابلیت حلقه زنی محدود حل نمود (یعنی هر زبانی که تضمین می‌کند که هر برنامه‌ای برای یک لحظه مکث می‌کند).
با تعیین زبان مکث ار محدود، تابع قابل محاسبه‌ای که با استدلال محاوره‌ای کانتور در تمام توابع قابل محاسبه در ان زبان ایجاد می‌شود، در ان زبان قابل محاسبه نمی‌باشد.

اوراکل‌های تورینگ[ویرایش]

کامپیوتری با دستیابی به نوار نامتناهی به داده‌ها، قدرتمندتر از یک دستگاه تورینگ می‌باشد زیرا این نوار می‌تواند در اصل شامل راه حلی برای مشکلات مکث کردن یا هر مشکلا غیرقابل تصمیم گیری دیگری باشد. نوار نامتناهی داده‌ها، یک اوراکل تورینگ می‌باشد. حتی یک اوراکل تورینگ با داده‌های تصادفی، قابل محاسبه نمی‌باشد زیرا تنها محاسبات زیادی وجود دارند ولی اوراکل‌های زیادی وجود دارند. دستگاهی که به استثناء دستیابی به برخی از اوراکل‌های تورینگ، جامع است، جامع ضعیف نامیده می‌شود.

فیزیک دیجیتالی[ویرایش]

تمام قوانین شناخته شده از فیزیک، پیامدهایی دارند که با مجموعه‌ای از تقریب‌ها در یک کامپیوتر دیجیتالی، قابل محاسبه می‌باشند. فرضیه‌ای به نام فیزیک دیجیتالی بیان می‌کند که این مساله، تصادفی نیست که بدین علت است که خود جامعیت در دستگاه تورینگ جامع، قابل محاسبه می‌باشد. این مساله بیان می‌کند که هیچ کامپیوتر قدرتمندتر از دستگاه تورینگ جامع را می‌توان به طور فیزیکی ساخت.

نمونه‌ها[ویرایش]

سیستم‌های محاسباتی (الجبرا، حساب) که به عنوان سیستم‌های تورینگ کامل موردبحث قرار می‌گیرند، سیستم‌های موردنظر برای مطالعه علوم کامپیوتری تئوریکی می‌باشند. انها خیلی ساده هستند بنابراین درک محدودیت‌های محاسباتی، اسانتراست. دراینجا برخی از انها موجود می‌باشند:

اکثر زبان‌های برنامه نویسی، مرسوم و غیرمرسوم، تورینگ کامل می‌باشند. این زبان‌ها عبارتند از:

  • زبان‌های چندمنظوره در کاربردهای گسترده.
  • اکثر زبان‌هایی که از نمونه‌های کم کاربردتر استفاده می‌کنند.
  • زبان‌های تابعی نظیر Lisp، Haskell.
  • زبان‌های برنامه نویسی منطقی نظیر Prolog.
  • زبان‌های تشریحی نظیر XSLT
  • زبان‌های برنامه نویسی رمزی، شکلی از خلاقیت ریاضی که دران برنامه نویس درباره نحوه انجام ساختارهای برنامه نویسی پایه‌ای در یک زبان مشکل ولی هم ارز با تورینگ کار می‌کند.

تورنیگ کامل، گزاره‌ای از توانایی می‌باشد به جای تجویزی از ویژگی‌های خاص زبان استفاده شده برای پیاده سازی ان توانایی. ویژگی‌های استفاده شده برای انجام تورینگ کامل می‌توانند کاملاً متفاوت باشند. سیستم‌های فرترن از ساختارهای حلقه‌ای حتی گزاره‌های goto برای انجام تکرار استفاده می‌کنند؛Haskell ,Prolog، که فاقد حله می‌باشند از بازگشت استفاده می‌کنند.
تورینگ کامل در SQL، از طریق ویژگی‌های استاندارد پیشرفته پیاده سازی می‌شود، که دلیلی برای قدرتمندبودن زبان‌های غیراز تورینگ، نادر است. هرچقدر این زبان، قدرتمندتر باشد، وظایفی که برای ان انجام می‌شود، پیچیده تر می‌باشد و فقدان کامل بودن ان به صورت یک مانع و اشکال، زودتر می‌باشد و بسط والحاق ان را تشویق می‌کند تا اینکه تورینگ کامل شود.
حساب لاندا، تورینگ کامل می‌باشد ولی حساب‌های لاندای زیادی شامل سیستم F تورینگ کامل نمی‌باشند. ارزش سیستم‌های معلوم شده مبتنی بر توانایی انها برای نمایش معمولترین برنامه‌های کامپیوتری درحین شناسایی خطاهای بیشتر می‌باشد.
قانون ۱۱۰ و بازی زندگی Conway، تورینگ کامل می‌باشند.

زبان‌های غیر تورینگ کامل[ویرایش]

زبان‌های محاسباتی زیادی وجود دارند که تورینگ کامل نمی‌باشند. یک چنین نمونه‌ای، مجموعه‌ای از زبان‌های قانونی می‌باشد که با دستگاه‌های خودکار متناهی تولید می‌شوند.
یک الحاق قدرتمندتر ولی غیرتورینگ کامل از دستگاه‌های خودکار متناهی، گروهی از ماشین‌های خودکار و گرامرهای بدون متن می‌باشد که برای ایجاد درخت‌های پویشی در مرحله ابتدایی برنامه استفاده می‌شوند. نمونه‌های بیشتر شامل برخی از نسخه‌های ابتدایی زبان‌های سایه زنی پیکسل جاسازی شده در Direct3D و OpenGL می‌باشند.
در زبان‌های برنامه نویسی تابعی کلی، تمام توابع، کلی می‌باشند و باید پایان یابند نظیر Charity، Epigram. Charity، از یک سیستم نوعی و ساختارهای کنترلی مبتنی بر تئوری گروهی استفاده می‌کند درحالیکه Epigram از نوع‌های وابسته استفاده می‌کند. زبان LOOP طراحی می‌شود بنابراین تنها توابعی را محاسبه نماید که بازگشتی ضروری می‌باشند. تمام اینها، زیرمجموعه‌های مناسب از توابع قابل محاسبه را محاسبه می‌کنند زیرا مجموعه کاملی از توابع قابل محاسبه، شمارش پذیر نمی‌باشند.

زبان داده‌ها[ویرایش]

تصوری از تورینگ کامل به زبان‌هایی نظیر XML، JSON، YAML، S اعمال نمی‌شود زیرا انها برای نمایش داده‌های ساختاریافته استفاده می‌شوند ولی محاسبات را توصیف نمی‌کنند. اینها به عنوان زبان نشانه‌گذاری و یا زبان‌های محفظه‌ای یا زبان‌های توصیف داده‌ها می‌باشند.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

مشارکت‌کنندگان ویکی‌پدیا، «Turing completeness»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۴ ژوئن ۲۰۱۳).