Tag Info

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 ...
• 29.2k

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 ...

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 ...
• 21.7k

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 ...

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 ...
• 10.6k
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}$$ ...
• 2,077

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