HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Can input to a Turing machine be of infinite length?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
caninfinitelengthinputmachineturing

Problem

Considering only the alphabet $\Sigma = \{0,1\}$, the strings which can be given as input to the Turing machines are from the set $\Sigma^{*}$. But does it make sense for the input to be an infinite binary string ? For example if a Turing machine accepts all strings starting with a 0, does a binary string of infinite zeros also belong to the language accepted by the Turing machine ?

Solution

There is no problem in running a Turing machine on a tape initialized with an infinite string, although this is not usually considered. We still need the machine to terminate in finite time, though. There are also notions of infinite-time computation, which may be appropriate here.

Context

StackExchange Computer Science Q#48381, answer score: 22

Revisions (0)

No revisions yet.