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

Thu May 1 18:50:46 EDT 2008

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).

----- 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.)
>
>
> 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