[tsimionescu]

My assumption is that something like a Turing machine, or like a reduction in Lambda calculus, or like a demonstration with the basic laws of predicate logic (all known equivalent models of computation) is a computer.