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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ You can give it any individual natural number, so the machine accepts infinitely many inputs, but you cannot feed into it an infinite string. $\endgroup$– André NicolasAug 31, 2014 at 6:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Sep 2, 2014 at 10:36
-
$\begingroup$ I was thinking of a following decision problem: given any set as input, can a turing machine decide in finite time if the set is finite or infinite? $\endgroup$– AdamSep 2, 2014 at 15:29
-
2$\begingroup$ @Adam: the answer is that it cannot. Let $A$ be a finite set - then the machine would have to stop after a finite number of steps and say that $A$ is finite. Leaving unchanged the part of the tape the machine sees during that finite number of steps, we can then add infinitely many new numbers to $A$. The machine will also claim, incorrectly, that the resulting set is finite. (This is exactly the sort of problem where the input may naturally be infinite - so we would usually put the input on a separate tape from the work tape of the machine.) $\endgroup$ Sep 2, 2014 at 16:33