2025-06-13 | | Total: 3
Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for $G$-shifts, where $G$ is a finitely generated group with decidable word problem. A $G$-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of $G$-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions.
Markov decision processes (MDPs) are a popular model for decision-making in the presence of uncertainty. The conventional view of MDPs in verification treats them as state transformers with probabilities defined over sequences of states and with schedulers making random choices. An alternative view, especially well-suited for modeling dynamical systems, defines MDPs as distribution transformers with schedulers distributing probability masses. Our main contribution is a unified semantical framework that accommodates these two views and two new ones. These four semantics of MDPs arise naturally through identifying different sources of randomness in an MDP (namely schedulers, configurations, and transitions) and providing different ways of interpreting these probabilities (called the chance and mass interpretations). These semantics are systematically unified through a mathematical construct called chance-mass (CM) classifier. As another main contribution, we study a reachability problem in each of the two new semantics, demonstrating their hardness and providing two algorithms for solving them.
According to the Landauer principle, any logically irreversible process accompanies entropy production, which results in heat dissipation in the environment. Erasing of information, one of the primary logically irreversible processes, has a lower bound on heat dissipated into the environment, called the Landauer bound (LB). However, the practical erasure processes dissipate much more heat than the LB. Recently, there have been a few experimental investigations to reach this bound both in the classical and quantum domains. There has also been a spate of activities to enquire about this LB in finite time, with finite-size heat baths, non-Markovian and nonequilibrium environment in the quantum regime where the effects of fluctuations and correlation of the systems with the bath can no longer be ignored. This article provides a comprehensive review of the recent progress on the Landauer bound, which serves as a fundamental principle in the thermodynamics of computation. We also provide a perspective for future endeavors in these directions. Furthermore, we review the recent exploration toward establishing energetic bounds of a computational process. We also review the thermodynamic aspects of error correction, which is an indispensable part of information processing and computations. In doing so, we briefly discuss the basics of these fields to provide a complete picture.