After briefly discussing the relevance of the notions ‘computation’ and ‘implementation’ for cognitive science, I summarize some of the problems that have been found in their most common interpretations. In particular, I argue that standard notions of computation together with a ‘state-to-state correspondence view of implementation’ cannot overcome difficulties posed by Putnam's Realization Theorem and that, therefore, a different approach to implementation is required. The notion ‘realization of a function’, developed out of physical theories, is then introduced as a replacement for the notional pair ‘computation-implementation’. After gradual refinement, taking practical constraints into account, this notion gives rise to the notion ‘digital system’ which singles out physical systems that could be actually used, and possibly even built.
@article{scheutz99mm,
title={When Physical Systems Realize Functions...},
author={Scheutz, Matthias},
year={1999},
journal={Minds and Machines},
volume={9},
pages={161--196}
url={https://hrilab.tufts.edu/publications/scheutz99mm.pdf}
doi={10.1023/A:1008364332419}
}