<p>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.</p>

<p>There is a formal definition of computability: a function <span class="math-container">$f$</span> is computable if there is a Turing machine that, given input <span class="math-container">$x$</span>, always halts with <span class="math-container">$f(x)$</span> written on its tape.</p>

<p>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. </p>

<p>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 <span class="math-container">$f:\mathbb{N}\to \{0,1\}$</span> that outputs the <span class="math-container">$i$</span>'th bit of the number is computable. But that is only a "lift" of the concept of computability.</p>

CC BY-SA 4.0
2020-01-16T17:52:03.560Z
"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.
superman321
CC BY-SA 4.0
2020-01-16T21:16:17.257Z
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
Denis
CC BY-SA 4.0
2020-01-16T21:27:48.103Z
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.
Shaull
CC BY-SA 4.0
2020-01-16T21:55:19.463Z
Then there is no point in using the term "computability" when there is no one generic definition.
superman321
CC BY-SA 4.0
2020-01-17T06:27:52.677Z
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.)
Shaull
CC BY-SA 4.0
2020-01-16T16:10:15.003Z
2020-01-16T16:40:02.230Z
2020-01-16T16:40:02.230Z
Shaull
<p>I still haven't found a good definition of <em>computability</em>. All the definitions are either too vague, or they delegate the definition to another loaded term like <em>"anything that uses <strong>math</strong> to solve a problem"</em>, or <em>"anything that can be solved by a <strong>computer</strong>"</em>. So I came up with my own definition:</p>

<p><em>"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."</em></p>

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

CC BY-SA 4.0
2020-01-20T18:01:27.103Z
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](https://en.wikipedia.org/wiki/Arithmetical_hierarchy) in the structure $(\mathbb{N};+,\times)$.
Noah Schweber
CC BY-SA 4.0
2020-01-20T18:02:54.860Z
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.
Noah Schweber
<computability><halting-problem><formal-modeling><church-turing-thesis>
Is this a good definition of computability?
superman321
# Is this a good definition of computability?

(Asked by: username_0 on 2020-01-16)

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?

**Tags:** computability, halting-problem, formal-modeling, church-turing-thesis
> **Comments:**
> **username_1**: 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](https://en.wikipedia.org/wiki/Arithmetical_hierarchy) in the structure $(\mathbb{N};+,\times)$.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2020-01-16. Score: 2

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.

> **Comments:**
> **username_0**: "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.  
> **username_3**: 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  
> **username_2**: 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.  
> **username_0**: Then there is no point in using the term "computability" when there is no one generic definition.  
> **username_2**: 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.)  

---

