A Perspective on Putnam's Realizability Theorem in the Context of Unconventional Computation

摘要

Putnam proved a theorem stating that, under very generic conditions, every physical system implements any finite state automaton. This challenges the whole field of unconventional computation in the most fundamental way. The present study is a response to this challenge. Putnam's theorem is revisited in the context of unconventional computation where the emphasis is on the practical use of a system for a computation. The main goal of this study is to identify an algorithm that can solve the following (natural computability) problem: Given a physical system, identify the automaton (automata) that it naturally implements. A rigorous definition of the concept of natural computation is suggested: The natural implementation results in the largest computing power and has the lowest realisation cost. These ideas are formalized using rigorous mathematical reasoning. A generic algorithm for identifying the automata of interest is presented.