1936年，阿兰·图灵在其名为“论可计算数字及其在判定性问题中的应用”的论文中，首次提出了使用图灵机来理论化一个关键概念。在这篇论文中，他揭示了判定性问题的不可解决性，即无法找到一个通用方法来确定任何给定问题是否有确定的答案。
在此之前几个月，阿隆佐·邱奇在“关于判定性问题的解释”一文中，同样探讨了类似的主题。他运用递归函数和Lambda可定义函数来定义有效可计算性。递归函数是库尔特·歌德尔和雅克斯·赫尔布兰特所发展的重要概念，而Lambda可定义函数则由阿隆佐·邱奇和史蒂芬·克林在其著作中提出，如Church(1932, 1936a, 1941)和Kleene(1935)的工作。这些方法实质上描述了同一集合中函数的行为，正如邱奇和克林在他们的研究中所展示的正整数函数那样，它们的计算能力是等价的。
在得知邱奇的工作后，图灵迅速地认识到他的图灵机模型实际上与递归函数和Lambda可定义函数描述的计算能力是一致的。图灵在他的论文(Turing 1936, 263ff)中，进一步证实了这一观点，将这些理论框架统一在了一起。
邱奇-图灵论题(The Church-Turing thesis)是计算机科学中以数学家阿隆佐·邱奇(Alonzo Church)和阿兰·图灵命名的论题。该论题最基本的观点表明，所有有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言大程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题。