16 votes
Accepted

A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

This is not a research-level question, but since the general level of interest seems high, here is an answer. I cannot guess from your question whether you're shooting for something that will result ...
Andrej Bauer's user avatar
  • 28.8k
4 votes

A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

Computing an 'infinite' object is usually defined based on Turing machines with one-way output tape; cmp. Section 2.1 in [Weihrauch'00]. This also asserts closure under composition. [Turing'36] first ...
Martin Ziegler's user avatar
3 votes

A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

The standard solution is to require write only tape if you want to use TTE. Obviously you can have RW work tapes. Another solution is information theoretic (domain theory) and says that you get ...
Kaveh's user avatar
  • 21.6k
2 votes

A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

One solution is what Radu GRIGore suggested, namely requiring that every digit becomes fixed after some (finite) number of steps. Of course, this comes with the practical issue that you never know ...
Christian Matt's user avatar
2 votes

A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

How about, $x\in[0,1]$ is computable if there is a TM $M$ which, on input $n\in\mathbb{N}$, prints the first $n$ digits of the decimal expansion of $x$ and then halts. Edit (13-Jul-2021). This ...
Aryeh's user avatar
  • 10.5k
1 vote
Accepted

Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain

I guess I have an alternative solution. Let $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$ be computable. Define $$ h(u) = v \mbox{ iff } f(u\Sigma^{\omega}) = \{v\} \mbox{ with $u$ minimal} $$ ...
StefanH's user avatar
  • 2,077

Only top scored, non community-wiki answers of a minimum length are eligible