This paper studies effectiveness in the domain of computability. In the context of model-theoretical approaches to effectiveness, where a function is considered effective if there is a model containing a representation of such function, our definition relies on a model provided by functions between finite sets and uses category theory as its mathematical foundations. The model relies on the fact that every function between finite sets is computable, and that the finite composition of such functions is also computable. Our approach is an alternative to the traditional model-theoretical based works which rely on (ZFC) set theory as a mathematical foundation, and our approach is also novel when compared to the already existing works using category theory to approach computability results. Moreover, we show how to encode Turing machine computations in the model, thus concluding the model expresses at least the desired computational behavior. We also provide details on what instances of the model would indeed be computable by a Turing machine.
|Journal||Electronic Notes in Theoretical Computer Science|
|Publication status||Published - 2016|
|Event||3rd Workshop-School on Theoretical Computer Science (WEIT 2015) - Porto Alegre, Brazil|
Duration: 14 Oct 2015 → 16 Oct 2015
Conference number: 3
|Workshop||3rd Workshop-School on Theoretical Computer Science (WEIT 2015)|
|Period||14/10/2015 → 16/10/2015|
Bibliographical noteThis is an open access article under the CC BY-NC-ND licens.
- Finite sets
- Models of computation