Skip to main content
15 events
when toggle format what by license comment
Jan 30, 2017 at 11:20 answer added Martin Ziegler timeline score: 4
Jan 27, 2017 at 12:35 vote accept StefanH
Jan 27, 2017 at 10:43 comment added Radu GRIGore Also, I believe I'm not saying anything different from what cody already said, but seemed to be somewhat ignored.
Jan 27, 2017 at 10:41 comment added Radu GRIGore @SashoNikolov: Your quote is not from the definition, but from a comment that follows. In interpreted that comment as an attempt to relate the definition given above to the usual definition. In the definition given above, I interpreted "infinity" in the sense of a limit. The way I understand the original question is this: "Does it make a difference if we require or not the stability time to be computable?" Andrej Bauer seems to answer this question with "yes", if I understand correctly. (He also answers many other questions ...)
Jan 27, 2017 at 6:33 answer added Andrej Bauer timeline score: 16
Jan 27, 2017 at 6:19 review Close votes
Jan 27, 2017 at 23:46
Jan 27, 2017 at 3:08 answer added Kaveh timeline score: 3
Jan 26, 2017 at 21:41 answer added Christian Matt timeline score: 2
Jan 26, 2017 at 19:26 comment added Sasho Nikolov @RaduGRIGore what you wrote is well-defined, but the OP says "How can anybode read off one digit of x, as we cannot be sure that it is definite, i.e. it could be changed infinitely often in the run of the machine." This does not sound like your definition in which every digit "settles" after finite time. Maybe Stefan can clarify if this is what he meant.
Jan 26, 2017 at 16:57 comment added Radu GRIGore The definition seems well-formed to me. Spelled out: there exists a TM $T$, such that for all $n\in\mathbb{N}$ there is a $t\in\mathbb{N}$ such that for all $t'\ge t$, if you run $T$ for $t'$ steps, then the first $n$ symbols on the tape are the first $n$ bits of $x$.
Jan 26, 2017 at 15:41 comment added StefanH For each specific instance of time, the machine has written something (or even nothing) on its tape; so the output is well-defined. Imagine pause the machine and look whats written. But the problem is that we can never be sure if the written digits are the correct ones, as at a later instance of time they might get replaced. That quite different than what Aryeh wrote, as in his definition we know at a certain instance of time (i.e. when the machine finishes on processing $n$) that we have a correct digit of the result. Does this make sense? The result would be valid if we wait infinitely long.
Jan 26, 2017 at 15:07 comment added Sasho Nikolov I don't understand the definition. What is the output of a machine with infinite running time? And what is actually your question? The standard definition of a computable real is what Aryeh wrote below.
Jan 26, 2017 at 14:03 comment added cody The definition is fine as-is, which is just "eventually the TM will write the correct digit of $x$ to the right place". I agree that one might desire a more workable definition, in which we know when the correct digit is written. Typically you would ask for a computable function $f$ which, given $n$, gives the number of steps $f(n)$ after which the $n$-th digit does not change. One might call this a computable rate of convergence.
Jan 26, 2017 at 14:01 answer added Aryeh timeline score: 2
Jan 26, 2017 at 13:08 history asked StefanH CC BY-SA 3.0