[QUOTE=R.D. Silverman;111658]
Another example: We know that almost all real numbers are Transcendental.
The subset that is algebraic is countable, while the reals are uncountable.
Thus, the algebraic numbers have density 0 in the reals. But knowing that
almost all numbers are transcendental does not help us prove that e.g.
The Euler-Mascheroni constant is.[/QUOTE]Even worse: almost all numbers are not computable by a Turing machine but, on the C-T hypothesis, we can't give even a single example!

Paul

[QUOTE=xilman;111663]Even worse: almost all numbers are not computable by a Turing machine but, on the C-T hypothesis, we can't give even a single example!

Paul[/QUOTE]

Sure we can. One such example is:

For a given finite state machine, what is the probability that a random input
tape will halt?

[QUOTE=R.D. Silverman;111664]For a given finite state machine, what is the probability that a random input
tape will halt?[/QUOTE]

Your Turing machine still uses a tape drive?!! You should consider upgrading.

[Fry's has specials on TMs nearly every week, you just need to be careful to read the fine print, send any rebate form in promptly, and make sure to save a copy of the latter in case it gets "lost" in the mail, as rebate forms appear to be distressingly prone to doing, similarly to insurance claim forms.]

[QUOTE=R.D. Silverman;111664]Sure we can. One such example is:

For a given finite state machine, what is the probability that a random input
tape will halt?[/QUOTE]Fair enough --- my statement was too sloppily phrased and should not have used "give". A more accurate verb would be "compute".

Even this statement needs tightening up a little. For instance, e is transcendental but we can compute it to an arbitrary but fixed precision and do so efficiently. Non-computable numbers are, by definition, non-computable.

Paul

[QUOTE=ewmayer;111672]Your Turing machine still uses a tape drive?!! You should consider upgrading.

[Fry's has specials on TMs nearly every week, you just need to be careful to read the fine print, send any rebate form in promptly, and make sure to save a copy of the latter in case it gets "lost" in the mail, as rebate forms appear to be distressingly prone to doing, similarly to insurance claim forms.][/QUOTE]

This is terrific! What is the price on a standard NDTM??? I'd like to buy one.

[QUOTE=xilman;111663]Even worse: almost all numbers are not computable by a Turing machine but, on the C-T hypothesis, we can't give even a single example!

Paul[/QUOTE]

Even weirder is the fact that if we work outside of the system, there can be an 'equal' number of non-computable numbers as there are computable ones. In other words, there is a countable model for the (standard) reals. And, of course, one could just work with the "computable" reals in the first place depending on which model one favors. :smile: