Computability
I recently mentioned the fact that some (actually, almost all) functions (and real numbers) are not computable by a Turing machine. I gave some very familiar examples: the Busy Beaver function, the Entscheidungsproblem or halting problem, and Chaitin's omega.
One thing that bothers me is that all of these examples construct an uncomputable function or constant by reference to the properties of activities of Turing machines themselves: that is, they are all functions describing the (hypothetical) behavior of other computers or programs. All of these uncomputable things relate to attempts to summarize or predict the behavior of other computations or sets of computations.
There is a sense in which this feels like a gimmick, like these problems were devised or mentioned only in order to set up the diagonalization arguments, like these problems would be relatively unlikely to arise "naturally" in an area of mathematics or thought other than the problem of computability itself. Does anyone know an example of a function or number that is known to be formally uncomputable by a Turing machine but whose definition or at least motivation doesn't involve computation or computability?
- Links from other weblogs:
Fri Mar 02 14:33:09: はじめます from サプリのオススメ通販情報で健康一直線！
例の納豆のやらせ問題…結構話題になりましたよね。
スーパーからは納豆が消えたらしいですし。
とはいえ、納豆って普通に良いものですし、毎日食べたら体にいいはずなんですFri Mar 30 23:09:41: mature big boobs from mature big boobs
mature big boobs
