Re: OPPOSITE OF all coin sequences are computable to infinite length ?

From: Tim Peters (tim.one_at_comcast.net)
Date: 01/07/05 

Date: Thu, 6 Jan 2005 23:42:21 -0500

[Daryl McCullough]
>> To say that an infinite coin sequence cs is computable to infinite
>> length is to say that there is a single computable function f that
>> can compute all the places in cs. The negation is this:
>>
>> Every computable function f computes only finitely many places in cs.

[Robert Kolker]
> What about alternating heads/tails forever. That is a trivial function
> which computers all the places. Odd places have heads, even places have
> tails.

Then that's an examploe of an infinite coin sequence that is "computable to
infinite length" under Daryl's definition (which is a good definition, if
you ask me). Daryl didn't (and wouldn't) claim that no such seqeuence
exists.

OTOH, to |-|erc's question:

> all coin sequences are computable to infinite length ?
>
> What is its negative proposition?

Daryl probably should have gone on to preface his answer ("Every computable
function f ...") with "There exists an (at least one) infinite coin sequence
cs such that [every computable function f computes only finitely many places
in cs]". And then go on to define the domain and range more carefully, etc.
But one suspects that the niceties of rigor wouldn't be of any actual help
in this thread <wink>.

Relevant Pages