مهرداد فدایی پله شاهی - دانشجوی کارشناسی ارشد علوم کامپیوتر، دانشگاه آزاد اسلامی، واحد لاهیجان

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

تورینگ، پیچیدگی، اتوماتا، کوانتوم