Can input to a Turing machine be of infinite length?

Considering only the alphabet Σ={0,1}, the strings which can be given as input to the Turing machines are from the set Σ. 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 ?

Answer

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.

Attribution
Source : Link , Question Author : sashas , Answer Author : Yuval Filmus

Leave a Comment