[FOM] Plea for literature on recursion theory in V_\omega

[Vladimir Sazonov]

A highly relevant book by John Barwise was already mentioned by François G. Dorais. 
Also the Ackerman bijective encoding of HF (Hereditarily-Finite sets) = V_\omega 
by natural numbers recalled by Vaughan Pratt, 
e:N -> HF, 
e(0)={}, 
e(2^{n_1} + 2^{n_2}+ ... + 2^{n_k}) = {e(n_1) + e(n_2) + ... + e(n_k)},
n_1 > n_2 > ... >  n_k,

is indeed very nice from the point of view of general computability theory. 
But from the point ov view of complexity theory and *practical* computations 
it is *highly inefficient*. 
Graph encoding where each (finite acyclic) graph node naturally 
denotes an HF set is much more robust for defining Polynomial Time 
(or, alternatively, Logarithmic Space) computability over 
well-founded HF sets. For non-well-founded HFA sets (also called 
hypersets) satisfying finite version of Anti-foundation axiom 
(nodes of) *arbitrary* finite graphs (possibly with cycles) can serve 
as encoding. See more on that and on Bounded Set Theory in 
http://www.csc.liv.ac.uk/~sazonov/papers.html
An approach to semistructured or Web-like databases grounded 
on the universe HFA of hypersets is also being developed. 
Its working implementation in Java is presented in 
http://www.csc.liv.ac.uk/~molyneux/ICSOFT2007appendix/
>From this link you can run and play with queries in Delta language 
over HFA (whose expressive power over HFA is exactly Ptime). 
The BNF of the query language Delta and some examples of queries 
are also presented in the latter URL which can help to start with. 
Any comments on this language and its implementation, etc. are welcome! 
Finally, let me also recall the relevant (universal) set theoretic 
programming language SETL. Note that Delta is rather a database query 
language than a universal programming language. However, there is no 
problem to extend it to a universal programming language, say by 
unbounded existential quantification making it rather the language 
Sigma (using the terminology close to the Barwise book). 
Vladimir Sazonov


----- Original Message ----
> From: Csaba Henk <csaba-ml at creo.hu>
> To: fom at cs.nyu.edu
> Sent: Monday, April 28, 2008 12:36:52 PM
> Subject: [FOM] Plea for literature on recursion theory in V_\omega
> 
> Dear FOM members,
> 
> I am to write my PhD thesis. I plan to base my "design" on recursion
> theory built up in V_\omega (ie., the universe of hereditarily finite
> sets [as a first-order structure with the language of set theory]).
> 
> All textbooks I know of use an arithmetic context for explaining
> recursion theory. I'd like to ask: do you know of some book which uses
> V_\omega for this purpose? Or any book which discusses the well-known
> semantic equivalence (yes, this is a vague term, but you should know
> what I mean...) of <\omega, + , *> and ?
> 
> (I know this is a well explored area, but I don't know how much of this
> remained "folklore"... My focus is on finding nicely worded definitions
> and theorems which I can use as references for my original work.)
> 
> Thanks for your suggestions!
> 
> Regards,
> Csaba
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom



      ____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now..  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ