[FOM] Universal but not acceptable programming systems
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
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.
More information about the FOM