# Is this a good definition of computability? [closed]

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?

• 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)$. Jan 20, 2020 at 18:01
• 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. Jan 20, 2020 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.

• "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. Jan 16, 2020 at 17:52
• 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 Jan 16, 2020 at 21:16
• 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. Jan 16, 2020 at 21:27
• Then there is no point in using the term "computability" when there is no one generic definition. Jan 16, 2020 at 21:55
• 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.) Jan 17, 2020 at 6:27