CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

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

Zoran Konkoli (Institutionen för mikroteknologi och nanovetenskap, Bionanosystem)
International Journal of Unconventional Computing (1555-0281). Vol. 11 (2015), p. 83-102.
[Artikel, refereegranskad vetenskaplig]

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.

Denna post skapades 2015-04-01. Senast ändrad 2015-05-11.
CPL Pubid: 214750


Institutioner (Chalmers)

Institutionen för mikroteknologi och nanovetenskap, Bionanosystem (2007-2015)


Statistisk fysik
Övrig informationsteknik
Praktisk filosofi

Chalmers infrastruktur