History of the Church–Turing thesis
চার্চ-টুরিং থিসিসের ("থিসিস") ইতিহাসে ফাংশনের প্রকৃতি অধ্যয়নের ইতিহাস জড়িত যার মানগুলি কার্যকরভাবে গণনাযোগ্য; অথবা, আরও আধুনিক ভাষায়, ফাংশন যার মানগুলি অ্যালগরিদমিকভাবে গণনাযোগ্য। এটি আধুনিক গাণিতিক তত্ত্ব এবং কম্পিউটার বিজ্ঞানের একটি গুরুত্বপূর্ণ বিষয়, বিশেষত অ্যালনজো চার্চ এবং অ্যালান টুরিংয়ের কাজের সাথে যুক্ত। "গণনা" এবং "পুনরাবৃত্তির" অর্থ নিয়ে বিতর্ক এবং আবিষ্কার দীর্ঘ এবং বিতর্কিত। এই নিবন্ধটি "স্বতঃসিদ্ধ" অর্থের সাম্প্রতিক আলোচনার মাধ্যমে 1889 সালে পিওনোর স্বতঃসিদ্ধ থেকে সেই বিতর্ক এবং আবিষ্কারের বিশদ বিবরণ প্রদান করে। পিনোর গণিতের নয়টি স্বতঃসিদ্ধ 1889 সালে, জুসেপ্পে পেনো ডেডেকিন্ডের কাজের উপর ভিত্তি করে একটি নতুন পদ্ধতি দ্বারা উপস্থাপিত তাঁর গণিতের নীতিগুলি উপস্থাপন করেছিলেন। সোয়ার প্রস্তাব করেন যে "আদিম পুনরাবৃত্তির" উৎপত্তি আনুষ্ঠানিকভাবে পিয়ানো স্বতঃসিদ্ধের সাথে শুরু হয়েছিল, যদিও "ঊনবিংশ শতাব্দীর আগে গণিতবিদরা আনয়ন দ্বারা একটি ফাংশন সংজ্ঞায়িত করার নীতি ব্যবহার করেছিলেন। 1888 সালে ডেডেকিন্ড স্বীকৃত স্বতঃসিদ্ধ ব্যবহার করে প্রমাণ করেন যে, এই ধরনের সংজ্ঞা একটি অনন্য ফাংশনকে সংজ্ঞায়িত করে এবং তিনি এটিকে m + n, m x n এবং mn ফাংশনের সংজ্ঞায় প্রয়োগ করেন। ডেডেকিন্ডের এই কাজের উপর ভিত্তি করে, পেনো 1889 এবং 1891 ধনাত্মক পূর্ণসংখ্যার জন্য পরিচিত পাঁচটি [সিক] স্বতঃসিদ্ধ রচনা করেছিলেন। তাঁর পঞ্চম [সিক] স্বতঃসিদ্ধ, গাণিতিক প্রবর্তনের সহচর হিসাবে, পেনো প্রবর্তন দ্বারা সংজ্ঞা ব্যবহার করেছিলেন, যাকে আদিম পুনরাবৃত্তি বলা হয় (পিটার 1934 এবং ক্লেইন 1936 থেকে)। "। লক্ষ্য করুন যে প্রকৃতপক্ষে পিনোর স্বতঃসিদ্ধ সংখ্যা 9 এবং স্বতঃসিদ্ধ 9 হল পুনরাবৃত্তি/প্রবর্তন স্বতঃসিদ্ধ। "পরবর্তীকালে 9 কে কমিয়ে 5 করা হয় কারণ" 2,3,4 এবং 5 স্বতঃসিদ্ধ যা পরিচয়ের সাথে সম্পর্কিত, অন্তর্নিহিত যুক্তির অন্তর্গত। এর ফলে পাঁচটি স্বতঃসিদ্ধ রয়েছে যা সর্বজনীনভাবে "পেয়ানো স্বতঃসিদ্ধ" নামে পরিচিত হয়ে উঠেছে। পেয়ানো স্বীকার করেছেন (1891বি, পৃ. 93) যে তাঁর স্বতঃসিদ্ধগুলি ডেডেকিন্ড থেকে এসেছে। "। হিলবার্ট এবং 1900 সালে প্যারিসে গণিতবিদদের আন্তর্জাতিক কংগ্রেসে (আই. সি. এম) বিখ্যাত গণিতবিদ ডেভিড হিলবার্ট বিংশ শতাব্দীর গণিতবিদদের জন্য পথ আলোকিত করে এমন সমস্যার একটি সেট উপস্থাপন করেছিলেন-যা এখন হিলবার্টের সমস্যা নামে পরিচিত। হিলবার্টের 2য় এবং 10ম সমস্যাগুলি ("সিদ্ধান্ত সমস্যা") প্রবর্তন করেছিল। তাঁর দ্বিতীয় সমস্যায় তিনি একটি প্রমাণ চেয়েছিলেন যে "গাণিতিক" হল "সামঞ্জস্যপূর্ণ"। কার্ট গোডেল 1931 সালে প্রমাণ করেছিলেন যে, তিনি যাকে "পি" (বর্তমানে যাকে পিয়ানো অ্যারিথমেটিক বলা হয়) বলেছিলেন, তার মধ্যে "অনির্ধারিত বাক্য [প্রস্তাবনা] রয়েছে"। এই কারণে, "পি-তে পি-এর সামঞ্জস্য প্রমাণযোগ্য নয়, যদি পি সামঞ্জস্যপূর্ণ হয়।" যদিও গোডেলের প্রমাণ অ্যালনজো চার্চ এবং অ্যালান টুরিংয়ের সমাধানের জন্য প্রয়োজনীয় সরঞ্জামগুলি প্রদর্শন করবে, তিনি নিজেই এর উত্তর দেবেন না। এটি হিলবার্টের দশম সমস্যার মধ্যে রয়েছে যেখানে একটি প্রশ্ন আসলে উপস্থিত হয়। পদার্থের মূল প্রশ্নটি ছিলঃ "আমরা যখন বলি যে একটি ফাংশন 'কার্যকরভাবে গণনাযোগ্য' তখন আমরা কী বোঝাতে চাই?" উত্তরটি এই প্রভাবের কিছু হবেঃ "যখন একটি যান্ত্রিক পদ্ধতি (প্রক্রিয়া, পদ্ধতি) দ্বারা ফাংশনটি গণনা করা হয়।" যদিও আজকাল সহজেই বলা যায়, প্রশ্নটি (এবং উত্তর) সঠিকভাবে তৈরি হওয়ার আগে প্রায় 30 বছর ধরে ভাসছিল। হিলবার্টের সমস্যা 10-এর মূল বর্ণনাটি নিম্নরূপঃ "10। ডায়োফ্যান্টাইন সমীকরণের সমাধানযোগ্যতা নির্ধারণ। যে কোনও সংখ্যক অজানা পরিমাণ এবং যুক্তিসঙ্গত অবিচ্ছেদ্য সহগ সহ একটি ডায়োফ্যান্টাইন সমীকরণ দেওয়া হয়েছেঃ এমন একটি প্রক্রিয়া তৈরি করা যা অনুসারে সমীকরণটি যুক্তিসঙ্গত পূর্ণসংখ্যায় সমাধানযোগ্য কিনা তা সীমাবদ্ধ সংখ্যক ক্রিয়াকলাপে নির্ধারণ করা যেতে পারে। 1922 সালের মধ্যে, ডায়োফ্যান্টাইন সমীকরণগুলিতে প্রয়োগ করা একটি নির্দিষ্ট প্রশ্ন যে কোনও গাণিতিক সূত্রের জন্য একটি "সিদ্ধান্ত পদ্ধতি" সম্পর্কে আরও সাধারণ প্রশ্ন হিসাবে বিকশিত হয়েছিল। মার্টিন ডেভিস এটিকে এইভাবে ব্যাখ্যা করেছেনঃ ধরুন আমাদের একটি "গণনামূলক পদ্ধতি" দেওয়া হয়েছে যা (1) স্বতঃসিদ্ধগুলির একটি সেট এবং (2) প্রথম-ক্রম যুক্তিতে লেখা একটি যৌক্তিক উপসংহার নিয়ে গঠিত, অর্থাৎ-ডেভিস যাকে "ফ্রেজের ডিডাকশনের নিয়ম" (বা বুলিয়ান যুক্তির আধুনিক সমতুল্য) বলে অভিহিত করেন তাতে লেখা। গডেলের ডক্টরাল গবেষণামূলক প্রবন্ধ প্রমাণ করে যে ফ্রেজের নিয়মগুলি সম্পূর্ণ ছিল. "এই অর্থে যে প্রতিটি বৈধ সূত্র প্রমাণযোগ্য"। সেই উৎসাহব্যঞ্জক তথ্যের পরিপ্রেক্ষিতে, কি একটি সাধারণ "গণনামূলক পদ্ধতি" থাকতে পারে যা আমাদের বলবে যে এর পরিসর থেকে কোনও উপসংহার নেওয়া যেতে পারে কিনা? ডেভিস এই ধরনের গণনামূলক প্রক্রিয়াকে "অ্যালগরিদম" বলে অভিহিত করেন। এটি একটি অ্যালগরিদমও হবে। "নীতিগতভাবে, [এর] জন্য একটি অ্যালগরিদম সমস্ত মানব অবরোহী যুক্তিকে ব্রুট গণনায় হ্রাস করত।" অন্য কথায়ঃ এমন কোনও "অ্যালগরিদম" আছে কি যা আমাদের বলতে পারে যে কোনও সূত্র "সত্য" কিনা (অর্থাৎ। একটি অ্যালগরিদম যা সর্বদা সঠিকভাবে একটি রায় "সত্য" বা "মিথ্যা" প্রদান করে?) ". হিলবার্টের কাছে এটা স্পষ্ট মনে হয়েছিল যে এই সমস্যার সমাধানের মাধ্যমে, এন্টশেইডংসপ্রোবলেম, যে নীতিগতভাবে সমস্ত গাণিতিক প্রশ্ন বিশুদ্ধ যান্ত্রিক পদ্ধতিতে সমাধান করা সম্ভব হওয়া উচিত। অতএব, আদৌ অমীমাংসিত সমস্যাগুলির পরিপ্রেক্ষিতে, যদি হিলবার্ট সঠিক হন, তবে এনটশেইডংসপ্রোবলেম নিজেই অমীমাংসিত হওয়া উচিত। প্রকৃতপক্ষেঃ আমাদের অ্যালগরিদম সম্পর্কে কী? এটি কি সীমিত সংখ্যক ধাপে নির্ধারণ করতে পারে যে এটি নিজেই "সফল" এবং "সত্যবাদী" (অর্থাৎ, এটি একটি অন্তহীন "বৃত্ত" বা "লুপ"-এ আটকে যায় না, এবং এটি সঠিকভাবে তার নিজস্ব আচরণ এবং ফলাফল সম্পর্কে "সত্য" বা "মিথ্যা" রায় দেয়)? হিলবার্টের দ্বিতীয় ও দশম সমস্যা থেকে তিনটি সমস্যা 1928 সালের কংগ্রেসে [ইতালির বোলোনিয়ায়] হিলবার্ট প্রশ্নটিকে খুব যত্ন সহকারে তিনটি অংশে পরিমার্জন করেছেন। স্টিফেন হকিং-এর সারসংক্ষেপ নিম্নরূপঃ "1. প্রমাণ করা যে সমস্ত সত্য গাণিতিক বিবৃতি প্রমাণিত হতে পারে, অর্থাৎ গণিতের সম্পূর্ণতা। "2। প্রমাণ করার জন্য যে শুধুমাত্র সত্য গাণিতিক বিবৃতি প্রমাণ করা যেতে পারে, অর্থাৎ গণিতের সামঞ্জস্য, "3। গণিতের নির্ণয়যোগ্যতা প্রমাণ করার জন্য, অর্থাৎ কোনও প্রদত্ত গাণিতিক প্রস্তাবের সত্য বা মিথ্যা নির্ধারণের জন্য একটি সিদ্ধান্ত পদ্ধতির অস্তিত্ব। আদিম পুনরাবৃত্তির জন্য অপরিবর্তনীয় সাধারণ গাণিতিক ফাংশন গ্যাব্রিয়েল সুদান (1927) এবং উইলহেলম একারম্যান (1928) পুনরাবৃত্তিমূলক ফাংশন প্রদর্শন করে যা আদিম পুনরাবৃত্তিমূলক নয়ঃ "এমন পুনরাবৃত্তিমূলক ফাংশন কি রয়েছে যা আদিম পুনরাবৃত্তির জন্য হ্রাসযোগ্য নয়; এবং বিশেষ করে পুনরাবৃত্তিকে এমন একটি ফাংশন সংজ্ঞায়িত করতে ব্যবহার করা যেতে পারে যা আদিম পুনরাবৃত্তিমূলক নয়? এই প্রশ্নটি 1926 সালে হিলবার্টের কন্টিনিউয়াম সমস্যার উপর একটি অনুমান থেকে উদ্ভূত হয়েছিল এবং অ্যাকারম্যান 1928 দ্বারা উত্তর দেওয়া হয়েছিল [হ্যাঁঃ এমন পুনরাবৃত্তি রয়েছে যা আদিম পুনরাবৃত্তিমূলক নয়]। পরবর্তী বছরগুলিতে ক্লেইন লক্ষ্য করেন যে রোজা পিটার (1935) অ্যাকারম্যানের উদাহরণকে ("সিএফ। এছাড়াও হিলবার্ট-বার্নেস 1934 ") এবং রাফায়েল রবিনসন (1948)। পিটার আরেকটি উদাহরণ (1935) প্রদর্শন করেছিলেন যা ক্যান্টরের তির্যক যুক্তি প্রয়োগ করেছিল। পিটার (1950) এবং অ্যাকারম্যান (1940) "ট্রান্সফাইনাইট রিকার্সন" প্রদর্শন করেছিলেন এবং এটি ক্লেইনকে ভাবতে পরিচালিত করেছিলঃ "আমরা কোনও" রিকার্সন "-এর ধারণা বা সমস্ত" রিকার্সিভ ফাংশন "-এর শ্রেণীকে কোনও সঠিক উপায়ে চিহ্নিত করতে পারি কিনা। ক্লেইন উপসংহারে বলেন যে, সমস্ত "পুনরাবৃত্তির" মধ্যে রয়েছে (i) তাঁর §54-এ আদিম পুনরাবৃত্তিমূলক ফাংশনের আনুষ্ঠানিক গণনায় উপস্থাপিত আনুষ্ঠানিক বিশ্লেষণ এবং (ii) গাণিতিক প্রবর্তনের ব্যবহার। তিনি অবিলম্বে বলেন যে প্রকৃতপক্ষে গোডেল-হারব্র্যান্ড সংজ্ঞা প্রকৃতপক্ষে "সমস্ত পুনরাবৃত্তিমূলক ফাংশনকে চিহ্নিত করে"-নীচের 1934 সালের উদ্ধৃতিটি দেখুন। গডেলের প্রমাণ 1930 সালে গণিতবিদরা হিলবার্টের জন্য একটি গণিত সভা এবং অবসর অনুষ্ঠানের জন্য জড়ো হয়েছিলেন। ভাগ্যক্রমে, "একই বৈঠকে, একজন তরুণ চেক গণিতবিদ, কার্ট গোডেল, ফলাফল ঘোষণা করেছিলেন যা এটিকে [হিলবার্টের মতামত যে তিনটি উত্তরই হ্যাঁ ছিল] একটি গুরুতর আঘাত হিসাবে বিবেচনা করেছিল।" তিনি ঘোষণা করেছিলেন যে 1928 সালে হিলবার্টের তিনটি প্রশ্নের মধ্যে প্রথম দুটির উত্তর ছিল না। পরবর্তীকালে 1931 সালে গডেল তাঁর বিখ্যাত গবেষণাপত্র অন ফর্মালি আনডিসিডিবল প্রপোসিশনস অফ প্রিন্সিপিয়া ম্যাথমেটিকা অ্যান্ড রিলেটেড প্রকাশ করেন এই গবেষণাপত্রের ভূমিকায় মার্টিন ডেভিস একটি সতর্কতা প্রদান করেনঃ "পাঠককে সতর্ক করা উচিত যে [এই বিশেষ গবেষণাপত্রে] গডেল যাকে পুনরাবৃত্তিমূলক ফাংশন বলে অভিহিত করেন তাকে এখন আদিম পুনরাবৃত্তিমূলক ফাংশন বলা হয়। (সংশোধিত পরিভাষাটি ক্লিন দ্বারা প্রবর্তিত হয়েছিল)। "কার্যকর গণনার" গোডেল সম্প্রসারণ ক্লেইনের (1952) উদ্ধৃতি দিতে গিয়ে, "সমস্ত" পুনরাবৃত্তিমূলক ফাংশনের "বৈশিষ্ট্যায়ন গোডেল 1934 দ্বারা 'সাধারণ পুনরাবৃত্তিমূলক ফাংশনের' সংজ্ঞায় সম্পন্ন হয়েছিল, যিনি হারব্র্যান্ডের পরামর্শে তৈরি করেছিলেন" (ক্লেইন 1952:274)। প্রিন্সটন এনজে-র ইনস্টিটিউট ফর অ্যাডভান্সড স্টাডিতে (আইএএস) গোডেল একাধিক বক্তৃতা দেন। মার্টিন ডেভিসের লেখা একটি ভূমিকায় ডেভিস লক্ষ্য করেছেন যে "ডঃ গডেল একটি চিঠিতে বলেছেন যে, এই বক্তৃতাগুলির সময় তিনি মোটেও নিশ্চিত ছিলেন না যে তাঁর পুনরাবৃত্তির ধারণাটি সমস্ত সম্ভাব্য পুনরাবৃত্তির সমন্বয়ে গঠিত।" ডসন বলেছেন যে এই বক্তৃতাগুলি উদ্বেগকে স্পষ্ট করার জন্য ছিল যে "অসম্পূর্ণতা উপপাদ্যগুলি কোনওভাবে আনুষ্ঠানিকতার বিশেষত্বের উপর নির্ভরশীল ছিল": "গডেল তাঁর 1934 সালের গবেষণাপত্রের চূড়ান্ত বিভাগে অ্যাকারম্যানের উদাহরণ উল্লেখ করেছেন," সাধারণ পুনরাবৃত্তিমূলক ফাংশন "ধারণাটিকে অনুপ্রাণিত করার উপায় হিসাবে যা তিনি সেখানে সংজ্ঞায়িত করেছিলেন; তবে এর আগে পাদটীকা 3-এ তিনি ইতিমধ্যে অনুমান করেছিলেন (" একটি অনুসন্ধানমূলক নীতি "হিসাবে) যে সমস্ত সীমাবদ্ধভাবে গণনাযোগ্য ফাংশন প্রাপ্ত করা যেতে পারে। "অনুমানটি তখন থেকে অনেক মন্তব্য পেয়েছে। বিশেষত, মার্টিন ডেভিস যখন গোডেলের 1934 সালের বক্তৃতা [ডেভিস 1965:41 এফএফ-এ] প্রকাশের উদ্যোগ নিয়েছিলেন তখন তিনি এটিকে চার্চের থিসিসের একটি রূপ হিসাবে গ্রহণ করেছিলেন; কিন্তু ডেভিসকে লেখা একটি চিঠিতে। গোডেল জোরালোভাবে বলেছিলেন যে এটি "সত্য নয়" কারণ সেই বক্তৃতাগুলির সময় তিনি "মোটেও নিশ্চিত ছিলেন না" যে তাঁর পুনরাবৃত্তির ধারণাটি "সমস্ত সম্ভাব্য পুনরাবৃত্তি" নিয়ে গঠিত। বরং, তিনি বলেছিলেন, "সেখানে বর্ণিত অনুমানটি কেবল 'সীমাবদ্ধ (গণনা) পদ্ধতি' এবং 'পুনরাবৃত্তিমূলক পদ্ধতি'-র সমতুল্যতাকে বোঝায়।" সমস্যাটি স্পষ্ট করার জন্য গোডেল বক্তৃতাগুলিতে একটি পোস্টস্ক্রিপ্ট যুক্ত করেছিলেন, যেখানে তিনি ইঙ্গিত দিয়েছিলেন যে যা শেষ পর্যন্ত তাকে নিশ্চিত করেছিল যে স্বজ্ঞাতভাবে গণনাযোগ্য ফাংশনগুলি সাধারণ পুনরাবৃত্তিমূলকগুলির সাথে মিলে যায় তা ছিল অ্যালান টুরিংয়ের কাজ। "সাধারণ পুনরাবৃত্তি বা λ-সংজ্ঞাকে কার্যকর গণনার অনানুষ্ঠানিক ধারণার পর্যাপ্ত বৈশিষ্ট্য হিসাবে বিবেচনা করতে গোডেলের অনীহা বেশ কয়েকজন লেখক দ্বারা বিস্তারিতভাবে পরীক্ষা করা হয়েছে [পাদটীকা 248:" "বিশেষ করে ডেভিস 1982 দেখুন; গ্যান্ডি 1980 এবং 1988; সিগ 1994" "]।" একটি ঐকমত্য রয়েছে যে, প্রকৃতপক্ষে, অ্যালান টুরিংয়ের বিশ্লেষণের মতো গোডেল বা চার্চের আনুষ্ঠানিকতা এতটা সুস্পষ্ট বা অন্তর্নিহিতভাবে প্ররোচিত ছিল না এবং উইলফ্রেড সিগ যুক্তি দিয়েছেন যে চার্চের থিসিসের পক্ষে প্রমাণগুলি "বিভিন্ন ধারণার সঙ্গম" দ্বারা সরবরাহ করা হয়েছে (চার্চ, গোডেল, পোস্ট এবং অ্যালান টুরিং দ্বারা প্রস্তাবিত ব্যবস্থাগুলির একই সম্প্রসারণ রয়েছে বলে প্রমাণিত হয়েছে) সাধারণভাবে অনুমিত তুলনায় কম জোরালো। অতএব, গোডেলের সহজাত সতর্কতা ছাড়াও তাঁর সংশয়বাদের যথেষ্ট কারণ ছিল। কিন্তু, সাধারণ পুনরাবৃত্তির ধারণার মাধ্যমে তিনি কী অর্জন করার চেষ্টা করছিলেন? "বরং, গোডেল হারব্র্যান্ডের ধারণাগুলির পরিবর্তনের মাধ্যমে তাঁর সংজ্ঞা [সাধারণ পুনরাবৃত্তিমূলক ক্রিয়াকলাপের শ্রেণী] অর্জন করেছিলেন। এবং উইলফ্রেড সিগ যুক্তি দিয়েছিলেন যে 1934 সালের গবেষণাপত্রের চূড়ান্ত বিভাগে তাঁর আসল উদ্দেশ্য ছিল" "[হারব্র্যান্ডের] জ্ঞানতাত্ত্বিকভাবে সীমাবদ্ধ প্রমাণের ধারণা থেকে পুনরাবৃত্তিমূলক ক্রিয়াকলাপগুলিকে বিচ্ছিন্ন করা" "" "সমীকরণ অর্জনের যান্ত্রিক নিয়মগুলি" "নির্দিষ্ট করে।" সিগ পরামর্শ দেন যে, গোডেলের "সাধারণ" পুনরাবৃত্তির ধারণা সম্পর্কে আরও সাধারণ বিষয় ছিল যে, হারব্র্যান্ডের উদ্দেশ্য ছিল কেবল সেই ফাংশনগুলিকে চিহ্নিত করা যা সীমাবদ্ধ উপায়ে পুনরাবৃত্তিমূলক প্রমাণিত হতে পারে [250]। " প্রিন্সটন ক্লিনে এবং রোসারের গডেলের বক্তৃতাগুলি প্রিন্সটনে গডেলের 1934 সালের বক্তৃতাগুলি প্রতিলিপি করে। তাঁর গবেষণাপত্রে জেনারেল রিকার্সিভ ফাংশনস অফ ন্যাচারাল নাম্বারস ক্লেইন বলেনঃ "প্রাকৃতিক সংখ্যার সাধারণ রিকার্সিভ ফাংশনের একটি সংজ্ঞা হারব্র্যান্ড দ্বারা গোডেলের কাছে প্রস্তাবিত হয়েছিল এবং 1934 সালে প্রিন্সটনে বক্তৃতার একটি সিরিজে একটি গুরুত্বপূর্ণ পরিবর্তনের সাথে গোডেল দ্বারা ব্যবহৃত হয়েছিল।" গোডেলের অর্থে একটি রিকার্সিভ ফাংশন (সম্পর্ক) এখন একটি আদিম রিকার্সিভ ফাংশন (সম্পর্ক) বলা হবে। চার্চের "কার্যকরীভাবে গণনাযোগ্য" গবেষণাপত্রের চার্চের সংজ্ঞা প্রাথমিক সংখ্যা তত্ত্বের একটি অমীমাংসিত সমস্যা (1936) প্রমাণ করে যে λ-ক্যালকুলাস এবং গডেল-হারব্র্যান্ডের সাধারণ পুনরাবৃত্তির মধ্যে এন্টশেইডংসপ্রোবলেম অনিবার্য ছিল; উপরন্তু চার্চ ক্লেইনের দুটি উপপাদ্য উদ্ধৃত করে যা প্রমাণ করে যে λ-ক্যালকুলাসে সংজ্ঞায়িত ফাংশনগুলি সাধারণ পুনরাবৃত্তির দ্বারা সংজ্ঞায়িত ফাংশনের অনুরূপঃ "উপপাদ্য XVI। ধনাত্মক পূর্ণসংখ্যার প্রতিটি পুনরাবৃত্তিমূলক ফাংশন হল λ-definable.16 "উপপাদ্য XVII। ধনাত্মক পূর্ণসংখ্যার প্রতিটি λ-সংজ্ঞায়িত ফাংশন হল recursive.17 "16। এখানকার আকারে এটি প্রথম ক্লেইন দ্বারা প্রাপ্ত হয়েছিল। 17 এই ফলাফলটি বর্তমান লেখক এবং এস. সি. ক্লেইন প্রায় একই সময়ে স্বাধীনভাবে অর্জন করেছিলেন। কাগজটি একটি খুব দীর্ঘ পাদটীকা দিয়ে শুরু হয়, 3। আরেকটি পাদটীকা, 9, আগ্রহের বিষয়। মার্টিন ডেভিস বলেছেন যে "এই গবেষণাপত্রটি মূলত তার স্পষ্ট বিবৃতির জন্য গুরুত্বপূর্ণ (যেহেতু চার্চের থিসিস নামে পরিচিত) যে একটি সীমাবদ্ধ অ্যালগরিদম দ্বারা যে ফাংশনগুলি গণনা করা যেতে পারে সেগুলি সুনির্দিষ্টভাবে পুনরাবৃত্তিমূলক ফাংশন এবং ফলস্বরূপ একটি স্পষ্ট অমীমাংসিত সমস্যা দেওয়া যেতে পারে": "3 যেমন প্রদর্শিত হবে, কার্যকর গণনার এই সংজ্ঞাটি দুটি সমতুল্য ফর্মের যে কোনও একটিতে বলা যেতে পারে, (1). λ-সংজ্ঞায়িত. 2). পুনরাবৃত্তিমূলক। λ-সংজ্ঞার ধারণাটি বর্তমান লেখক এবং এস. সি. ক্লেইনের যৌথ কারণে, বর্তমান লেখক অ্যানালস অফ ম্যাথমেটিক্স, ভলিউম-এ এর দিকে ধারাবাহিক পদক্ষেপ নিয়েছেন। 34 (1933), পৃ. 863, এবং আমেরিকান জার্নাল অফ ম্যাথমেটিক্সে ক্লেইন, খণ্ড। 57 (1935), পৃ. 219। নীচে §4 অর্থে পুনরাবৃত্তির ধারণাটি যৌথভাবে জ্যাক হারব্র্যান্ড এবং কার্ট গোডেলের কারণে, যেমনটি সেখানে ব্যাখ্যা করা হয়েছে। এবং দুটি ধারণার সমতুল্যতার প্রমাণ প্রধানত ক্লেইনের কারণে, তবে আংশিকভাবে বর্তমান লেখক এবং জে। বি. রোসার... কার্যকর গণনার স্বজ্ঞাত ধারণার সাথে এই ধারণাগুলি চিহ্নিত করার প্রস্তাবটি প্রথমে বর্তমান গবেষণাপত্রে তৈরি করা হয়েছে (তবে নীচের § 7-এর প্রথম পাদটীকাটি দেখুন)। "ক্লেইনের (আমেরিকান জার্নাল অফ ম্যাথমেটিক্স, 1935) পদ্ধতির সাহায্যে, বর্তমান গবেষণাপত্রের বিবেচনাগুলি, তুলনামূলকভাবে সামান্য পরিবর্তন সহ, পুনরাবৃত্তির ধারণাটি ব্যবহার না করে, λ-সংজ্ঞার পরিপ্রেক্ষিতে সম্পূর্ণরূপে পরিচালিত হতে পারে। অন্যদিকে, যেহেতু বর্তমান গবেষণাপত্রের ফলাফল পাওয়া গেছে, ক্লিনের দ্বারা এটি দেখানো হয়েছে (তাঁর আসন্ন গবেষণাপত্রটি দেখুন, "প্রাকৃতিক সংখ্যার সাধারণ পুনরাবৃত্তিমূলক ফাংশন") যে λ-সংজ্ঞা ব্যবহার না করে সম্পূর্ণরূপে পুনরাবৃত্তির পরিপ্রেক্ষিতে অনুরূপ ফলাফল পাওয়া যেতে পারে। যাইহোক, কার্যকরী গণনার দুটি ব্যাপকভাবে ভিন্ন এবং (লেখকের মতে) সমানভাবে প্রাকৃতিক সংজ্ঞা সমতুল্য বলে প্রমাণিত হওয়ার বিষয়টি বিশ্বাস করার জন্য নীচে যুক্ত কারণগুলির শক্তিকে যুক্ত করে যে তারা এই ধারণার একটি সাধারণ বৈশিষ্ট্য হিসাবে গঠন করে যা এটির স্বাভাবিক স্বজ্ঞাত বোঝার সাথে সামঞ্জস্যপূর্ণ। পাদটীকা 9 অনুচ্ছেদে 4 পুনরাবৃত্তিমূলক ফাংশন রয়েছেঃ "9 এই সংজ্ঞাটি [" পুনরাবৃত্তিমূলক "] পুনরাবৃত্তিমূলক ফাংশনের একটি সংজ্ঞার সাথে ঘনিষ্ঠভাবে সম্পর্কিত এবং এটি দ্বারা প্রস্তাবিত হয়েছিল যা কার্ট গোডেল, প্রিন্সটন, এনজে, 1934-এর বক্তৃতায় প্রস্তাব করেছিলেন এবং জ্যাক হারব্র্যান্ডের একটি অপ্রকাশিত পরামর্শের অংশ হিসাবে তাঁর দ্বারা কৃতিত্ব দেওয়া হয়েছিল। যে প্রধান বৈশিষ্ট্যগুলিতে পুনরাবৃত্তির বর্তমান সংজ্ঞা গডেলের থেকে আলাদা তা এস. সি. ক্লেইনের কারণে। "স্বাভাবিক সংখ্যার সাধারণ পুনরাবৃত্তিমূলক ফাংশন" শিরোনামে ক্লেইনের একটি আসন্ন গবেষণাপত্রে বলা হয়েছে যে, বর্তমান অর্থে পুনরাবৃত্তিমূলক প্রতিটি ফাংশন গডেল (1934) অর্থে পুনরাবৃত্তিমূলক এবং বিপরীতভাবে। চার্চের গবেষণাপত্র অ্যান আনসোলভেবল প্রবলেম অফ এলিমেন্টারি নম্বর থিওরি (1936)-এর কিছু সময় আগে গোডেল এবং চার্চের মধ্যে একটি কথোপকথন হয়েছিল যে "অ্যালগরিদম" এবং "কার্যকর গণনাযোগ্যতা" ধারণার সংজ্ঞার জন্য λ-সংজ্ঞা যথেষ্ট ছিল কি না। চার্চে (1936) আমরা দেখি, §7 অধ্যায়ের অধীনে কার্যকর গণনার ধারণা, একটি পাদটীকা 18 যা নিম্নলিখিতটি উল্লেখ করেঃ "18 কার্যকর গণনাযোগ্যতা এবং পুনরাবৃত্তির মধ্যে সম্পর্কের প্রশ্ন (যা এখানে দুটি ধারণা চিহ্নিত করে উত্তর দেওয়ার প্রস্তাব করা হয়েছে) লেখকের সাথে কথোপকথনে গোডেল উত্থাপন করেছিলেন। কার্যকর গণনাযোগ্যতা এবং λ-সংজ্ঞায়িততার মধ্যে সম্পর্কের সংশ্লিষ্ট প্রশ্নটি পূর্বে লেখক স্বাধীনভাবে প্রস্তাব করেছিলেন। "চার্চকে চিহ্নিত করার অর্থ হল-" "পরিচয় প্রতিষ্ঠা করা" "নয়-বরং" "অভিন্ন হওয়া বা হয়ে ওঠা", "" "ঐক্যবদ্ধ হিসাবে ধারণা করা" "(আত্মা, দৃষ্টিভঙ্গি বা নীতির মতো) (vt রূপ), এবং (vi রূপ)" "একই হওয়া বা হওয়া" "।" "প্রাকৃতিক আইন" হিসাবে পোস্ট এবং "কার্যকর গণনাযোগ্যতা" পুনরাবৃত্তি "কার্যকর গণনাযোগ্যতার" পর্যাপ্ত সংজ্ঞা কিনা এবং চার্চের গবেষণাপত্র প্রকাশের বিষয়ে পোস্টের সন্দেহ, 1936 সালের শরত্কালে তাকে "মনস্তাত্ত্বিক বিশ্বস্ততা" সহ একটি "সূত্র" প্রস্তাব করতে উত্সাহিত করেছিলঃ একজন কর্মী প্রতিটি বাক্সের কাগজের শীটে মেশিনের মতো "আদিম কাজ" সম্পাদন করে "স্থান বা বাক্সের একটি ক্রম" দিয়ে চলে যায়। শ্রমিকটি "একটি নির্দিষ্ট অপরিবর্তনীয় দিকনির্দেশনা" দিয়ে সজ্জিত। প্রতিটি নির্দেশে তিনটি বা চারটি চিহ্ন থাকেঃ (1) একটি চিহ্নিতকরণ লেবেল/সংখ্যা, (2) একটি অপারেশন, (3) পরবর্তী নির্দেশ জি; তবে, যদি নির্দেশটি টাইপের হয় (ই) এবং নির্ধারণ "হ্যাঁ" হয় তবে নির্দেশ জি 'অন্যথায় যদি এটি "না" নির্দেশ হয়। "আদিম কাজগুলি" 5টির মধ্যে মাত্র 1 প্রকারের হয়ঃ (ক) যে বাক্সে কাগজটি রয়েছে তাতে কাগজটিকে চিহ্নিত করুন (বা ইতিমধ্যে সেখানে থাকা একটি চিহ্নকে অতিরিক্ত চিহ্নিত করুন), (খ) চিহ্নটি মুছে দিন (বা অতিরিক্ত মুছে দিন), (গ) একটি ঘরকে ডানদিকে সরান, (ঘ) একটি ঘরকে বাম দিকে সরান, (ঙ) কাগজটি চিহ্নিত বা ফাঁকা কিনা তা নির্ধারণ করুন। কর্মী প্রারম্ভিক কক্ষের প্রথম ধাপ থেকে শুরু করে এবং নির্দেশাবলী তাদের যা করতে নির্দেশ করে তা করে। (পোস্ট-টুরিং মেশিনে আরও দেখুন।) "স্বজ্ঞাত তত্ত্ব" সম্পর্কে ভূমিকায় উল্লিখিত এই বিষয়টি পোস্টকে চার্চের উপর একটি শক্তিশালী আঘাত হানতে বাধ্য করেছিলঃ "লেখক আশা করেন যে বর্তমান সূত্রটি গডেল-চার্চ development.7 এর অর্থে যৌক্তিকভাবে পুনরাবৃত্তির সমতুল্য হয়ে উঠবে, তবে এর উদ্দেশ্য কেবল একটি নির্দিষ্ট যৌক্তিক শক্তির ব্যবস্থা উপস্থাপন করা নয়, এর সীমাবদ্ধ ক্ষেত্রে মনস্তাত্ত্বিক বিশ্বস্ততাও উপস্থাপন করা। পরবর্তী অর্থে বৃহত্তর এবং বৃহত্তর গঠনগুলি বিবেচনা করা হয়। অন্যদিকে, আমাদের লক্ষ্য হবে এটি দেখানো যে এই সমস্তগুলি সূত্র 1-এর জন্য যৌক্তিকভাবে হ্রাসযোগ্য। আমরা বর্তমান মুহুর্তে একটি কার্যকরী অনুমান হিসাবে এই উপসংহারটি উপস্থাপন করি। এবং আমাদের মনে এই হল চার্চের কার্যকর গণনার শনাক্তকরণ recursiveness.8 "(মূল ইটালিক) 7 [তিনি একটি প্রমাণের পদ্ধতির স্কেচ করেন] 8" সিএফ। চার্চ, তালা। সিট, পিপি। 346, 356-358। প্রকৃতপক্ষে চার্চ এবং অন্যান্যদের দ্বারা ইতিমধ্যে করা কাজটি এই সনাক্তকরণকে কার্যকরী অনুমান পর্যায়ের বাইরেও বহন করে। কিন্তু একটি সংজ্ঞার অধীনে এই শনাক্তকরণকে আড়াল করার জন্য এই সত্যটি লুকিয়ে রাখা হয়েছে যে হোমো সেপিয়েন্সের গাণিতিক শক্তির সীমাবদ্ধতার মধ্যে একটি মৌলিক আবিষ্কার করা হয়েছে এবং এর ক্রমাগত যাচাইয়ের প্রয়োজনীয়তার প্রতি আমাদের অন্ধ করে দিয়েছে। অন্য কথায় পোস্ট বলছে, "আপনি এটিকে সংজ্ঞায়িত করেছেন বলেই এটি সত্যিকারের নয়; আপনার সংজ্ঞা একটি অন্তর্দৃষ্টি ছাড়া আর কিছুর উপর ভিত্তি করে নয়।" পোস্ট একটি সংজ্ঞার চেয়েও বেশি কিছু খুঁজছিলঃ "উপরের প্রোগ্রামটির সাফল্য, আমাদের কাছে, এই অনুমানটিকে কোনও সংজ্ঞা বা স্বতঃসিদ্ধিতে নয়, বরং একটি প্রাকৃতিক নিয়মে পরিবর্তন করবে। লেখকের কাছে তাই মনে হয়, গোডেলের উপপাদ্য এবং চার্চের ফলাফলগুলি সমস্ত প্রতীকী যুক্তি এবং সমাধানযোগ্যতার সমস্ত পদ্ধতি সম্পর্কিত সিদ্ধান্তে রূপান্তরিত হতে পারে। এই বিতর্কিত অবস্থানটি অ্যালান টুরিং 1939-এ ক্রুদ্ধ অভিব্যক্তি খুঁজে পায় এবং এটি গোডেল, গ্যান্ডি এবং সিগের সাথে আবার উপস্থিত হবে। টুরিং এবং গণনাযোগ্যতা এ. এম. টুরিংয়ের গবেষণাপত্র অন কম্পিউটাবল নাম্বারস, উইথ অ্যান অ্যাপ্লিকেশন টু দ্য এন্টশেইডংসপ্রোবলেম 1936 সালের নভেম্বরে লন্ডন ম্যাথমেটিকাল সোসাইটিতে সরবরাহ করা হয়। আবার পাঠককে অবশ্যই একটি সতর্কতার কথা মনে রাখতে হবেঃ যেমন টুরিং ব্যবহার করেছেন, "কম্পিউটার" শব্দটি একজন মানুষ, এবং একটি "কম্পিউটার"-এর ক্রিয়াকে তিনি "কম্পিউটিং" বলে অভিহিত করেছেন; উদাহরণস্বরূপ, তিনি বলেছেন "কম্পিউটিং সাধারণত কাগজে নির্দিষ্ট কিছু চিহ্ন লিখে করা হয়" (পৃ. 135)। কিন্তু তিনি তাঁর যন্ত্র-সংজ্ঞার প্রসঙ্গে "গণনা" শব্দটি ব্যবহার করেন এবং তাঁর "গণনাযোগ্য" সংখ্যার সংজ্ঞাটি নিম্নরূপঃ "গণনাযোগ্য" সংখ্যাগুলিকে সংক্ষেপে বাস্তব সংখ্যা হিসাবে বর্ণনা করা যেতে পারে যার দশমিক হিসাবে অভিব্যক্তিগুলি সীমাবদ্ধ উপায়ে গণনা করা যায়। আমার সংজ্ঞা অনুসারে, একটি সংখ্যা গণনাযোগ্য যদি তার দশমিক একটি মেশিন দ্বারা লেখা যায়। " টুরিং-এর "যন্ত্র"-এর সংজ্ঞা কী? টুরিং দুটি সংজ্ঞা দিয়েছেন, প্রথমটি §1 কম্পিউটিং মেশিনে একটি সারসংক্ষেপ এবং অন্যটি §9-এ খুব অনুরূপ। তাঁর সংজ্ঞা §1 সম্পর্কে তিনি বলেছেন যে "ন্যায্যতা এই সত্যের মধ্যে নিহিত যে মানুষের স্মৃতি অপরিহার্যভাবে সীমিত", এবং তিনি "সমস্ত" শব্দটি ব্যবহার করে তাঁর প্রস্তাবিত যন্ত্রের টাক দাবি সহ §1 শেষ করেছেন "এটি আমার যুক্তি যে এই ক্রিয়াকলাপগুলি [টেপ-বর্গের উপর প্রতীক লিখুন, প্রতীক মুছে ফেলুন, এক বর্গ বাম দিকে সরান, এক বর্গ ডানদিকে সরান, প্রতীকের জন্য বর্গ স্ক্যান করুন এবং একটি স্ক্যান করা প্রতীকের ফলস্বরূপ মেশিন-কনফিগারেশন পরিবর্তন করুন] একটি সংখ্যার গণনায় ব্যবহৃত সমস্ত কিছু অন্তর্ভুক্ত করে।" উপরের বন্ধনীতে এক শব্দের উপর জোর দেওয়া ইচ্ছাকৃত। §9. I সম্পর্কে তিনি যন্ত্রটিকে আরও বর্গ পরীক্ষা করার অনুমতি দেন; এটি এই আরও বর্গাকার আচরণ যা তিনি দাবি করেন যে একটি কম্পিউটারের (ব্যক্তির) ক্রিয়াগুলিকে চিহ্নিত করেঃ "যন্ত্রটি কম্পিউটার দ্বারা পর্যবেক্ষণ করা বি বর্গগুলির সাথে সামঞ্জস্যপূর্ণ বি বর্গগুলি স্ক্যান করে। যে কোনও পদক্ষেপে যন্ত্রটি স্ক্যান করা বর্গক্ষেত্রের একটি প্রতীক পরিবর্তন করতে পারে বা স্ক্যান করা বর্গক্ষেত্রের যে কোনও একটিকে অন্য বর্গক্ষেত্রে পরিবর্তন করতে পারে যা অন্য স্ক্যান করা বর্গক্ষেত্রের একটির থেকে এল বর্গক্ষেত্রের বেশি দূরে নয়। এইমাত্র বর্ণিত যন্ত্রগুলি §2 [sic]-এ সংজ্ঞায়িত কম্পিউটিং মেশিনগুলির থেকে খুব বেশি আলাদা নয় এবং এই ধরনের যে কোনও মেশিনের সাথে সামঞ্জস্য রেখে একটি কম্পিউটিং মেশিন একই ক্রম গণনা করার জন্য তৈরি করা যেতে পারে, অর্থাৎ কম্পিউটার দ্বারা গণনা করা ক্রম। টুরিং ধারা 2-এ একটি "কম্পিউটিং মেশিন"-কে সংজ্ঞায়িত করেছেন (i) "এ-মেশিন" ("স্বয়ংক্রিয় মেশিন") যা ধারা 1-এ অতিরিক্ত বিধিনিষেধের সাথে সংজ্ঞায়িত করা হয়েছে (ii): (ii) এটি দুই ধরনের প্রতীক মুদ্রণ করে-চিত্র 0 এবং 1-এবং অন্যান্য প্রতীক। 0 এবং 1 সংখ্যাগুলি "মেশিন দ্বারা গণনা করা ক্রম" উপস্থাপন করবে। উপরন্তু, সংখ্যাটিকে "গণনাযোগ্য" হিসাবে বিবেচনা করতে হলে, যন্ত্রটিকে অবশ্যই 0 এবং 1 এর একটি অসীম সংখ্যা মুদ্রণ করতে হবে; যদি না হয় তবে এটি "বৃত্তাকার" হিসাবে বিবেচিত হয়; অন্যথায় এটি "বৃত্ত-মুক্ত" হিসাবে বিবেচিত হয়ঃ "একটি সংখ্যা গণনাযোগ্য যদি এটি একটি বৃত্ত-মুক্ত যন্ত্র দ্বারা গণনা করা সংখ্যা থেকে একটি পূর্ণসংখ্যা দ্বারা পৃথক হয়"। যদিও তিনি এটিকে তাঁর "থিসিস" বলেন না, টুরিং একটি প্রমাণ প্রস্তাব করেন যে তাঁর "গণনাযোগ্যতা" চার্চের "কার্যকর গণনাযোগ্যতার" সমতুল্যঃ "সাম্প্রতিক এক গবেষণাপত্রে অ্যালনজো চার্চ" কার্যকর গণনাযোগ্যতার "একটি ধারণা প্রবর্তন করেছেন, যা আমার" গণনাযোগ্যতার "সমতুল্য, তবে এটি খুব আলাদাভাবে সংজ্ঞায়িত। "গণনাযোগ্যতা" এবং "কার্যকর গণনাযোগ্যতা"-র মধ্যে সমতুল্যতার প্রমাণ বর্তমান কাগজের একটি পরিশিষ্টে বর্ণিত হয়েছে। পরিশিষ্টঃ গণনাযোগ্যতা এবং কার্যকর গণনাযোগ্যতা নিম্নলিখিত পদ্ধতিতে শুরু হয়; লক্ষ্য করুন যে তিনি এখানে পুনরাবৃত্তির কথা উল্লেখ করেন না, এবং প্রকৃতপক্ষে তাঁর প্রুফ-স্কেচে তাঁর যন্ত্রের λ-ক্যালকুলাস এবং ক্যালকুলাস তাঁর যন্ত্রের "সম্পূর্ণ কনফিগারেশন"-এ চিহ্নগুলির স্ট্রিং রয়েছে এবং কোথাও পুনরাবৃত্তির উল্লেখ নেই। যন্ত্র-গণনাযোগ্যতা এবং পুনরাবৃত্তির সমতুল্যতার প্রমাণ অবশ্যই ক্লেইন 1943 এবং 1952-এর জন্য অপেক্ষা করতে হবেঃ "এই উপপাদ্য যে সমস্ত কার্যকরভাবে গণনাযোগ্য (λ-সংজ্ঞায়িত) ক্রমগুলি গণনাযোগ্য এবং এর বিপরীত রূপরেখা নীচে প্রমাণিত হয়েছে।" গ্যান্ডি (1960) এই সাহসী প্রুফ-স্কেচটিকে চার্চের থিসিসের সাথে বিভ্রান্ত করেছে বলে মনে হয়; নীচে 1960 এবং 1995 দেখুন। উপরন্তু টুরিংয়ের সংজ্ঞাগুলি যত্ন সহকারে পড়ার ফলে পাঠক লক্ষ্য করেন যে টুরিং জোর দিয়ে বলছিলেন যে §1-এ তাঁর প্রস্তাবিত যন্ত্রের "ক্রিয়াকলাপ" যে কোনও গণনাযোগ্য সংখ্যা গণনা করার জন্য যথেষ্ট, এবং যে যন্ত্রটি §9-এ উপস্থাপিত মানুষের "কম্পিউটার"-এর ক্রিয়াকে অনুকরণ করে। 1939 সালে টুরিং এই বিষয়টির পুনরাবৃত্তি করবেন। টুরিং মেশিন গণনার মাধ্যমে কার্যকর গণনাযোগ্যতা চিহ্নিত করেন অ্যালান টুরিংয়ের বিশাল প্রিন্সটন পিএইচডি থিসিস (অ্যালনজো চার্চের অধীনে) সিস্টেমস অফ লজিক বেসড অন অর্ডিনালস হিসাবে উপস্থিত হয়। এতে তিনি "কার্যকরভাবে গণনাযোগ্য"-এর সংজ্ঞার অনুসন্ধানের সারসংক্ষেপ করেছেন। তিনি বোল্ডফেসের ধরণে দেখানো একটি সংজ্ঞা প্রস্তাব করেন যা "মেশিন গণনা" এবং "কার্যকরভাবে গণনাযোগ্য" ধারণাগুলিকে বিশেষভাবে চিহ্নিত করে (অভিন্ন রেন্ডার করে)। "একটি ফাংশনকে" "কার্যকরভাবে গণনাযোগ্য" "বলা হয় যদি এর মানগুলি কোনও বিশুদ্ধ যান্ত্রিক প্রক্রিয়া দ্বারা খুঁজে পাওয়া যায়।" যদিও এই ধারণাটি স্বজ্ঞাতভাবে উপলব্ধি করা মোটামুটি সহজ, তবুও আরও নির্দিষ্ট, গাণিতিকভাবে সুস্পষ্ট সংজ্ঞা থাকা বাঞ্ছনীয়। 1934 সালে প্রিন্সটনে গোডেল প্রথম এই ধরনের সংজ্ঞা দিয়েছিলেন। গোডেল এই ফাংশনগুলিকে "সাধারণ পুনরাবৃত্তিমূলক" হিসাবে বর্ণনা করেছেন। চার্চ কার্যকর গণনার আরেকটি সংজ্ঞা দিয়েছে। চার্চ এটিকে λ-সংজ্ঞার সাথে চিহ্নিত করে। লেখক সম্প্রতি স্বজ্ঞাত ধারণার সাথে আরও ঘনিষ্ঠভাবে সম্পর্কিত একটি সংজ্ঞা প্রস্তাব করেছেন (টুরিং [1], পোস্টের [1] দেখুন)। উপরে বলা হয়েছে যে "কোনও ফাংশন কার্যকরভাবে গণনাযোগ্য যদি তার মানগুলি কোনও বিশুদ্ধ যান্ত্রিক প্রক্রিয়া দ্বারা খুঁজে পাওয়া যায়"। আমরা এই বিবৃতিটি আক্ষরিক অর্থে নিতে পারি, একটি বিশুদ্ধ যান্ত্রিক প্রক্রিয়া দ্বারা বোঝা যা একটি মেশিন দ্বারা পরিচালিত হতে পারে। এই যন্ত্রগুলির কাঠামোর একটি নির্দিষ্ট স্বাভাবিক আকারে গাণিতিক বিবরণ দেওয়া সম্ভব। এই ধারণাগুলির বিকাশ লেখকের একটি গণনাযোগ্য ফাংশনের সংজ্ঞা এবং কার্যকর গণনার সাথে গণনাযোগ্যতার একটি সনাক্তকরণের দিকে পরিচালিত করে। এই তিনটি সংজ্ঞা সমতুল্য প্রমাণ করা কঠিন নয়, যদিও কিছুটা শ্রমসাধ্য। "আমরা" গণনাযোগ্য ফাংশন "অভিব্যক্তিটি ব্যবহার করব একটি মেশিন দ্বারা গণনাযোগ্য একটি ফাংশন বোঝাতে, এবং আমরা" কার্যকরভাবে গণনাযোগ্য "এই সংজ্ঞাগুলির কোনও একটির সাথে নির্দিষ্ট সনাক্তকরণ ছাড়াই স্বজ্ঞাত ধারণাকে বোঝাতে পারি। আমরা একটি গণনাযোগ্য ফাংশন দ্বারা গৃহীত মানগুলিকে প্রাকৃতিক সংখ্যা হিসাবে সীমাবদ্ধ করি না; উদাহরণস্বরূপ আমাদের গণনাযোগ্য প্রস্তাবমূলক ফাংশন থাকতে পারে। এটি একটি শক্তিশালী অভিব্যক্তি। কারণ "অভিন্নতা" আসলে প্রয়োজনীয় এবং পর্যাপ্ত অবস্থার একটি দ্ব্যর্থহীন বিবৃতি, অন্য কথায় "ফাংশন", "মেশিন", "গণনাযোগ্য" এবং "কার্যকরভাবে গণনাযোগ্য" শব্দগুলির কী ব্যাখ্যা দেওয়া হয়েছে তা ছাড়া "সনাক্তকরণের জন্য অন্য কোনও আকস্মিকতা নেইঃ সমস্ত ফাংশনের জন্যঃ" যদি এই ফাংশনটি মেশিন দ্বারা গণনাযোগ্য হয় "তবে" এই ফাংশনটি কার্যকরভাবে গণনাযোগ্য "এবং যদি" এই ফাংশনটি কার্যকরভাবে গণনাযোগ্য হয় "তারপর" এই ফাংশনটি একটি মেশিন দ্বারা গণনাযোগ্য। রসারঃ রিকার্সন, λ-ক্যালকুলাস, এবং টুরিং-মেশিন গণনা পরিচয় জে। বি. রোসারের গবেষণাপত্র অ্যান ইনফরমাল এক্সপোজিশন অফ প্রুফস অফ গডেলের উপপাদ্য এবং চার্চের উপপাদ্য নিম্নরূপ বলেঃ "'কার্যকরী পদ্ধতি' এখানে একটি পদ্ধতির পরিবর্তে বিশেষ অর্থে ব্যবহৃত হয় যার প্রতিটি ধাপ সুনির্দিষ্টভাবে পূর্বনির্ধারিত এবং যা একটি সীমাবদ্ধ সংখ্যক ধাপে উত্তর তৈরি করতে নিশ্চিত। এই বিশেষ অর্থ সহ, তারিখ 5 পর্যন্ত তিনটি ভিন্ন সুনির্দিষ্ট সংজ্ঞা দেওয়া হয়েছে। এগুলির মধ্যে সবচেয়ে সহজভাবে বলা যায় (পোস্ট এবং টুরিংয়ের কারণে) মূলত বলে যে একটি নির্দিষ্ট সমস্যা সমাধানের একটি কার্যকর পদ্ধতি বিদ্যমান যদি কেউ এমন একটি যন্ত্র তৈরি করতে পারে যা প্রশ্নটি সন্নিবেশ করা এবং (পরে) উত্তরটি পড়ার বাইরে কোনও মানুষের হস্তক্ষেপ ছাড়াই সেটের যে কোনও সমস্যা সমাধান করবে। তিনটি সংজ্ঞাই সমতুল্য, তাই কোনটি ব্যবহার করা হয়েছে তা বিবেচ্য নয়। উপরন্তু, এই তিনটিই সমতুল্য যে কোনও একটির সঠিকতার পক্ষে একটি খুব শক্তিশালী যুক্তি। 5 একটি সংজ্ঞা চার্চ দ্বারা দেওয়া হয়েছে I [অর্থাৎ। চার্চ 1936 প্রাথমিক সংখ্যা তত্ত্বের একটি অমীমাংসিত সমস্যা]। আরেকটি সংজ্ঞা জ্যাক হারব্র্যান্ড এবং কার্ট গোডেলের কারণে। এটি I, পাদটীকা 3, পৃ. 346-এ উল্লেখ করা হয়েছে। তৃতীয় সংজ্ঞাটি স্বাধীনভাবে দুটি সামান্য ভিন্ন রূপে ই. এল. পোস্ট এবং এ. এম. টুরিং দ্বারা দেওয়া হয়েছিল। প্রথম দুটি সংজ্ঞা I-তে সমতুল্য প্রমাণিত হয়েছে। তৃতীয়টি প্রথম দুটির সমতুল্য প্রমাণিত হয়েছে এ. এম. টুরিং, গণনাযোগ্যতা এবং λ-সংজ্ঞা [জার্নাল অফ সিম্বলিক লজিক, ভলিউম। 2 (1937), পৃ. 153-163] "। ক্লেইন এবং থিসিস আই ক্লেইন তাঁর গবেষণাপত্রে "সাধারণ পুনরাবৃত্তিমূলক" ফাংশন এবং "আংশিক পুনরাবৃত্তিমূলক ফাংশন" সংজ্ঞায়িত করেছেন। প্রতিনিধিত্বকারী ফাংশন, মিউ-অপারেটর ইত্যাদি তাদের চেহারা তৈরি করে। তিনি §12 অ্যালগরিদম তত্ত্বগুলিতে তাঁর বিখ্যাত থিসিস I উল্লেখ করেছেন, যা তিনি 1952 সালে চার্চের থিসিস বলতে এসেছিলেনঃ "এই অনুসন্ধানমূলক সত্য, সেইসাথে প্রতীকী অ্যালগরিদম প্রক্রিয়াগুলির প্রকৃতির উপর কিছু প্রতিফলন, চার্চকে নিম্নলিখিত থিসিসটি বর্ণনা করতে পরিচালিত করেছিল। একই থিসিসটি টুরিংয়ের কম্পিউটিং মেশিনের বর্ণনায় অন্তর্নিহিতভাবে রয়েছে। "থিসিস আই। প্রতিটি কার্যকরভাবে গণনাযোগ্য ফাংশন (কার্যকরভাবে নির্ণায়ক ভবিষ্যদ্বাণী) সাধারণ পুনরাবৃত্তিমূলক। "যেহেতু কার্যকরভাবে গণনাযোগ্য (কার্যকরীভাবে নির্ণায়ক) শব্দটির একটি সুনির্দিষ্ট গাণিতিক সংজ্ঞা চাওয়া হচ্ছে, তাই আমরা এই থিসিসটিকে তার সংজ্ঞা হিসাবে গ্রহণ করতে পারি, যা ইতিমধ্যে গৃহীত নীতির সাথে এটি বিপরীত। থিসিসটির একটি অনুমানের চরিত্র রয়েছে-পোস্ট এবং চার্চ 24 দ্বারা জোর দেওয়া একটি বিন্দু। 22 চার্চ [1] [প্রাথমিক সংখ্যা তত্ত্বের একটি অমীমাংসিত সমস্যা] 23 টুরিং [1] [গণনাযোগ্য সংখ্যার উপর, এন্টশেইডংসপ্রবলেমের (1936) একটি প্রয়োগ সহ] 24 পোস্ট [1, পৃ. 105], এবং চার্চ [2] ক্লেইনের চার্চ, টুরিং এবং চার্চ-টুরিং থিসিস তাঁর § 60 অধ্যায়ে, ক্লেইন "চার্চের থিসিস" কে নিম্নরূপ সংজ্ঞায়িত করেছেনঃ ". অনুসন্ধানমূলক প্রমাণ এবং অন্যান্য বিবেচনার কারণে চার্চ 1936 নিম্নলিখিত থিসিসটি প্রস্তাব করেছিল। "থিসিস আই। প্রতিটি কার্যকরভাবে গণনাযোগ্য ফাংশন (কার্যকরভাবে নির্ণায়ক ভবিষ্যদ্বাণী) সাধারণ পুনরাবৃত্তিমূলক। এই থিসিসটি টুরিং 1936-7 এবং 1936-এর পরে প্রণীত একটি কম্পিউটিং মেশিনের ধারণার মধ্যেও অন্তর্নিহিত। 317 পৃষ্ঠায় তিনি স্পষ্টভাবে উপরের থিসিসটিকে "চার্চের থিসিস" বলে অভিহিত করেছেনঃ "§62। চার্চের থিসিস। এই এবং পরবর্তী অধ্যায়ের অন্যতম প্রধান উদ্দেশ্য হল চার্চের থিসিসের (থিসিস 1 § 60) প্রমাণ উপস্থাপন করা। টুরিংয়ের "গঠন" সম্পর্কে ক্লেইন বলেনঃ "টুরিংয়ের গঠন তাই চার্চের থিসিসের (সমতুল্য ভাষায়) একটি স্বাধীন বিবৃতি গঠন করে। 1936-এর পরেও একই ধরনের সূত্র দেওয়া হয়েছিল। ক্লেইন প্রস্তাব করেন যে টুরিং যা দেখিয়েছেনঃ "টুরিংয়ের গণনাযোগ্য ফাংশনগুলি (1936-1937) এমন একটি মেশিন দ্বারা গণনা করা যেতে পারে যা তার বিশ্লেষণ অনুসারে, একটি মানব কম্পিউটার পূর্বনির্ধারিত নির্দেশাবলী অনুসারে কাজ করতে পারে এমন সমস্ত ধরণের ক্রিয়াকলাপ পুনরুত্পাদন করার জন্য ডিজাইন করা হয়েছে।" ক্লেইন টুরিংয়ের থিসিসকে নিম্নরূপ সংজ্ঞায়িত করেছেনঃ "§70। টুরিংয়ের থিসিস। টুরিংয়ের থিসিস যে প্রতিটি ফাংশন যা স্বাভাবিকভাবেই তাঁর সংজ্ঞার অধীনে গণনাযোগ্য হিসাবে বিবেচিত হবে, অর্থাৎ তাঁর একটি যন্ত্র দ্বারা, তত্ত্ব XXX দ্বারা চার্চের থিসিসের সমতুল্য। প্রকৃতপক্ষে এই বিবৃতির ঠিক আগে, ক্লেইন উপপাদ্য XXX উল্লেখ করেছেনঃ "উপপাদ্য XXX (= উপপাদ্য XXVIII + XXIX)। আংশিক ফাংশনের নিম্নলিখিত শ্রেণীগুলি সহবিস্তৃত, অর্থাৎ। তাদের একই সদস্য রয়েছেঃ (ক) আংশিক পুনরাবৃত্তিমূলক ফাংশন, (খ) গণনাযোগ্য ফাংশন, (গ) 1/1 গণনাযোগ্য ফাংশন। একইভাবে l [ছোট হাতের L]-এর সাথে সম্পূর্ণরূপে সংজ্ঞায়িত অনুমিত ফাংশন ম্বা "। গোডেল, টুরিং মেশিন, এবং কার্যকরীভাবে গণনাযোগ্যতা তাঁর 1931 সালের গবেষণাপত্রে অন ফর্মালি আনডিসিডিবল প্রপোসিশনস-এ, গোডেল একটি নোট যোগ করেছেন যা 28 আগস্ট 1963 যোগ করা হয়েছে যা "একটি আনুষ্ঠানিক ব্যবস্থার" বিকল্প রূপ/অভিব্যক্তি সম্পর্কে তাঁর মতামতকে স্পষ্ট করে। 1964 সালে তিনি আরও স্পষ্টভাবে তাঁর মতামত পুনর্ব্যক্ত করেন (নীচে দেখুন): "নোট 28 আগস্ট 1963 যোগ করা হয়েছে। পরবর্তী অগ্রগতির ফলস্বরূপ, বিশেষত এ. এম. টুরিংয়ের কাজ 69-এর কারণে আনুষ্ঠানিক পদ্ধতি 70-এর সাধারণ ধারণার একটি সুনির্দিষ্ট এবং নিঃসন্দেহে পর্যাপ্ত সংজ্ঞা দেওয়া যেতে পারে, উপপাদ্য 6 এবং 11-এর একটি সম্পূর্ণ সাধারণ সংস্করণ এখন সম্ভব। অর্থাৎ, এটি কঠোরভাবে প্রমাণ করা যেতে পারে যে প্রতিটি সামঞ্জস্যপূর্ণ আনুষ্ঠানিক ব্যবস্থায় যেখানে একটি নির্দিষ্ট পরিমাণের সীমাবদ্ধ সংখ্যা তত্ত্ব রয়েছে সেখানে অনির্বচনীয় গাণিতিক প্রস্তাব রয়েছে এবং উপরন্তু, এই ধরনের কোনও ব্যবস্থার সামঞ্জস্য ব্যবস্থায় প্রমাণ করা যায় না। "69 দেখুন, পৃ. 249। "70 আমার মতে" আনুষ্ঠানিক ব্যবস্থা "বা" আনুষ্ঠানিকতা "শব্দটি এই ধারণা ছাড়া অন্য কোনও কিছুর জন্য ব্যবহার করা উচিত নয়। প্রিন্সটনের একটি বক্তৃতায় (1946 সালে প্রিন্সটন বিশ্ববিদ্যালয়ে উল্লিখিত, পৃ. 11) [ডেভিস 1965, পৃ. দেখুন। 84-88 [অর্থাৎ। ডেভিস পি. 84-88]), আমি আনুষ্ঠানিকতার কিছু ট্রান্সফাইনাইট সাধারণীকরণের পরামর্শ দিয়েছিলাম, তবে এগুলি শব্দটির সঠিক অর্থে আনুষ্ঠানিক ব্যবস্থাগুলির থেকে মৌলিকভাবে আলাদা কিছু, যার বৈশিষ্ট্যগত বৈশিষ্ট্য হল যে তাদের মধ্যে যুক্তি, নীতিগতভাবে, যান্ত্রিক যন্ত্র দ্বারা সম্পূর্ণরূপে প্রতিস্থাপিত হতে পারে। গডেল 1964-প্রিন্সটনের আইএএস-এ 1934 সালের তাঁর বক্তৃতার নোটগুলিতে গডেলের পোস্টস্ক্রিপ্টে তিনি পুনরাবৃত্তি করেছেন, তবে আরও সাহসী ভাষায় পুনরাবৃত্তি করেছেন, চার্চের λ-সংজ্ঞা এবং পুনরাবৃত্তি দ্বারা সংজ্ঞায়িত গণনার কার্যকারিতা সম্পর্কে তাঁর কম-উজ্জ্বল মতামত (আমাদের অনুমান করতে হবে যে নিম্নলিখিতগুলিতে বহুবচন "সংজ্ঞা" ব্যবহারের কারণে উভয়ই অবমাননা করা হয়েছে)। এটি মার্টিন ডেভিসের কাছে লেখা একটি চিঠিতে ছিল (সম্ভবত তিনি দ্য আনডিডিবলকে একত্রিত করছিলেন)। কিছু বাক্যাংশের পুনরাবৃত্তি লক্ষণীয়ঃ "পরবর্তী অগ্রগতির ফলস্বরূপ, বিশেষত এই সত্য যে, এ. এম. টুরিংয়ের কাজের কারণে, আনুষ্ঠানিক ব্যবস্থার সাধারণ ধারণার একটি সুনির্দিষ্ট এবং নিঃসন্দেহে পর্যাপ্ত সংজ্ঞা এখন দেওয়া যেতে পারে, অনির্ধারিত গাণিতিক প্রস্তাবের অস্তিত্ব এবং একই ব্যবস্থায় একটি ব্যবস্থার সামঞ্জস্যের অ-প্রদর্শনযোগ্যতা এখন একটি নির্দিষ্ট পরিমাণের সীমাবদ্ধ সংখ্যা তত্ত্ব ধারণকারী প্রতিটি সামঞ্জস্যপূর্ণ আনুষ্ঠানিক ব্যবস্থার জন্য কঠোরভাবে প্রমাণিত হতে পারে। "টুরিংয়ের কাজ" যান্ত্রিক পদ্ধতি "(উপনাম" অ্যালগরিদম "বা" গণনা পদ্ধতি "বা" সীমাবদ্ধ সমন্বয় পদ্ধতি ") ধারণার একটি বিশ্লেষণ দেয়। এই ধারণাটি "টুরিং মেশিনের" সমতুল্য হিসাবে দেখানো হয়েছে। একটি আনুষ্ঠানিক ব্যবস্থাকে সহজভাবে সূত্র তৈরির জন্য যে কোনও যান্ত্রিক পদ্ধতি হিসাবে সংজ্ঞায়িত করা যেতে পারে, যাকে প্রমাণযোগ্য সূত্র বলা হয়. আনুষ্ঠানিক ব্যবস্থার ধারণা, যার সারমর্ম হল সূত্রগুলির উপর যান্ত্রিক ক্রিয়াকলাপ দ্বারা যুক্তি সম্পূর্ণরূপে প্রতিস্থাপিত হয়। (লক্ষ্য করুন যে কোনও অ্যালগরিদমের সমতুল্য নয় এমন সীমাবদ্ধ অ-যান্ত্রিক পদ্ধতি রয়েছে কিনা এই প্রশ্নের "আনুষ্ঠানিক ব্যবস্থা" এবং "যান্ত্রিক পদ্ধতির" সংজ্ঞার পর্যাপ্ততার সাথে কোনও সম্পর্ক নেই। ". যদি" "সীমাবদ্ধ পদ্ধতি" "মানে" "যান্ত্রিক পদ্ধতি" "বোঝা যায়, তবে পাদটীকা 3-এ উত্থাপিত প্রশ্নের উত্তর §9-এ সংজ্ঞায়িত পুনরাবৃত্তির জন্য ইতিবাচকভাবে দেওয়া যেতে পারে, যা আজকের সংজ্ঞায়িত সাধারণ পুনরাবৃত্তির সমতুল্য (এস. সি. ক্লেইন (1936) দেখুন।)" "* দেখুন। এবং ই. এল. পোস্টের প্রায় একযোগে লেখা কাগজ (1936)।" গণনাযোগ্যতার পূর্ববর্তী সমতুল্য সংজ্ঞাগুলির জন্য, যা আমাদের উদ্দেশ্যের জন্য অনেক কম উপযুক্ত, এ দেখুন। চার্চ 1936। পাদটীকা 3 1934 সালের বক্তৃতার মূল অংশে রয়েছেঃ "3 বিপরীতটি সত্য বলে মনে হয়, যদি পরিকল্পনা অনুসারে পুনরাবৃত্তি ছাড়াও (2) অন্যান্য রূপের পুনরাবৃত্তি (যেমন, একই সাথে দুটি চলকের ক্ষেত্রে) গ্রহণ করা হয়। এটি প্রমাণ করা যায় না, কারণ সীমাবদ্ধ গণনার ধারণাটি সংজ্ঞায়িত করা হয় না, তবে এটি একটি অনুসন্ধানমূলক নীতি হিসাবে কাজ করে। ডেভিস লক্ষ্য করেছেন যে "প্রকৃতপক্ষে তাঁর [গোডেলের] সংজ্ঞা [পুনরাবৃত্তির] এবং ক্লেইনের [1936] মধ্যে সমতা খুব সামান্য নয়। সুতরাং, বিপরীত চেহারা সত্ত্বেও, এই বক্তৃতাগুলির পাদটীকা 3 চার্চের থিসিসের বিবৃতি নয়। গ্যান্ডিঃ "মেশিন গণনা", বিচ্ছিন্ন, নির্ধারক, এবং হালকা গতির দ্বারা "স্থানীয় কার্যকারণ"-এর মধ্যে সীমাবদ্ধ রবিন গ্যান্ডির প্রভাবশালী গবেষণাপত্র চার্চের থিসিস অ্যান্ড প্রিন্সিপলস ফর মেকানিজমস শিরোনামে বারওয়াইজ এট আল-এ প্রকাশিত হয়েছে। গ্যান্ডি চার্চের থিসিসের একটি অপ্রত্যাশিত অভিব্যক্তি দিয়ে শুরু করেন, যা নিম্নরূপঃ "1। ভূমিকা "এই গবেষণাপত্র জুড়ে আমরা কিছু স্বজ্ঞাতভাবে প্রদত্ত ধারণাকে বোঝাতে" গণনাযোগ্য "এবং" গণনাযোগ্য "অর্থ" টুরিং মেশিন দ্বারা গণনাযোগ্য "ব্যবহার করব; অবশ্যই" গণনাযোগ্য "এর অনেক সমতুল্য সংজ্ঞা এখন উপলব্ধ। "চার্চের থিসিস। যা কার্যকরভাবে গণনা করা যায় তা গণনাযোগ্য। । চার্চ এবং টুরিং উভয়েরই মনে কিছু যান্ত্রিক সহায়তা (যেমন কাগজ এবং পেন্সিল) ব্যবহার করে একজন বিমূর্ত মানুষের দ্বারা গণনা করা ছিল "রবার্ট সোয়ারের (1995, নীচে দেখুন) এই ফ্রেমিং নিয়ে সমস্যা ছিল, টুরিংয়ের" পরিশিষ্ট প্রমাণ "(1937) এর আগে প্রকাশিত চার্চের গবেষণাপত্র (1936) বিবেচনা করে। গ্যান্ডি "যান্ত্রিক প্রক্রিয়াগুলি বিশ্লেষণ করার চেষ্টা করেছেন এবং তাই নিম্নলিখিতগুলির জন্য যুক্তি সরবরাহ করার চেষ্টা করেছেনঃ" থিসিস এম। একটি মেশিন দ্বারা যা গণনা করা যেতে পারে তা গণনাযোগ্য। " গ্যান্ডি "বিবেচনামূলক যন্ত্রগুলি থেকে বাদ দেয় যা মূলত অ্যানালগ মেশিন। যান্ত্রিক যন্ত্রগুলি সম্পর্কে তৈরি একমাত্র শারীরিক অনুমানগুলি (নীচের সিএফ নীতি 4) হ 'ল যন্ত্রের প্রতিটি পারমাণবিক অংশের রৈখিক মাত্রায় একটি নিম্ন সীমা রয়েছে এবং পরিবর্তনের প্রসারণের গতিতে একটি উপরের সীমা (আলোর বেগ) রয়েছে।" কিন্তু তারপর তিনি তাঁর যন্ত্রগুলিকে আরও বেশি সীমাবদ্ধ করেনঃ "(2) দ্বিতীয়ত, আমরা ধরে নিই যে একটি যান্ত্রিক যন্ত্র দ্বারা গণনার অগ্রগতিকে পৃথক ভাষায় বর্ণনা করা যেতে পারে, যাতে বিবেচনা করা যন্ত্রগুলি আলগা অর্থে ডিজিটাল কম্পিউটার হয়। (3) সবশেষে আমরা ধরে নিই যে যন্ত্রটি নির্ণায়কঃ অর্থাৎ, যন্ত্রটির প্রাথমিক অবস্থার সম্পূর্ণ বিবরণ দেওয়ার পরে তার পরবর্তী আচরণ অনন্যভাবে নির্ধারিত হয়। প্রকৃতপক্ষে তিনি এই "থিসিস এম"-এর জন্য একটি যুক্তি দেন যে তিনি তাঁর "উপপাদ্য"-কে বলেন, যার মধ্যে সবচেয়ে গুরুত্বপূর্ণ "নীতি" হল "চতুর্থ নীতিঃ স্থানীয় কার্যকারণের নীতি": "এখন আমরা আমাদের নীতিগুলির মধ্যে সবচেয়ে গুরুত্বপূর্ণটিতে আসি। টুরিংয়ের বিশ্লেষণে এই প্রয়োজনীয়তা ছিল যে কর্মটি শুধুমাত্র রেকর্ডের একটি সীমাবদ্ধ অংশের উপর নির্ভরশীল ছিল একটি মানবিক সীমাবদ্ধতার উপর ভিত্তি করে। আমরা এটিকে একটি শারীরিক সীমাবদ্ধতা দ্বারা প্রতিস্থাপন করি যাকে আমরা স্থানীয় কার্যকারণের নীতি বলি। এর যৌক্তিকতা প্রভাব এবং সংকেতের প্রসারণের সীমাবদ্ধ বেগের মধ্যে নিহিতঃ সমসাময়িক পদার্থবিজ্ঞান দূরত্বে তাৎক্ষণিক ক্রিয়ার সম্ভাবনাকে প্রত্যাখ্যান করে। 1985 সালে "থিসিস এম" কোয়ান্টাম টুরিং মেশিনের জন্য অভিযোজিত হয়, যার ফলে একটি চার্চ-টুরিং-ডয়েশ নীতি তৈরি হয়। সোয়ার সোয়ারের গণনাযোগ্যতা এবং পুনরাবৃত্তির পুঙ্খানুপুঙ্খ পরীক্ষা প্রদর্শিত হয়। তিনি গণনাযোগ্যতার "অনেক কম উপযুক্ত" সংজ্ঞার বিষয়ে গোডেলের 1964 সালের মতামত (উপরে) উদ্ধৃত করেছেন এবং যোগ করেছেনঃ "ক্লেইন লিখেছেন [1981বি, পৃ. 49]", টুরিংয়ের গণনাযোগ্যতা অন্তর্নিহিতভাবে প্ররোচিত করে "তবে" λ-সংজ্ঞা অন্তর্নিহিতভাবে প্ররোচিত করে না "এবং" সাধারণ পুনরাবৃত্তিমূলকতা খুব কমই হয় (এর লেখক গোডেল সেই সময়ে মোটেও প্ররোচিত হননি)। বেশিরভাগ মানুষ আজ টুরিংয়ের থিসিস "সোয়ারের পাদটীকা 7 (1995)-এও গ্যান্ডির" বিভ্রান্তি "ধরা পড়ে, তবে স্পষ্টতই এটি গ্যান্ডির (1988) অবধি অব্যাহত রয়েছে। এই বিভ্রান্তি গবেষণা এবং/অথবা চিন্তার একটি গুরুতর ত্রুটির প্রতিনিধিত্ব করে এবং তার পুরো প্রোগ্রামের উপর একটি মেঘ ঝুলে রয়েছেঃ "7গ্যান্ডি আসলে চার্চের থিসিস লিখেছিলেন" এখানে লেখা "টুরিংয়ের থিসিস" নয়, তবে অবশ্যই গ্যান্ডি পরেরটিকে বোঝাতে চেয়েছিলেন, অন্তত ইচ্ছাকৃতভাবে, কারণ টুরিং 1936 সালে বা সাধারণ পুনরাবৃত্তিমূলক ফাংশন সম্পর্কে অন্য কোথাও কিছু প্রমাণ করেননি। " ব্রেগার একটি সমস্যা নির্দেশ করে যখন কেউ "স্বতঃসিদ্ধভাবে" একটি ধারণার কাছে পৌঁছায়, অর্থাৎ, একটি "স্বতঃসিদ্ধ ব্যবস্থা" এতে এক বা একাধিক স্বতঃসিদ্ধ স্বতঃসিদ্ধ অন্তর্ভুক্ত থাকতে পারে যা স্বতঃসিদ্ধ-সেট উপস্থাপনের সময় অব্যক্ত থাকে। উদাহরণস্বরূপ, জ্ঞান (এবং ক্ষমতা) সহ একজন সক্রিয় প্রতিনিধি যে কোনও স্বতঃসিদ্ধ ব্যবস্থায় একটি (সম্ভাব্য) মৌলিক স্বতঃসিদ্ধ হতে পারেঃ "একজন মানুষের জ্ঞান-একটি জ্ঞান-যা স্বতঃসিদ্ধগুলিতে আনুষ্ঠানিক নয়। Â। গণিতকে প্রতীকের একটি বিশুদ্ধ আনুষ্ঠানিক ব্যবস্থা হিসাবে চিহ্নিত করা অসম্ভব। "তিনি হিলবার্টের উদ্ধৃতি দিয়েছেনঃ" 1905 সালে দেওয়া একটি বিশ্ববিদ্যালয় বক্তৃতায়, হিলবার্ট যুক্তিতে স্বতঃসিদ্ধগুলি বর্ণনা করার আগে একটি "চিন্তার স্বতঃসিদ্ধ" বা "বুদ্ধিমত্তার অস্তিত্বের স্বতঃসিদ্ধ" থাকা "একেবারে প্রয়োজনীয়" বলে মনে করেছিলেন। স্ক্রিপ্টের প্রান্তে, হিলবার্ট পরে যোগ করেছেনঃ "দার্শনিকদের একটি অগ্রাধিকার"। তিনি এই স্বতঃসিদ্ধটি নিম্নরূপ প্রণয়ন করেছিলেনঃ "বস্তুর সম্পর্কে চিন্তা করার এবং a, b,.., x, y,.. এর মতো সহজ প্রতীকগুলির মাধ্যমে সেগুলিকে বোঝানোর ক্ষমতা আমার রয়েছে, যাতে সেগুলি দ্ব্যর্থহীনভাবে শনাক্ত করা যায়। আমার চিন্তাভাবনা নির্দিষ্ট নিয়ম অনুসারে এই বস্তুগুলির সাথে একটি নির্দিষ্ট উপায়ে কাজ করে এবং আমার চিন্তাভাবনা নিজের পর্যবেক্ষণের মাধ্যমে এই নিয়মগুলি সনাক্ত করতে সক্ষম হয় এবং এই নিয়মগুলি সম্পূর্ণরূপে বর্ণনা করতে সক্ষম হয় "[(হিলবার্ট 1905,219; আরও দেখুন (পেখাউস 1990,62এফ এবং 227)]। জুসেপ্পে ভেরোনীস (1891) এবং হারমান ওয়েল (1930-1)-এর উদাহরণ দিয়ে ব্রেগার তাঁর যুক্তিকে আরও সমর্থন করেন। তিনি একটি নির্দিষ্ট ভাষায় একটি স্বতঃসিদ্ধ-সেটের প্রকাশের সমস্যা নিয়ে আলোচনা করেনঃ অর্থাৎ। এজেন্ট দ্বারা পরিচিত একটি ভাষা, যেমন। জার্মান। অ্যালগরিদম চরিত্রায়নে এই বিষয়ে আরও দেখুন, বিশেষ করে সিয়ারলের মতামত যে কোনও গণনার বাইরে অবশ্যই একজন পর্যবেক্ষক থাকতে হবে যিনি ব্যবহৃত প্রতীকগুলিকে অর্থ প্রদান করেন। "ফেফারফেস্টে"-সলোমন ফেফারম্যানের 70তম জন্মদিনে-উইলফ্রেড সিগ প্রথম দুই বছর আগে "ক্যালকুলেশনস বাই ম্যান অ্যান্ড মেশিনঃ কনসেপচুয়াল অ্যানালাইসিস" শিরোনামে একটি গবেষণাপত্র উপস্থাপন করেন, যা (সিগ এট আল)-এ পুনরায় মুদ্রিত হয়। 2002:390-409)। এর আগে সিগ "মেকানিক্যাল প্রসিজার্স অ্যান্ড ম্যাথমেটিকাল এক্সপেরিয়েন্স" (জর্জ 1994, পৃ. 71এফএফ) প্রকাশ করেছিলেন যা রিচার্ড ডেডেকিন্ড থেকে শুরু করে 1950-এর দশকে অ্যালান টুরিং এবং স্টিফেন কোল ক্লেইনের পরবর্তী গবেষণাপত্রগুলি দিয়ে "গণনাযোগ্যতার" ইতিহাস উপস্থাপন করে। ফেফারফেস্ট কাগজটি পূর্ববর্তী কাগজটিকে তার প্রধান পয়েন্টগুলিতে ছড়িয়ে দেয় এবং প্রাথমিকভাবে 1980 সালের রবিন গ্যান্ডির কাগজে থাকে। সিগ টুরিংয়ের "স্ট্রিং মেশিন দ্বারা গণনাযোগ্যতা" (মানব "কম্পিউটার") কে গ্যান্ডির সমান্তরাল মেশিনে "লেটার মেশিন দ্বারা গণনাযোগ্যতা" পদ্ধতিতে হ্রাস করে প্রসারিত করে। সিগ "কোলমোগোরভ এবং উসপেনস্কির অ্যালগরিদমের উপর কাজ" এবং (ডি পিসাপিয়া 2000), বিশেষত, কেইউ-পয়েন্টার মেশিন-মডেল সহ আরও সাম্প্রতিক কাজের উদ্ধৃতি দিয়েছেন এবং দাবি করেছেনঃ "অনানুষ্ঠানিক ধারণাগত বিশ্লেষণ এবং গাণিতিক সমতুল্য প্রমাণের পৃথকীকরণ অপরিহার্য যে টুরিংয়ের থিসিসের (সাধারণভাবে নেওয়া) সঠিকতা দুটি স্তম্ভের উপর নির্ভর করে; যথা সীমাবদ্ধতার সঠিকতা এবং কম্পিউটারের জন্য স্থানীয় অবস্থার উপর, এবং প্রাসঙ্গিক কেন্দ্রীয় থিসিসের সঠিকতার উপর। পরেরটি স্পষ্টভাবে দাবি করে যে একটি গণকের গণনা সরাসরি একটি নির্দিষ্ট ধরনের যন্ত্র দ্বারা অনুকরণ করা যেতে পারে। বিশ্লেষণাত্মক যুক্তির এই ধারাটি যতই সন্তোষজনক মনে হোক না কেন, দুটি দুর্বল দিক রয়েছেঃ সীমাবদ্ধ শর্তগুলির শিথিলতা (প্রতীকী বিন্যাস কী? কোন পরিবর্তনগুলি যান্ত্রিক ক্রিয়াকলাপকে প্রভাবিত করতে পারে?) এবং কেন্দ্রীয় থিসিসের সংশ্লিষ্ট অস্পষ্টতা। আমরা যতই নিজেকে পরিণত করি না কেন, আমরা এমন একটি অবস্থানে রয়েছি যা পদ্ধতিগতভাবে এখনও অসন্তোষজনক। "। তিনি দাবি করেন "আরও সন্তোষজনক অবস্থানের দিকে এগিয়ে যাওয়া. নির্দিষ্ট ধরনের বিন্যাস এবং ক্রিয়াকলাপ থেকে আরও দূরে সরে যাওয়া।" প্রায়শই দাবি করা হয় যে টুরিং যন্ত্রের গণনা বিশ্লেষণ করেছিলেন। এটি ঐতিহাসিকভাবে এবং পদ্ধতিগতভাবে ভুল, কারণ আমার ব্যাখ্যাটি বেশ স্পষ্ট হওয়া উচিত ছিল। শুধুমাত্র 1980 সালে টুরিংয়ের ছাত্র রবিন গ্যান্ডি মেশিন গণনার বৈশিষ্ট্য তুলে ধরেন। উপরের উক্তিটি সত্য কি না তা পাঠকের বিবেচনার উপর ছেড়ে দেওয়া হয়েছে। সিগ গ্যান্ডির বিশ্লেষণের বর্ণনা দেন (উপরে 1980 দেখুন)। এটি করার মাধ্যমে তিনি "গ্যান্ডি মেশিন" কে আনুষ্ঠানিক করার চেষ্টা করেন (একটি পরিশিষ্টে বিস্তারিত বিশ্লেষণ সহ)। গ্যান্ডি মেশিন সম্পর্কেঃ ". গ্যান্ডি মেশিনের সংজ্ঞা হল একটি বিমূর্ত গাণিতিক সংজ্ঞা যা সমান্তরাল গণনার বৈশিষ্ট্যগুলিকে মূর্ত করে। দ্বিতীয়ত, গ্যান্ডি মেশিনগুলি বিমূর্ত স্বতঃসিদ্ধ সংজ্ঞাগুলির সাধারণ বৈশিষ্ট্য গোষ্ঠী এবং টপোলজিকাল স্পেসের সাথে ভাগ করে নেয়, যথা, তারা বিভিন্ন ধরণের ব্যাখ্যা স্বীকার করে। তৃতীয়ত, যে কোনও গ্যান্ডি মেশিনের গণনা একটি অক্ষর যন্ত্র দ্বারা অনুকরণ করা যেতে পারে, [এবং] স্বতঃসিদ্ধ ধারণার জন্য একটি উপস্থাপনা উপপাদ্য হিসাবে সর্বোত্তমভাবে বোঝা যায়। [বোল্ডফেস যোগ করা হয়েছে] "স্বতঃসিদ্ধ পদ্ধতিটি বিমূর্ত উপায়ে গণনা প্রক্রিয়াগুলির অপরিহার্য প্রকৃতিকে ধারণ করে। আমি যে দুই ধরনের ক্যালকুলেটর বর্ণনা করছি তার মধ্যে পার্থক্য এই সত্যে হ্রাস পেয়েছে যে টুরিং কম্পিউটারগুলি একটি অবস্থার একটি সীমাবদ্ধ অংশকে সংশোধন করে, যেখানে গ্যান্ডি মেশিনগুলি নির্বিচারে অনেক সীমাবদ্ধ অংশে সমান্তরালভাবে কাজ করে। উপস্থাপনা উপপাদ্যগুলি নিশ্চিত করে যে স্বতঃসিদ্ধগুলির মডেলগুলি তাদের বর্ণ বৈচিত্র্যে গণনামূলকভাবে টুরিং মেশিনের সমতুল্য। বারওয়াইজ, জন, এইচ. জে. কেইসলার, এবং কে. কুনেন, সম্পাদকগণ, 1980, দ্য ক্লেইন সিম্পোজিয়াম, 426 পৃষ্ঠা, নর্থ-হল্যান্ড পাবলিশিং কোম্পানি, আমস্টারডাম, চার্চ, এ., 1936এ, ইন (ডেভিস 1965:88 এফএফ), "অ্যান আনসোলভেবল প্রবলেম অফ এলিমেন্টারি নম্বর থিওরি" চার্চ, এ., 1936বি, ইন (ডেভিস 1965:108 এফএফ), "এ নোট অন দ্য এন্টশেইডংসপ্রবলেম" চার্চ, এ., 1938, দ্য কনস্ট্রাকটিভ সেকেন্ড নম্বর ক্লাস, বুল। আমের। গণিত। সোস। ভলি. 44, সংখ্যা 4,1938, পৃ. ডেভিস, মার্টিন সম্পাদক, 1965, দ্য আনডিডিবল, বেসিক পেপারস অন আনডিডিবল প্রপোসিশনস, আনসোলভেবল প্রবলেম অ্যান্ড কম্পিউটাবল ফাংশনস, রেভেন প্রেস, নিউ ইয়র্ক। এই নিবন্ধে উল্লিখিত গোডেল, চার্চ, টুরিং, রোজার, ক্লেইন এবং পোস্টের সমস্ত মূল কাগজপত্র এখানে রয়েছে। ডেভিসের মূল্যবান ভাষ্য বেশিরভাগ গবেষণাপত্রে প্রাধান্য পায়। ডেভিস, মার্টিন, 2001, ইঞ্জিনস অফ লজিকঃ ম্যাথমেটিশিয়ানস অ্যান্ড দ্য অরিজিন অফ দ্য কম্পিউটার, ডব্লিউ. ডব্লিউ. নর্টন অ্যান্ড কোম্পানি, নিউ ইয়র্ক, পিবিকে। ডসন, জন উইলিয়াম, জুনিয়র, 1997, লজিক্যাল ডাইলেমাসঃ দ্য লাইফ অ্যান্ড ওয়ার্ক অফ কার্ট গডেল, 361 পৃষ্ঠা, এ. কে. পিটার্স, ওয়েলেসলি, এমএ, QA29.058D39। ডসন, জন উইলিয়াম এবং জন উইলিয়াম ডসন, জুনিয়র, 2005, লজিক্যাল ডাইলেমাসঃ দ্য লাইফ অ্যান্ড ওয়ার্ক অফ কার্ট গডেল, 362 পৃষ্ঠা, এ. কে. পিটার্স, ওয়েলেসলি, এম. এ., ডি পিসাপিয়া, এন., 2000, গ্যান্ডি মেশিনসঃ অ্যান অ্যাবস্ট্র্যাক্ট মডেল অফ প্যারেলাল কম্পিউটশন ফর টুরিং মেশিনস, দ্য গেম অফ লাইফ, অ্যান্ড আর্টিফিশিয়াল নিউরাল নেটওয়ার্কস, এম. এস। থিসিস, কার্নেগি মেলন বিশ্ববিদ্যালয়, পিটসবার্গ। ডারশোভিটস, নাচুম এবং গুরেভিচ, ইউরি, 2007, চার্চের থিসিসের একটি প্রাকৃতিক স্বতঃসিদ্ধকরণ, http://research.microsoft.com ~ গুরেভিচ/অপেরা/188. পিডিএফ গ্যান্ডি, রবিন, 1978, চার্চের থিসিস এবং পদ্ধতির নীতিমালা, ইন (বারওয়াইজ এট আল। 1980:123-148) জর্জ, আলেকজান্ডার (+ সংস্করণ। ), 1994, ম্যাথমেটিক্স অ্যান্ড মাইন্ড, 216 পৃষ্ঠা, নিউ ইয়র্ক, অক্সফোর্ড ইউনিভার্সিটি প্রেস, গোডেল, কে., 1930, ইন (ভ্যান হেইজেনর্ট 1967:592 এফএফ), সম্পূর্ণতা এবং ধারাবাহিকতার উপর কিছু মেটামাথেমেটিকাল ফলাফল গোডেল, কে., 1931এ, ইন (ডেভিস 1965:4-38), অন ফর্মালি আনডিডিবল প্রপোসিশনস অফ দ্য প্রিন্সিপিয়া ম্যাথমেটিকা অ্যান্ড রিলেটেড সিস্টেমস। আই. গোডেল, কে., 1931বি, ইন (ভ্যান হেইজেনর্ট 1976:616 এফএফ) সম্পূর্ণতা এবং সামঞ্জস্যের উপর গোডেল, কে., 1934, ইন (ডেভিস 1965:39-74), অন আনডিডিবল প্রপোসিশনস অফ ফরমাল ম্যাথমেটিকাল সিস্টেমস গোডেল, কে., 1936, ইন (ডেভিস 1965:82 এফএফ), অন দ্য লেন্থ অফ প্রুফস, সম্পাদক দ্বারা অনুবাদিত এরজেনবনিস এইন্স ম্যাথমেটিশেন কোল্লোকিয়ামস, হেফ্ট 7 (1936)-এর মূল নিবন্ধ থেকে। 23-24 "। ক্লেইন (1952) এরজেবনিস এইন্স ম্যাথে "über die Lāange von Beweisen" হিসাবে উল্লেখ করেছেন। কোল ইত্যাদি। গোডেল, কে., 1964, ইন (ডেভিস 1965:71 এফএফ), পোস্টস্ক্রিপ্টাম গ্রোশোজ, এমিলি অ্যান্ড ব্রেগার, হারবার্ট, 2000, দ্য গ্রোথ অফ ম্যাথমেটিকাল নলেজ, 416 পৃষ্ঠা, ক্লুয়ার অ্যাকাডেমিক পাবলিশার্স, ডর্ড্রেক্ট, নেদারল্যান্ডস। হকিং, স্টিফেন, 2005, গড ক্রিয়েটেড দ্য ইন্টিজারসঃ দ্য ম্যাথমেটিকাল ব্রেকথ্রুস দ্যাট চেঞ্জড হিস্ট্রি, এডিটেড, উইথ কমেন্টারি বাই স্টিফেন হকিং, রানিং প্রেস, ফিলাডেলফিয়া, হজস, অ্যান্ড্রু, 1983, অ্যালান টুরিংঃ দ্য এনিগমা, 1ম সংস্করণ, সাইমন অ্যান্ড শুস্টার, নিউ ইয়র্ক, ক্লিন, এস. সি., 1935, ইন (ডেভিস 1965:236 এফ. এফ.) জেনারেল রিকার্সিভ ফাংশনস অফ ন্যাচারাল নাম্বারস ক্লিন, এস. সি., 1971,1952 (10ম ছাপ 1991) ইন্ট্রোডাকশন টু মেটামাথেম্যাটিক্স, 550 পৃষ্ঠা, নর্থ-হল্যান্ড পাবলিশিং কোম্পানি (ওল্টার্স-নর্ডহফ পাবলিশিং) মেরিয়াম-ওয়েবস্টার ইনক., 1983 1, না। 3 (সেপ্টেম্বর, 1936), পৃ. 103-105। রজার। জে। বি, 1939, গোডেলের উপপাদ্য এবং চার্চের উপপাদ্যের প্রমাণের একটি অনানুষ্ঠানিক ব্যাখ্যা, দ্য জার্নাল অফ সিম্বলিক লজিক। খণ্ড। 4. (1939), পৃ. 53-60 এবং (ডেভিস 1967:223-230)-এ পুনরায় মুদ্রিত। সিগ, উইলফ্রিড, রিচার্ড সমার এবং ক্যারোলিন ট্যালকট (সংস্করণ। ), 2002, রিফ্লেকশনস অন দ্য ফাউন্ডেশন্স অফ ম্যাথমেটিক্সঃ এসেস ইন অনার অফ সলোমন ফেফারম্যান, লেকচার নোটস ইন লজিক 15,444 পৃষ্ঠা, এ কে পিটার্স লিমিটেড, সোয়ার, রবার্ট, 1996, কম্পিউটাবিলিটি অ্যান্ড রিকার্সন, "বুলেটিন অফ সিম্বলিক লজিক 2", খণ্ড 2, সংখ্যা 3, সেপ্টেম্বর 1996, পৃ. এবং (আরও দেখুনঃ ডেভিস 1965:115 এফএফ) টুরিং, এ., 1939, ইন (ডেভিস 1965:154 এফএফ), সিস্টেমস অফ লজিক বেসড অন অর্ডিনালস ভ্যান হেইজেনর্ট, জিন, 1976, ফ্রম ফ্রেজ টু গডেলঃ এ সোর্স বুক ইন ম্যাথমেটিকাল লজিক, 116 পৃষ্ঠা, 1879-1931,3য় প্রিন্টিং, অরিজিনাল প্রিন্টিং 1967, হার্ভার্ড ইউনিভার্সিটি প্রেস, কেমব্রিজ ম্যাসাচুসেটস, (পিবিকে)। বাহ্যিক লিঙ্ক প্রতীকী যুক্তির বুলেটিনে অনলাইনে কাগজপত্র সহ সমস্ত খণ্ডের লিঙ্ক রয়েছে। অ্যালনজো চার্চ, 1938, দ্য কনস্ট্রাকটিভ সেকেন্ড নম্বর ক্লাস "সোসাইটির ইন্ডিয়ানাপলিস সভায় প্রোগ্রাম কমিটির আমন্ত্রণে প্রদত্ত একটি ঠিকানা, 29 ডিসেম্বর, 1937"। কার্ট গোডেল, 1931, প্রিন্সিপিয়া ম্যাথমেটিকা এবং সম্পর্কিত সিস্টেমগুলির আনুষ্ঠানিকভাবে অনির্ধারিত প্রস্তাবের উপর I। মার্টিন হিরজেল দ্বারা অনুবাদিত, 27 নভেম্বর 2000। এমিল এল. পোস্ট, 1946, আ ভ্যারিয়েন্ট অফ আ রিকার্সিভলি আনসোলভেবল প্রবলেম উইলফ্রিড সিগ, 2005, চার্চ উইথ ডট ডগমাঃ অ্যাক্সিওমস ফর কম্প্যুটেবিলিটি, কার্নেগি মেলন ইউনিভার্সিটি উইলফ্রিড সিগ, 2000, ক্যালকুলেশনস বাই ম্যান অ্যান্ড মেশিনঃ কনসেপচুয়াল অ্যানালাইসিস, কার্নেগি মেলন ইউনিভার্সিটি রবার্ট আই. সোয়ার, 1995, কম্প্যুটেবিলিটি অ্যান্ড রিকার্সন রবার্ট আই. সোয়ার, 1996, কম্প্যুটেবিলিটি অ্যান্ড রিকার্সন যা দ্য বুলেটিন অফ সিম্বলিক লজিক, ভলিউম 2, ভলিউম 2, নম্বর 3, সেপ্টেম্বর 1996-এ প্রকাশিত হয়েছিল। মাসাকো তাকাহাশি, 2004, সাধারণ পুনরাবৃত্তিমূলক ক্রিয়াকলাপের উপর, আন্তর্জাতিক খ্রিস্টান বিশ্ববিদ্যালয় বিশেষত, রেফারেন্স দেখুন। এ. এম. টুরিং, 1936, অন কম্পিউটাবল নাম্বারস, উইথ অ্যান অ্যাপ্লিকেশন টু দ্য এন্টশেইডংসপ্রোবলেম চার্চ-টুরিং থিসিস কম্পিউটাবিলিটি থিওরি অ্যালান টুরিং থিওরি অফ কম্প্যুটেশন