question for physicists

[Kuciwalker]

Originally posted by KrazyHorse
The problem is that the definition should not be in terms of "numbers" (since there exists a definition which prints out the nth digit of ANY number in finite time).

What?

The definition should be in terms of DEFINITIONS. The space of definitions is far larger than the space of numbers, since there exist an uncountable number of definitions for every number, some of which may be uncomputable and some of which may be computable.

What? The definable numbers are a superset of the computable numbers, e.g. Chaitin's constant (the proportion of programs that halt).

[Kuciwalker]

Computer programs are by definition finite in length, btw.

[KrazyHorse]

Originally posted by Kuciwalker


Many irrational numbers are computable

All numbers are computable. Get your definition straight.

[Kuciwalker]

Not all real numbers are computable.

[civman2000]

Originally posted by KrazyHorse


The problem is that the definition should not be in terms of "numbers" (since there exists a definition which prints out the nth digit of ANY number in finite time). The definition should be in terms of DEFINITIONS. The space of definitions is far larger than the space of numbers, since there exist an uncountable number of definitions for every number, some of which may be uncomputable and some of which may be computable.

Unless you allow definitions to refer to arbitrary constants (and thus allow circular definitions), there are only countably many possible definitions, since a definition is a finite string in a finite (or countable) language.

[KrazyHorse]

Originally posted by Kuciwalker

Originally posted by KrazyHorse
The problem is that the definition should not be in terms of "numbers" (since there exists a definition which prints out the nth digit of ANY number in finite time).

What?

There exists a decimal representation of any number.

Duh.

[civman2000]

Originally posted by KrazyHorse


All numbers are computable. Get your definition straight.

What's your definition of "computable"?

[KrazyHorse]

Originally posted by civman2000

Unless you allow definitions to refer to arbitrary constants (and thus allow circular definitions), there are only countably many possible definitions, since a definition is a finite string in a finite (or countable) language.

Hmmm. You're right.

[civman2000]

Originally posted by KrazyHorse


There exists a decimal representation of any number.

Duh.

Yes, but there exist numbers such that no algorithm can write down their decimal expansions.

(Why? There are only countably many algorithms, and uncountably many reals.)

[Kuciwalker]

Originally posted by KrazyHorse
There exists a decimal representation of any number.

Duh.

For most it's non-terminating, and for most of those it cannot be generated by any computer program.

[KrazyHorse]

Originally posted by Kuciwalker
Not all real numbers are computable.

On the contrary, all real numbers are computable. What is undecidable is whether a given real number corresponds to a definition you've chosen to give to it...

[civman2000]

Originally posted by KrazyHorse


On the contrary, all real numbers are computable. What is undecidable is whether a given real number corresponds to a definition you've chosen to give to it...

Again, I don't understand the definition of "computable" you're using. The standard definition is that an algorithm (=Turing machine) can compute it in any of several equivalent senses (generate the binary expansion, generate the decimal expansion, tell you whether a given rational number is less than it, etc).

[Kuciwalker]

Originally posted by KrazyHorse
On the contrary, all real numbers are computable. What is undecidable is whether a given real number corresponds to a definition you've chosen to give to it...

This is incorrect. Or rather, there are infinite sequences of numbers which cannot be generated by any algorithm, and the question of whether a given sequence matches one of those is also undecidable.

[KrazyHorse]

Originally posted by civman2000

Yes, but there exist numbers such that no algorithm can write down their decimal expansions.

(Why? There are only countably many algorithms, and uncountably many reals.)

Ah. I see. I should have read the definition more carefully.

[KrazyHorse]

Originally posted by Kuciwalker
Computer programs are by definition finite in length, btw.

This is the part I was missing...