infinitary structures

[Billy Tanksley]

> -----Original Message-----
> From:	RE01 Rice Brian T. EM2 [SMTP:BRice@vinson.navy.mil]
> 
> in the theory of computation, we have finite-state machines, Turing
> machines, languages with varying grammar extents (regular vs
> context-free
> and context-sensitive), lots of first-order languages and fragments,
> and
> many-sorted first-order languages.  the arrow language is designed to
> trascend these ideas.
> 
	Good.  They're a poor fit to computers, partially since they
model actual behavior so poorly and partially because they assume that a
computer can be infinite.

> the boundary of the arrow language needs to exceed
> all of these.
> 
	_Exceed_?

> a simple way to express this is that we have the goal of expressing at
> 
> least a countable number of types within this language, remembering
> of course that just about everything imaginable is available for 
> first-order analysis, even _without_ reflection.  instead 
> 
	That's a low goal.  I think you actually want to express all RE
languages, plus "some" languages (for the sake of proof only one) which
is known to be non-RE.

	And I think you're wasting your time, either way -- I find it
far more interesting to know what subset of RE languages my computer can
recognise.

	My friend is convinced that Rice's theorem, and thus the halting
problem, is invalid for actual computers, since they only have a finite
(but large) bumber of states ~= 2^(number of bits of memory and
registers).  His sketch of a proof for that is interesting (although
useless so far, since that's a LOT of states), but even theoretically
not useful, since few two computers will have the exact same set of
states.

	-Billy