什么是计算？计算机可干些什么？这是计算机科学的基本总是可通过建立可计算性的模型来讨论这个问题，而不是从一个具体的计算机入手。
选定英国数学家Turing 1936年提出的Turing机为可计算的模型，Turing机是一个非常简单但功能十分强的理想计算机，在一定程度上反映了人类最基本的原始的计算能力。
这个机器以一条无限长的带（可读写）为存储器，有几条指令，相当于运算器控制器，处理的符号以二值逻辑表示。指令共六条，写1、写0、右移、左移、遇1转移和遇0转移。这个计算机可实现当今计算机的功能，是计算机的模型。与今日机器相比主要区别是有无限的存储能力，但效率十分之低。正是Turing机推动了1946年第一台电子计算机的诞生。
Church论题规定，凡Turing机可作的都是计算，凡Turing可计算的就叫可计算的。
可计算的与直觉的实际上的可计算是有区别的，然而Turing不可计算的必为实际不可计算；而一个Turing可计算的计算过程需多少世纪才能完成的，自然是实际不可计算的。
（2）可计算性与递归函数
Turing可计算的函数必是递归函数，反过来递归函数必是Turing可计算的，它们是等同的概念。
递归函数是数论函数，即以自然数为研究对象，定义域和值域均是自然数。递归函数的一些主要方法直接关系着自然数，然而数论函数讨论的范围是相当广泛的。如整数-5可用（1，5）表示，有理数
可用（1，2，5）表示，实数可用自然数序列表示，复数可由一对自然数序列表示，符号A,B,C
也可用自然数来编码。一般地说有Godel编码定理：一个非数字系统与自然数间可建立一一对应关系。从而非数字系统的研究可归结为自然数间函数关系的研究。从可计算性角度限于递归函数的讨论并没有局限性。递归函数是一种构造性函数，不只限于存在性（非构造性）的讨论，给了一个递归函数，相当于给该函数一个计算的算法。如说任一偶数可表示成两素数之和的问题，一种解决办法是对偶数2n给一算法来找出素数a,b使2n=a+b ，这是构造性证明法。另一种解法是证明有a,b存在使2n=a+b，而a,b如何求并不指明，这是属于存在性证明，要真的求出a,b尚需另想办法。递归函数本身是构造性定义的，它的每个变元下的函数值都给了办法来计算。从这里便可想象递归函数直觉上是可计算的。