[FOM] Re: New Characterization of Recursivity

[Csaba Henk]

On Sun, Jun 06, 2004 at 08:05:51PM -0400, Ali Enayat wrote:

Sorry for the bit belated reaction -- I went through the following
phases (and it took some time): first, I tried to understand what you have
written, then I hunted down the reference you gave (the FMT book), and then
again, I tried to grasp your train of thouhgt, and finally, I concluded that
I couldn't understand it.

> 2. However, Henk's characterization follows immediately from the following
> "fine-tuning" of the classical characterization of recursivity:
> 
> X is recursive iff there is a Turing machine T with the following
> properties:
> 
> (1) On any given input, if T converges on some input q, and outputs s, then
> s = 0 or s = 1, but not both.

Does "but not both" mean that you speak about non-determininstic Turing
Machines [TM's] ? If so, what's the significance of non-determinism?
 
> (2) For any input q, property (1) above holds in any "universe" B that
> contains a sufficiently large finite subset F of the hereditarily finite
> sets (B is required to end extend F, hence Delta_0 formulae will be
> absolute).

This is the point where I lost. For first time, you seem to itend to give a
list of categoric TM properties (which are meaningful for any TM, and
applying them to a TM yields a truth value without further fuss), then in
(2) it seems as if (1) had a "universe" parameter as well, and you don't use
(1) as a categoric requirement, but as something which has to be fulfilled
for certain universes only. Furthermore, I don't see how "classic" TM
properties (ie. ones which composed of notions like halting, inputs, etc.)
can be parametrized by subuniverses of the hereditarily finite sets. (How
should one interpret such a property in an unverse B? What has a TM to with
such universes?)

> (3) T eventually halts on all inputs q.

What's the role of the attribute "eventually"? Why isn't it as simple as it
"halts or not"? Does it mean that here again we have a hidden universe
parameter, which being big enough ensures halting?
 
> (4) T outputs 1 on an input q iff q is in X.

That one at least is quite clear, I think :)
 
> The fine-tuning (2) is classical. The first time I encountered it was in
> the proof of Trakhtenbrot's theorem (asserting that the set of sentences in
> the language of binary graphs that are valid in finite domains is not
> r.e.). See section 6.2.1 of the following text for a beautiful
> presentation:
> 
> Finite Model Theory, by H.-D. Ebbinghaus and J. Flum (Springer).

The section you refer to presents Trakhtenbrot's theorem. There are finite
structures mentioned in the proof, but they are used to encode concrete TM
runs and not as some kind of universes in which TM-related properties can
hold or fail. The next section uses structures as inputs, but that usage
also differs from using them as "universes" in the sense of the previous
sentence. Thus it didn't help me in resolving my problems with the above.

I'd appreciate if you made a second attempt of writing down your ideas, or
sheded some lights on those implicit parts which I couldn't get.

Regards,
-- 
Csaba Henk

"There's more to life, than books, you know but not much more..."
[The Smiths]