Cigarette smokers problem
સિગારેટ પીનારાઓની સમસ્યા કોમ્પ્યુટર વિજ્ઞાનમાં એક સમવર્તી સમસ્યા છે, જેનું મૂળ વર્ણન 1971માં સુહાસ પાટિલે કર્યું હતું. આ સમસ્યાની "વ્યવહારુ વિચારણાઓ દ્વારા ન્યાયી ઠેરવી ન શકાય તેવા પ્રતિબંધો" હોવા બદલ ટીકા કરવામાં આવી છે. સમસ્યાનું વર્ણન પાટિલની સમસ્યામાં "તદ્દન મનસ્વી" પ્રતિબંધનો સમાવેશ થાય છે કે જે પ્રક્રિયા ઘટકો પૂરા પાડે છે તેને બદલી શકાતી નથી અને કોઈ શરતી નિવેદનોનો ઉપયોગ કરી શકાતો નથી ". ધારો કે સિગારેટ બનાવવા અને ધૂમ્રપાન કરવા માટે ત્રણ ઘટકોની જરૂર પડે છેઃ તમાકુ, કાગળ અને માચિસ. એક ટેબલની આસપાસ ત્રણ ધૂમ્રપાન કરનારાઓ હોય છે, જેમાંથી દરેકને ત્રણ ઘટકોમાંથી એકનો અનંત પુરવઠો હોય છે-એક ધૂમ્રપાન કરનારને તમાકુનો અનંત પુરવઠો હોય છે, બીજાને કાગળ હોય છે, અને ત્રીજા પાસે મેળ હોય છે. એક બિન-ધૂમ્રપાન કરનાર એજન્ટ પણ હોય છે જે ધૂમ્રપાન કરનારાઓને ટેબલ પર મૂકવા માટે બે પુરવઠો પસંદ કરીને મનસ્વી રીતે (બિન-નિર્ણાયક રીતે) તેમની સિગારેટ બનાવવા માટે સક્ષમ બનાવે છે. ધૂમ્રપાન કરનાર કે જેની પાસે ત્રીજો પુરવઠો હોય તેણે ટેબલ પરથી બે વસ્તુઓ દૂર કરવી જોઈએ, તેનો ઉપયોગ કરીને (તેમના પોતાના પુરવઠાની સાથે) સિગારેટ બનાવવી જોઈએ, જેને તેઓ થોડા સમય માટે ધૂમ્રપાન કરે છે. એકવાર ધુમ્રપાન કરનાર તેની સિગારેટ પૂરી કરી લે, પછી એજન્ટ ટેબલ પર બે નવી રેન્ડમ વસ્તુઓ મૂકે છે. આ પ્રક્રિયા કાયમ ચાલુ રહે છે. ટેબલ પરની વસ્તુઓનું પ્રતિનિધિત્વ કરવા માટે ત્રણ સેમાફોરનો ઉપયોગ કરવામાં આવે છે; એજન્ટ યોગ્ય સેમાફોરને સંકેત આપવા માટે વધારે છે કે વસ્તુ ટેબલ પર મૂકવામાં આવી છે, અને ધૂમ્રપાન કરનારાઓ વસ્તુઓને દૂર કરતી વખતે સેમાફોરને ઘટાડે છે. ઉપરાંત, દરેક ધુમ્રપાન કરનાર પાસે સંકળાયેલ સેમાફોર હોય છે જેનો ઉપયોગ તેઓ એજન્ટને સંકેત આપવા માટે કરે છે કે ચોક્કસ ધુમ્રપાન કરનાર ધૂમ્રપાન કરે છે; એજન્ટ પાસે એક પ્રક્રિયા હોય છે જે દરેક ધુમ્રપાન કરનારના સેમાફોર પર રાહ જુએ છે જેથી એજન્ટને ખબર પડે કે તે નવી વસ્તુઓ ટેબલ પર મૂકી શકે છે. તમાકુનો પુરવઠો ધરાવતા ધુમ્રપાન કરનારનું એક સરળ સ્યુડોકોડ અમલીકરણ નીચે મુજબ દેખાઈ શકે છેઃ ડેફ તમાકુ _ સ્મોકર (): પુનરાવર્તિતઃ paper.wait () matches.wait () સ્મોક () tobacco_smoker_done.signal () જો કે, આ મડાગાંઠ તરફ દોરી શકે છે; જો એજન્ટ ટેબલ પર કાગળ અને તમાકુ મૂકે, તો તમાકુ સાથે ધૂમ્રપાન કરનાર કાગળ દૂર કરી શકે છે અને માચિસ સાથે ધૂમ્રપાન કરનાર તમાકુ લઈ શકે છે, જેનાથી બંને તેમની સિગારેટ બનાવવામાં અસમર્થ રહે છે. ઉકેલ એ છે કે એજન્ટમાં ફેરફાર કર્યા વિના, ડેડલોકને અટકાવતી વધારાની પ્રક્રિયાઓ અને સેમાફોર્સને વ્યાખ્યાયિત કરવી. ટીકાકાર પાટિલે સિગારેટ પીનારાઓની સમસ્યા પર નીચેની મર્યાદાઓ મૂકીઃ એજન્ટ કોડમાં ફેરફાર કરી શકાતો નથી. ઉકેલને શરતી નિવેદનોનો ઉપયોગ કરવાની મંજૂરી નથી. પાટિલે પેટ્રી જાળીના સંદર્ભમાં સાબિતીનો ઉપયોગ કરીને દાવો કર્યો હતો કે સિગારેટના ધૂમ્રપાન કરનારાઓની સમસ્યાનો ઉકેલ એડસ્ગર ડીજ્ક્સ્ટ્રાના સેમાફોર પ્રિમિટિવ્સનો ઉપયોગ કરીને અશક્ય છે, અને સૂચવે છે કે વધુ શક્તિશાળી પ્રિમિટિવ જરૂરી છે. જો કે, ડેવિડ પાર્નાસે દર્શાવ્યું હતું કે જો સેમાફોર્સના એરેનો ઉપયોગ કરવામાં આવે તો પાટિલનો પુરાવો અપૂરતો છે, જે એક ઉકેલ પ્રદાન કરે છે જે સહાયક પ્રક્રિયાઓનો ઉપયોગ કરે છે જે યોગ્ય ધુમ્રપાન કરનારને આગળ વધવા માટે સંકેત આપવા માટે અંકગણિત કરે છે. એલન બી. ડાઉનીના જણાવ્યા અનુસાર, પ્રથમ પ્રતિબંધ અર્થપૂર્ણ છે, કારણ કે જો એજન્ટ ઓપરેટિંગ સિસ્ટમનું પ્રતિનિધિત્વ કરે છે, તો દર વખતે નવી એપ્લિકેશન આવે ત્યારે તેમાં ફેરફાર કરવો ગેરવાજબી અથવા અશક્ય હશે. જો કે, પર્નાસ દલીલ કરે છે કે બીજો પ્રતિબંધ અન્યાયી છેઃ પાટિલે નોંધાવેલી મર્યાદાઓ તેમના આદિકાળની મર્યાદાઓ છે, પરંતુ તે ડિજ્ક્સ્ટ્રા દ્વારા વર્ણવવામાં આવેલા આદિકાળની મર્યાદાઓ નથી. જો કે, એ મહત્વનું છે કે આવી તપાસ [ડિજ્ક્સ્ટ્રા પ્રિમિટિવ્સની] કૃત્રિમ પ્રતિબંધો હેઠળ આ પ્રિમિટિવ્સની શક્તિની તપાસ ન કરે. કૃત્રિમ દ્વારા અમારો અર્થ એવા પ્રતિબંધો છે જે વ્યવહારુ વિચારણાઓ દ્વારા ન્યાયી ઠેરવી શકાતા નથી. આ લેખકના મતે, શરતી અથવા સેમાફોર એરે પર પ્રતિબંધ મૂકતા પ્રતિબંધો કૃત્રિમ છે. આ પણ જુઓ ભોજન ફિલસૂફોની સમસ્યા વાચકો-લેખકોની સમસ્યા ઊંઘતા વાળંદની સમસ્યા સંદર્ભો વિરોધાભાસ સમરૂપતા (કોમ્પ્યુટર વિજ્ઞાન) ઉદાહરણ સ્યુડોકોડ સાથેના લેખો