Queue automaton
કતાર મશીન, કતાર ઓટોમેટન અથવા પુલઅપ ઓટોમેટન (પીયુએ) એ એક મર્યાદિત સ્થિતિ મશીન છે જે અનંત-મેમરી કતારમાંથી માહિતી સંગ્રહિત કરવાની અને પુનઃપ્રાપ્ત કરવાની ક્ષમતા ધરાવે છે. તે ટ્યુરિંગ મશીનની સમકક્ષ ગણતરીનું એક મોડેલ છે, અને તેથી તે ઔપચારિક ભાષાઓના સમાન વર્ગ પર પ્રક્રિયા કરી શકે છે. એક કતાર મશીનને છ-ટુપલ તરીકે વ્યાખ્યાયિત કરી શકાય છે જ્યાં સ્થિતિઓનો મર્યાદિત સમૂહ છે; ઇનપુટ મૂળાક્ષરનો મર્યાદિત સમૂહ છે; મર્યાદિત કતાર મૂળાક્ષર છે; પ્રારંભિક કતાર પ્રતીક છે; પ્રારંભિક સ્થિતિ છે; સંક્રમણ કાર્ય છે. મશીન રૂપરેખાંકન એ તેની સ્થિતિ અને કતારની સામગ્રીની ક્રમબદ્ધ જોડી છે, જ્યાં તેની ક્લાઈન ક્લોઝર સૂચવે છે. ઇનપુટ શબ્દમાળા પર પ્રારંભિક રૂપરેખાંકનને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે, અને એક રૂપરેખાંકનમાંથી બીજામાં સંક્રમણને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ જ્યાં કતાર મૂળાક્ષરમાંથી એક પ્રતીક છે, તે કતાર પ્રતીકો () નો ક્રમ છે, અને. સંબંધમાં કતારના "ફર્સ્ટ-ઇન-ફર્સ્ટ-આઉટ" ગુણધર્મની નોંધ લો. મશીન સ્ટ્રિંગ સ્વીકારે છે જો મર્યાદિત સંખ્યામાં સંક્રમણો પછી પ્રારંભિક રૂપરેખાંકન સ્ટ્રિંગને સમાપ્ત કરવા માટે વિકસિત થાય છે (નલ સ્ટ્રિંગ સુધી પહોંચે છે), અથવા અન્યથા જણાવ્યું છે કે, જો ટ્યુરિંગની પૂર્ણતા હોય તો આપણે સાબિત કરી શકીએ છીએ કે કતાર મશીન ટ્યુરિંગ મશીનની સમકક્ષ છે તે દર્શાવીને કે કતાર મશીન ટ્યુરિંગ મશીનનું અનુકરણ કરી શકે છે અને તેનાથી ઊલટું. ટ્યુરિંગ મશીનને કતાર મશીન દ્વારા અનુકરણ કરી શકાય છે, જે ટ્યુરિંગ મશીનની સામગ્રીની નકલ દરેક સમયે તેની કતારમાં રાખે છે, જેમાં બે વિશેષ માર્કર્સ હોય છેઃ એક ટ્યુરિંગ મશીનના માથાની સ્થિતિ માટે અને એક ટેપના અંત માટે; તેના સંક્રમણો ટ્યુરિંગ મશીનની નકલ કરીને સમગ્ર કતારમાંથી પસાર થાય છે, તેના દરેક પ્રતીકોને બહાર કાઢે છે અને પોપ કરેલા પ્રતીકને ફરીથી એન્ક્વીંગ કરે છે, અથવા, માથાની સ્થિતિ નજીક, ટ્યુરિંગ મશીન સંક્રમણની અસરની સમકક્ષ. ક્યુ મશીનને ટ્યુરિંગ મશીન દ્વારા અનુકરણ કરી શકાય છે, પરંતુ વધુ સરળતાથી મલ્ટી-ટેપ ટ્યુરિંગ મશીન દ્વારા, જે સામાન્ય સિંગલ-ટેપ મશીનની સમકક્ષ હોવાનું જાણીતું છે. સિમ્યુલેટિંગ કતાર મશીન એક ટેપ પર ઇનપુટ વાંચે છે અને બીજી પર કતારને સંગ્રહિત કરે છે, જેમાં ટેપના શરૂઆત અને અંતના પ્રતીકોમાં સરળ સંક્રમણો દ્વારા નિર્ધારિત દબાણ અને પૉપ હોય છે. આનો ઔપચારિક પુરાવો ઘણીવાર સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનના અભ્યાસક્રમોમાં કરવામાં આવતી કવાયત છે. એપ્લિકેશન્સ કતાર મશીનો એક સરળ મોડેલ પ્રદાન કરે છે જેના પર કમ્પ્યુટર આર્કિટેક્ચર, પ્રોગ્રામિંગ ભાષાઓ અથવા અલ્ગોરિધમ્સ આધારિત છે. કમ્પ્યુટેબિલિટી ટ્યુરિંગ મશીન સમકક્ષ નિર્ધારિત મર્યાદિત ઓટોમેટન પુશડાઉન ઓટોમેટન ટેગ સિસ્ટમ મેનુફેક્ટોરિયા પણ જુઓ, જે બ્રાઉઝર ફ્લેશ ગેમ છે જે કતાર મશીન મોડેલનો ઉપયોગ કરીને વિવિધ અલ્ગોરિધમ્સના અમલીકરણ સાથે ખેલાડીને કાર્ય કરે છે. સંદર્ભો ઓટોમેટા (ગણતરી) ગણતરીના નમૂનાઓ