[FOM] Universal but not acceptable programming systems

Brian Postow bpostow at union.edu
Tue Feb 17 15:38:32 EST 2004

Hello, I'm a fairly recent PhD from the University of Maryland. There
is a minor result in my thesis that I thought someone might be
interested in, and Bill Gasarch said that this community might be a
place start.

Basically, I accidentally found a natural model of computation which
is universal, but not acceptable (universal plus S-m-n functions). I consider
it natural because it arose out of an intermediate version of a model
that I was creating for a different purpose. Friedberg proved that
such a model can exist, only he used artificial means such as priority
and simulation arguments. 

The full bibliographic information is: 

Brian Postow and Kenneth Regan and Carl Smith, "UPSILON: A Universal
  Programming System with Incomplete Lazy Object Notation" in
  Fundamenta Informatica, 2002.  vol 50 num 3, pages 325-359.

or you can download it:

The relevant result is in section 8.2.

In addition I'd be interested to know if, beyond mere curiosity, there
is any interest in such a model.

Thank you

Brian Postow

More information about the FOM mailing list