I have a question about Turing machines. Is it allowed to give them infinitely long input? Can I give a Turing machine for example all of natural numbers as input?
2026-03-27 18:25:53.1774635953
infinitely long input for a turing machine
860 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
The question is what you want to do with the Turing machine.
The tape on a Turing machine is infinite. If you want, you can put anything you like on the tape before running the machine. The machine has to do something when you run it, regardless what is on the tape.
However, the reason we talk about "inputs" is that we use Turing machines to compute functions. If you are using a Turing machine to compute a function from the natural numbers to the natural numbers, it only matters what happens when you give the machine a natural number as input. In this setting, it makes no difference what the machine might happen to do if you ran it with an infinite "input" on the tape, because that input would not be a natural number.
If we are using a Turing machine to compute some other functions - e.g. a function from the reals to the reals - then we must have a way to give the Turing machine an infinitely long input, because few real numbers can be represented with only a finite amount of information. In this case, we usually include a separate infinite tape to hold the input, along with a tape for the machine to use for scratch work and a tape for the machine to use to write its output.