I still haven't found a good definition of computability. All the definitions are either too vague, or they delegate the definition to another loaded term like "anything that uses math to solve a problem", or "anything that can be solved by a computer". So I came up with my own definition:

"A problem is computable, if both it and its solution, can be reduced to a formal symbolic representation, and there exists a finite number of formally-defined symbolic manipulation steps that can convert the problem to its solution."

Does that make sense, and/or can you come up with a better or modified answer?

  • $\begingroup$ The definition you propose is rather close to the Godel-Herbrand definition, although yours is too vague to really constitute a precise definition. A related, and easier to use, notion is the following: a partial function $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable iff it is $\Sigma_1$-definable in the structure $(\mathbb{N};+,\times)$. $\endgroup$ – Noah Schweber Jan 20 at 18:01
  • $\begingroup$ But in my opinion you're ignoring one of the key points about computability: it's a concept which has many very different intuitive definitions which all turn out to be equivalent. That's indicative of its value: there's this collection of functions (or sets if you prefer) which keeps showing up over and over again in different guises. $\endgroup$ – Noah Schweber Jan 20 at 18:02

First of all, the place for this question is cs.se, not here. But since I've already written an answer, I'll leave it.

There is a formal definition of computability: a function $f$ is computable if there is a Turing machine that, given input $x$, always halts with $f(x)$ written on its tape.

You could of course define more general computability, which uses a different model, but you cannot hope to define computability independently of a model, since different models can compute different things.

Note that some things that are called "computable" don't fall under this definiiton, most notably that of a computable real number, where the definition actually says that a real number is computable if the function $f:\mathbb{N}\to \{0,1\}$ that outputs the $i$'th bit of the number is computable. But that is only a "lift" of the concept of computability.

| cite | improve this answer | |
  • $\begingroup$ "but you cannot hope to define computability independently of a model" but that is what the question asks.... a universal description of computability independent of the model. $\endgroup$ – superman321 Jan 16 at 17:52
  • 1
    $\begingroup$ if what you want is a definition not with a model, but with words in natural language with no well-defined meaning, it's not a mathematical definition, and your question is more appropriate for philosophy.se $\endgroup$ – Denis Jan 16 at 21:16
  • 1
    $\begingroup$ A definition cannot be independent of a model, because different models yield different computable functions. For example, finite automata cannot compute non-regular functions, but Turing machines can. So in order to get a well-defined concept, it must relate to a computational model. $\endgroup$ – Shaull Jan 16 at 21:27
  • $\begingroup$ Then there is no point in using the term "computability" when there is no one generic definition. $\endgroup$ – superman321 Jan 16 at 21:55
  • 1
    $\begingroup$ Whether there is or isn't a point to something is a philosophical question. The term computability is (currently) reserved to a definition via Turing machines. The mathematical community agrees that it is a useful term, so that is the point. If we want a different model, we say "computable by X" (where X is e.g., a regular transducer, etc.) $\endgroup$ – Shaull Jan 17 at 6:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.