🚀 go-pugleaf

On 04/05/2011 02:58 PM, Newberry wrote:
> On Apr 5, 8:40 am, Ralph Hartley<hart...@aic.nrl.navy.mil>  wrote:
>> On 03/30/2011 10:21 AM, Daryl McCullough wrote:
>>
>>> Here are two ways to think about computability for
>>> reals: (Off the top of my head, this is probably not
>>> the way that computability theorists would think of it).
>>
>>> (1) If you view reals as equivalence classes of [sequences of] rationals,
>>> then you can define a function f from reals to reals to be
>>> computable if there is a corresponding computable function
>>> F from rationals to rationals such that whenever
>>> limit of q_0, q_1, ... = r
>>> then
>>> limit of F(q_0), F(q_1), ... = f(r)

>> The extrapolation from the previous post would be to define a real as a
>> *particular* sequence of rationals.
>>
>> If we require that the representation of a rational (as a real) be a
>> constant sequence, then arithmetic on rationals would be computable.
...
>> Given a program that outputs a decimal expansion, it is undecidable if
>> the resulting number is rational or not, so there are computable (in the
>> normal sense) real numbers who's canonical sequence is not computable.
>
> Isn't the program that outputs a rational expansion going to have an
> infinite loop that you are going to recognize as such?

No, and no.

A program that produces a sequence is normally thought of as one that 
takes an index i as input and outputs the ith member of the sequence. By 
definition such programs halt for all inputs. Other definitions can be 
reduced to that. If you want a program that runs forever writing terms 
on the tape separated by delimiters (e.g. for 1/3 "2/3, 5/6, 8/9, 11/12 
...") you can write that using the normal definition (which writes 
(3i-1)/3i on the tape) as a subroutine.

But even if there were infinite loops involved, you aren't always going 
to recognize them. That is one of the first known undecidable problems.

Ralph Hartley