Open AccessAutomata, Languages and Programming
Author(s) -
Eugène Asarin,
Pieter Collins
Publication year - 2005
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/11523468
Subject(s) - automaton , programming language , computer science , theoretical computer science
International audienceTuring machines exposed to a small stochastic noise are considered. An exact characterisation of their (≈Π20) computational power (as noise level tends to 0) is obtained. From a probabilistic standpoint this is a theory of large deviations for Turing machines
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom