Andrew MacFie

Andrew MacFie

We consider the problem of rational uncertainty about unproven mathematical statements, remarked on by Gödel and others. Using Bayesian-inspired arguments we build a normative model of fair bets under deductive uncertainty which draws from both probability and the theory of algorithms. We comment on connections to Zeilberger's notion of "semi-rigorous proofs", particularly that inherent subjectivity would be present. We also discuss a financial view with models of arbitrage where traders have limited computational resources.

Andrew MacFie

We present an alternative methodology for the analysis of algorithms, based on the concept of expected discounted reward. This methodology naturally handles algorithms that do not always terminate, so it can (theoretically) be used with partial algorithms for undecidable problems, such as those found in artificial general intelligence (AGI) and automated theorem proving. We mention an approach to self-improving AGI enabled by this methodology. Aug 2017 addendum: This article was originally written with multiple audiences in mind. It is really best put in the following terms. Goertzel, Hutter, Legg, and others have developed a definition of an intelligence score for a general abstract agent: expected lifetime reward in a random environment. AIXI is generally the optimal agent according to this score, but there may be reasons to analyze other agents and compare score values. If we want to use this definition of intelligence in practice, perhaps we can start by analyzing some simple agents. Common algorithms can be thought of as simple agents (environment is input, reward is based on running time) so we take the goal of applying the agent intelligence score to algorithms. That is, we want to find, what are the IQ scores of algorithms? We can do some very simple analysis, but the real answer is that even for simple algorithms, the intelligence score is too difficult to work with in practice.