patternMajor
Can input to a Turing machine be of infinite length?
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.