১৯৩১ সালে কার্ট গডেল তার ইনকমপ্লিটনেস থিওরেম বা অসম্পূর্নতার উপপাদ্য প্রকাশ করেন। এই উপপাদ্য অনুসারে যেকোন গাণিতিক ধারা বা মডেলে(যা এক বা একাধিক স্বতঃসিদ্ধের উপর ভিত্তি করে তৈরী হয়) অসম্পূর্নতা থাকতে পারে। এই অসম্পূর্নতার অর্থ হল এই যে এখানে একাধিক (অনুমান) বা (বিবৃতি) থাকবে যাদেরকে গণিতের সাহায্যে প্রমাণ করা সম্ভব হবে না। এই উপপাদ্য এবিষয়ে আরও গবেষণার সূচনা করে এবং এর ফলে মিউ রিকার্সিভ ফাংশন,ল্যাম্বডা-ডিফাইনেবেল ফাংশন ধারণাগুলি সামনে আসে।

১৯৩৬ সালে (আলোঞ্জ চার্চ) ও ট্যুরিং চার্চ-ট্যুরিং থীসিস প্রকাশ করেন। চার্চ-ট্যুরিং থীসিস অনুযায়ী, কোন গাণিতিক সমাধানপদ্ধতিকে তখন (এফেক্টিভলি ক্যালকুলেবেল) অর্থাৎ গণনাযোগ্য বলা যায় যা কোন পূর্বার্জিত জ্ঞান ছাড়াই শুধুমাত্র কাগজ-কলমে অণুসরন করে সমাধান করা সম্ভব। এটি ছিল আধুনিক কম্পিউটার অ্যালগরিদম্-এর সরলতম মডেল প্রকৃতির যা পর্যাপ্ত সময় ও মেমরি থাকলে, যান্ত্রিকভাবে যেকোন সমাধান করতে সক্ষম। ট্যুরিং প্রকাশিত ট্যুরিং মেশিন-এর ধারণাও আধুনিক কম্পিউটার প্রোগ্রামিং-এর ভিত্তিপ্রস্তর স্থাপন করে। যে কাজ এই মেশিন করতে পারে তা ট্যুরিং কম্প্লিট বলে গণ্য হয়।

যদিও বিজ্ঞানী জন ভন নিউম্যান কে কম্পিউটারের জনক বলা হয়, কিন্তু অনেকের মতেই আসলে অ্যালেন ট্যুরিং-এর তত্ত্ব থেকেই কম্পিউটারের ধারণা শুরু হয়। উদাহরণস্বরুপ, (লস্ অ্যালামস্) গবেষণাগারের বিজ্ঞানী স্ট্যানলী ফ্র্যাঙ্কেল-এর একটি চিঠির কথা উল্লেখ করা যায় যার বয়ান নিম্নরুপ:
শুরুর দিকের কম্পিউটার হার্ডওয়্যার
চার্লস্ ব্যাবেজ ও এডা লাভলেস্
অ্যালেন ট্যুরিং ও ট্যুরিং মেশিন
শ্যানন্ ও ইনফরমেশন থিওরি