Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
<< vorige   
     Tijdschrift beschrijving
       Alle jaargangen van het bijbehorende tijdschrift
         Alle afleveringen van het bijbehorende jaargang
           Alle artikelen van de bijbehorende aflevering
                                       Details van artikel 5 van 5 gevonden artikelen
  Very Simple Chaitin Machines for Concrete AIT
Titel: Very Simple Chaitin Machines for Concrete AIT
Auteur: Michael Stay
Verschenen in: Fundamenta informaticae
Paginering: Jaargang 68 (2005) nr. 3 pagina's 231-247
Jaar: 2005-09-16
Inhoud: In 1975, Chaitin introduced his celebrated Omega number, the halting probability of a universal Chaitin machine, a universal Turing machine with a prefix-free domain. The Omega number's bits are algorithmically random-there is no reason the bits should be the way they are, if we define "reason" to be a computable explanation smaller than the data itself. Since that time, only two explicit universal Chaitin machines have been proposed, both by Chaitin himself. Concrete algorithmic information theory involves the study of particular universal Turing machines, about which one can state theorems with specific numerical bounds, rather than include terms like O(1). We present several new tiny Chaitin machines (those with a prefix-free domain) suitable for the study of concrete algorithmic information theory. One of the machines, which we call Keraia, is a binary encoding of lambda calculus based on a curried lambda operator. Source code is included in the appendices. We also give an algorithm for restricting the domain of blank-endmarker machines to a prefix-free domain over an alphabet that does not include the endmarker; this allows one to take many universal Turing machines and construct universal Chaitin machines from them.
Uitgever: IOS Press
Bronbestand: Elektronische Wetenschappelijke Tijdschriften

                             Details van artikel 5 van 5 gevonden artikelen
<< vorige   
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland