Defining Effectiveness Using Finite Sets A Study on Computability

Hugo Daniel dos Santos Macedo, Edward H. Haeusler, Alex Garcia

Research output: Contribution to journalConference articleResearchpeer-review

250 Downloads (Pure)

Abstract

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.
Original languageEnglish
JournalElectronic Notes in Theoretical Computer Science
Volume324
Pages (from-to)91-106
ISSN1571-0661
DOIs
Publication statusPublished - 2016
Event3rd Workshop-School on Theoretical Computer Science (WEIT 2015) - Porto Alegre, Brazil
Duration: 14 Oct 201516 Oct 2015
Conference number: 3
https://www.ufrgs.br/weit2015/

Workshop

Workshop3rd Workshop-School on Theoretical Computer Science (WEIT 2015)
Number3
CountryBrazil
CityPorto Alegre
Period14/10/201516/10/2015
Internet address

Bibliographical note

This is an open access article under the CC BY-NC-ND licens.

Keywords

  • Effectiveness
  • Finite sets
  • Models of computation

Fingerprint Dive into the research topics of 'Defining Effectiveness Using Finite Sets A Study on Computability'. Together they form a unique fingerprint.

Cite this