Queue automaton
একটি সারি মেশিন, সারি অটোমেটন, বা পুলআপ অটোমেটন (পিইউএ) একটি সীমাবদ্ধ অবস্থা মেশিন যা একটি অসীম-মেমরি সারি থেকে তথ্য সংরক্ষণ এবং পুনরুদ্ধার করার ক্ষমতা রাখে। এটি একটি টুরিং মেশিনের সমতুল্য গণনার একটি মডেল এবং তাই এটি একই শ্রেণীর আনুষ্ঠানিক ভাষাগুলি প্রক্রিয়া করতে পারে। একটি সারি যন্ত্রকে ছয়-টুপল হিসাবে সংজ্ঞায়িত করা যেতে পারে যেখানে অবস্থার একটি সসীম সেট; ইনপুট বর্ণমালার সসীম সেট; সসীম সারি বর্ণমালা; প্রাথমিক সারি প্রতীক; শুরু অবস্থা; ট্রানজিশন ফাংশন। একটি মেশিন কনফিগারেশন হল তার অবস্থা এবং সারির বিষয়বস্তুর একটি সাজানো জোড়া, যেখানে এর ক্লিন ক্লোজার বোঝায়। একটি ইনপুট স্ট্রিং-এর প্রারম্ভিক বিন্যাসকে এইভাবে সংজ্ঞায়িত করা হয়, এবং একটি বিন্যাস থেকে অন্য বিন্যাসে রূপান্তরকে এইভাবে সংজ্ঞায়িত করা হয়ঃ যেখানে সারি বর্ণমালা থেকে একটি প্রতীক, সারি চিহ্নগুলির একটি ক্রম (), এবং। রিলেশনে সারির "ফার্স্ট-ইন-ফার্স্ট-আউট" বৈশিষ্ট্যটি লক্ষ্য করুন। মেশিনটি একটি স্ট্রিং গ্রহণ করে যদি সীমিত সংখ্যক রূপান্তরের পরে প্রারম্ভিক কনফিগারেশনটি স্ট্রিংটি শেষ করার জন্য বিকশিত হয় (নাল স্ট্রিংয়ে পৌঁছায়), বা অন্যথায় বলা হয়, যদি টুরিং সম্পূর্ণতা আমরা প্রমাণ করতে পারি যে একটি সারি মেশিন একটি টুরিং মেশিনের সমতুল্য যে একটি সারি মেশিন একটি টুরিং মেশিনকে অনুকরণ করতে পারে এবং তদ্বিপরীত। একটি টুরিং মেশিন একটি সারি মেশিন দ্বারা সিমুলেট করা যেতে পারে যা টুরিং মেশিনের বিষয়বস্তুর একটি অনুলিপি তার সারিতে সর্বদা রাখে, দুটি বিশেষ চিহ্নিতকারী সহঃ একটি টুরিং মেশিনের মাথার অবস্থানের জন্য এবং একটি টেপের শেষের জন্য; এর রূপান্তরগুলি পুরো সারির মধ্য দিয়ে দৌড়ে টুরিং মেশিনের অনুকরণ করে, এর প্রতিটি প্রতীককে পপ করে এবং পপ করা প্রতীকটি বা মাথার অবস্থানের কাছাকাছি, টুরিং মেশিনের রূপান্তর প্রভাবের সমতুল্য পুনরায় এনকুয়েট করে। একটি সারি মেশিন একটি টুরিং মেশিন দ্বারা সিমুলেট করা যেতে পারে, তবে আরও সহজে একটি মাল্টি-টেপ টুরিং মেশিন দ্বারা, যা একটি সাধারণ একক-টেপ মেশিনের সমতুল্য হিসাবে পরিচিত। সিমুলেটিং কিউ মেশিনটি একটি টেপে ইনপুট পড়ে এবং দ্বিতীয়টিতে সারিটি সংরক্ষণ করে, টেপের শুরু এবং শেষ প্রতীকগুলিতে সহজ রূপান্তর দ্বারা সংজ্ঞায়িত ধাক্কা এবং পপ সহ। এর একটি আনুষ্ঠানিক প্রমাণ প্রায়শই তাত্ত্বিক কম্পিউটার বিজ্ঞান কোর্সের একটি অনুশীলন। অ্যাপ্লিকেশন সারি মেশিনগুলি একটি সহজ মডেল সরবরাহ করে যার উপর ভিত্তি করে কম্পিউটার আর্কিটেকচার, প্রোগ্রামিং ভাষা বা অ্যালগরিদম তৈরি করা যায়। আরও দেখুন গণনাযোগ্যতা টুরিং মেশিনের সমতুল্য নির্ধারিত সীমাবদ্ধ অটোমেটন পুশডাউন অটোমেটন ট্যাগ সিস্টেম ম্যানুফ্যাক্টরিয়া, একটি ব্রাউজার ফ্ল্যাশ গেম যা খেলোয়াড়কে একটি সারি মেশিন মডেল ব্যবহার করে বিভিন্ন অ্যালগরিদম বাস্তবায়নের কাজ করে। তথ্যসূত্র স্বয়ংক্রিয় (গণনা) গণনার মডেল