邱奇图灵论题

该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。邱奇-图灵论题(The Church-Turing thesis)是计算机科学中以数学家阿隆佐·邱奇(Alonzo Church)和阿兰·图灵命名的论题。该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言的程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题。本论题的另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。