The Complexity of Songs
"ધ કોમ્પ્લેક્સિટી ઓફ સોંગ્સ" એ કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરી વિશેની મજાક તરીકે 1977માં કોમ્પ્યુટર વૈજ્ઞાનિક ડોનાલ્ડ ક્નુથનો વિદ્વતાપૂર્ણ લેખ છે. આ લેખ લોકપ્રિય ગીતોની લાંબી અને વિષયવસ્તુથી સમૃદ્ધ લોકગીતોમાંથી ખૂબ જ પુનરાવર્તિત ગ્રંથોમાં ઓછી અથવા કોઈ અર્થપૂર્ણ સામગ્રી સાથે વહેંચવાની વૃત્તિ પર ભાર મૂકે છે. લેખ નોંધે છે કે લંબાઈ એન શબ્દોના ગીતને યાદ કરીને રજૂ કરી શકાય છે, દા. ત., માત્ર શબ્દો (ગીતની "જગ્યા જટિલતા") અથવા તેનાથી પણ ઓછા. લેખ સારાંશ ક્નુથ લખે છે કે ગીતોની જગ્યાની જટિલતાને ઘટાડવા માટે "આપણા પ્રાચીન પૂર્વજોએ અવલંબનની વિભાવનાની શોધ કરી હતી", જે ત્યારે નિર્ણાયક બને છે જ્યારે મોટી સંખ્યામાં ગીતો કોઈની યાદશક્તિ માટે પ્રતિબદ્ધ હોય છે. ક્નુથના લેમ્મા 1 જણાવે છે કે જો એન એ ગીતની લંબાઈ છે, તો વિરામ ગીતની જટિલતાને સીએનમાં ઘટાડે છે, જ્યાં પરિબળ સી <1 છે. નુથ આગળ ઓ () જટિલતા સાથે ગીતો બનાવવાની રીત દર્શાવે છે, જે અભિગમ "ઓ. મેકડોનાલ્ડ નામના સ્કોટિશ ખેડૂત દ્વારા વધુ સુધારવામાં આવ્યો છે". વધુ કુશળ અભિગમો જટિલતા ઓ () ના ગીતો આપે છે, જે "દિવાલ પર બીયરની એમ બોટલ" તરીકે ઓળખાતો વર્ગ છે. છેવટે, 20મી સદી દરમિયાનની પ્રગતિ-એ હકીકત દ્વારા ઉત્તેજિત કે "આધુનિક દવાઓના આગમનથી હજુ પણ ઓછી યાદશક્તિની માંગ થઈ છે"-અંતિમ સુધારણા તરફ દોરી જાય છેઃ અવકાશ જટિલતા ઓ (1) સાથે મનસ્વી રીતે લાંબા ગીતો અસ્તિત્વ ધરાવે છે, દા. ત. પુનરાવર્તન સંબંધ દ્વારા વ્યાખ્યાયિત ગીત 'તે રસ્તો છે', 'મને તે ગમે છે,', બધા માટે 'ઉહ હુ', 'ઉહ હુ' વધુ વિકાસ સાન ડિએગો સ્ટેટ યુનિવર્સિટીના પ્રોફેસર કર્ટ આઈઝમેને એસીએમના સંદેશાવ્યવહારને લખેલા પત્રમાં પછીના દેખીતી રીતે અજેય અંદાજમાં વધુ સુધારો કરે છે. તેઓ એક નિરીક્ષણ સાથે શરૂઆત કરે છે કે વ્યવહારુ ઉપયોગો માટે બિગ ઓહ સંકેતલિપીમાં "છુપાયેલા અચળાંક" c નું મૂલ્ય શક્યતા અને અશક્યતા વચ્ચેનો તફાવત કરવામાં નિર્ણાયક હોઈ શકે છેઃ ઉદાહરણ તરીકે 1080 નું અચળ મૂલ્ય કોઈપણ જાણીતા ઉપકરણની ક્ષમતા કરતાં વધી જશે. તેમણે વધુમાં નોંધ્યું છે કે મધ્યયુગીન યુરોપમાં પહેલેથી જ એક તકનીક જાણીતી છે જેમાં પુનરાવર્તન સંબંધના આધારે મનસ્વી સૂરની લખાણની સામગ્રી રેકોર્ડ કરી શકાય છે, જ્યાં, મોટા-ઓહ અચળાંક c નું મૂલ્ય 2 ની બરાબર મળે છે. જો કે તે તારણ આપે છે કે અન્ય સંસ્કૃતિએ ઓ (0) ની સંપૂર્ણ નીચલી સીમા પ્રાપ્ત કરી છે. જેમ પ્રો. આઈઝમેન કહે છેઃ "જ્યારે મેફ્લાવર સમુદ્રયાત્રીઓ પ્રથમ વખત આ કિનારાઓ પર ઉતર્યા હતા, ત્યારે મૂળ અમેરિકનોને માહિતી સંગ્રહ અને પુનઃપ્રાપ્તિના સિદ્ધાંતમાં તેમની સિદ્ધિ પર ગર્વ હતો, શરૂઆતમાં અજાણ્યાઓને સંપૂર્ણ મૌન સાથે આવકાર્યા હતા. આનો હેતુ ગીતોની જટિલતામાં તેમની ટોચની સિદ્ધિને વ્યક્ત કરવાનો હતો, એટલે કે પ્રદર્શન કે સી = 0 જેટલી નીચી મર્યાદા ખરેખર પ્રાપ્ય છે. જો કે યુરોપિયનો આ કલ્પનાને સમજવા માટે તૈયાર નહોતા, અને વડાઓ, તેમની સિદ્ધિઓ વ્યક્ત કરવા માટે એક સામાન્ય આધાર સ્થાપિત કરવા માટે પાછળથી પુનરાવર્તિત સંબંધ દ્વારા વર્ણવેલ અભિગમ દર્શાવવા માટે આગળ વધ્યા, જ્યાં, c = 1 દ્વારા આપવામાં આવેલી ઓછી જટિલતા સાથે. ઓ (1) અવકાશ જટિલતા પરિણામનો અમલ ગાય એલ. સ્ટીલ, જુનિયર દ્વારા પણ કરવામાં આવ્યો હતો, જેને કદાચ ક્નુથના લેખ દ્વારા પડકારવામાં આવ્યો હતો. ડૉ. સ્ટીલના ટેલનેટ સોંગમાં ઘાતાંકીય પુનરાવર્તન પર આધારિત સંપૂર્ણપણે અલગ અલ્ગોરિધમનો ઉપયોગ કરવામાં આવ્યો છે, જે ટેલનેટના કેટલાક અમલીકરણ પરની પેરોડી છે. દર્રાહ ચાવેએ સૂચવ્યું હતું કે માનવ ગીતનું જટિલતા વિશ્લેષણ વિદ્યાર્થીઓને જટિલતા સિદ્ધાંત શીખવવા માટે ઉપયોગી શિક્ષણશાસ્ત્રનું સાધન બની શકે છે. પ્રોફેસર એલન શેરમનનો લેખ "સુપરપોલિલોગેરિથમિક સબએક્સપોનેન્શિયલ ફંક્શન્સ પર" લખે છે કે ક્નુથનો લેખ કાર્યોના વિશેષ વર્ગના વિશ્લેષણ માટે નિર્ણાયક હતો. સંદર્ભો બાહ્ય કડીઓ "ગીતોની જટિલતા", ક્નુથ, ડોનાલ્ડ ઇ. (1984). કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરી સંગીતનું ગણિત ઇન-જોક્સ કમ્પ્યુટર રમૂજ ડોનાલ્ડ ક્નુથ 1977 દસ્તાવેજો કમ્પ્યુટર વિજ્ઞાનના કાગળો સંગીત અને રમૂજ