A Chaitin Omega number, Ω, is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Ω number is both computably enumerable and random. In particular, every Ω number is non-computable. In this thesis, we describe a method to compute the exact values of the first 64 successive bits of a natural Chaitin Omega number. We first describe a model of computation which has been defined and proved to be a universal Chaitin machine U. We then propose a method (procedure) which combines iterative executions of an algorithm with mathematical analysis to get the exact values of the first successive 64 bits of the corresponding Chaitin ΩU number of U. This particular defined Chaitin machine U is essentially a register machine and has been implemented in Java. We call it the canonical compressed model (or compressed model) as it allows only ‘canonical’ program strings to be processed in U. Thus, many input strings which are illegal, hence useless, are ignored and never involved in the computational process. In addition, the compressed design shortens the length of all instructions so that relatively short strings now contain somewhat complex programs. A simulator for U, written in Java, is a primary part of the project. The algorithm is executed iteratively, computing step by step an increasing sequence of rational numbers (in binary) to approximate Ω U. In the n-th step, the algorithm produces four main output files: all halting strings, looping strings, run-time errors, and prefix strings (incomplete programs). In each step, all prefix strings (of the previous step) are read and processed one by one. Each string is extended by 7 bits (ASCII code representations for symbols) to generate new strings that are examined one by one to detect any lexical, syntactic, semantic, or run-time error in each of them. Any of those strings with an error detected is discarded to save storage space and execution time. We solve the Halting Problem for all programs for U of length less than or equal to 84 bits so we can calculate an increasing sequence of exact approximations converging to ΩU. By means of a mathematical analysis the first successive 64 bits, 0000001000000100000110001000011010001111110010111011101000010000 of the 84 bits are proved to be the exact first bits of ΩU. Actually, more bits can be obtained by this procedure if the disk space is sufficient for it to go on, but this procedure cannot be extended indefinitely. In order to assure that our computing result is correct, we have proved that all input strings of length less than or equal to 84 executed in U over 100 steps are not halting programs.* *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation). The CD requires the following system requirements: Adobe Acrobat; Microsoft Office.
| Identifer | oai:union.ndltd.org:ADTP/274392 |
| Date | January 2004 |
| Creators | Shu, Chi-Kou |
| Publisher | ResearchSpace@Auckland |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated., http://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm, Copyright: The author |
Page generated in 0.002 seconds