23
$\begingroup$

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 ?

$\endgroup$
20
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Finishing the calculations in finite time while the input is infinite seems like a tough challenge. $\endgroup$ – Mast Oct 18 '15 at 17:05
  • 4
    $\begingroup$ @Mast Not necessarily. You just can't afford to read the entire input. $\endgroup$ – Yuval Filmus Oct 18 '15 at 17:32
  • 1
    $\begingroup$ @JulesMazur The keyword is hypercomputation. $\endgroup$ – Yuval Filmus Oct 18 '15 at 17:35
  • 3
    $\begingroup$ @JulesMazur You don't necessarily need any hypercomputation. The program can just keep writing to an output tape, and the result converges to an infinite string like in a Type II Turing Machine. $\endgroup$ – man and laptop Oct 18 '15 at 18:28
  • 1
    $\begingroup$ I think you get into difficulty if you allow infinte strings as input. In particular the set of inputs are no longer countable, which breaks several proofs. $\endgroup$ – Taemyr Oct 19 '15 at 10:10
16
$\begingroup$

That's one of the features of Type 2 Turing Machines. They're used, among other things, to analyse the computability of functions between real numbers. Even more interestingly, they're used to analyse the computability of operators like integration.

Cool fact: Exact numerical integration is computable.

$\endgroup$
5
$\begingroup$

To answer the question "does it make sense", this can even be useful if you consider Turing machines that run in finite time.

Specifically, this is a very useful way to think of prefix-free Turing machines. These are machines whose set of halting inputs is prefix-free; that is, no input that causes the machine to halt is the prefix of another. These are equivalent in power to regular Turing machines, but only if we allow the Turing machine to decide its own halting inputs: ie. the user has no idea what inputs the machine will halt on (and this is an undecidable property).

One way to see this is as a regular Turing machine with a one-way infinite input tape with a tape head that can't move back. The user fills the tape with bits and runs the machine. This is by definition a prefix-free Turing machine. If the machine halts, it must have read only a finite number of bits, and no prefix of that part of the tape can be a program, or the machine would have halted there instead.

This is a good way to talk about computable probability distributions: the user fills the tape with random bits (the machine's source of randomness), and the machine spits out a random bitstring. The set of all such Turing machines corresponds to the set of computable distributions (specifically the lower semicomputable semimeasures).

The advantage of the infinite input is that we don't have to specify what the machine does if we give it a prefix of a halting program, ie. the machine tries to read beyond the end of the input we've given it.

$\endgroup$
2
$\begingroup$

Even if you do not have such a tape, you can employ another Turing machine to produce it.

A Turing machine has an access to the empty, but infinite data tape (or some sources says "the machine just has a small tape factory built in"). So it can initialize it with some programmable pattern of data, and then the tape could be consumed as an input of another Turing machine.

Of course, if your content is such that no algorithm could be defined how to produce it, such content cannot be created by Turing machine.

$\endgroup$
  • 6
    $\begingroup$ I'm not sure how this answers the question. In any case, not all infinite sequences can be generated by Turing machines, since there are uncountably many infinite strings over any alphabet with at least two symbols, whereas there are only countably many Turing machines and countably many finite inputs to seed them with. $\endgroup$ – David Richerby Oct 19 '15 at 7:41
2
$\begingroup$

There are some cases where infinite input can be considered and reduced to the action of a "standard" Turing machine. For example, consider an infinitely repeating finite pattern specified on the input. A Turing machine can be created that keeps track of how much of this infinite pattern has been modified by the current actions of the tape head using a finite amount of memory/ tape storage. In other words, it "equivalently simulates" an infinite size pattern on the tape.

Another case where "infinite input" has been considered is the analysis of the Turing equivalence/ completeness of cellular automata. in a complex proof, Cook introduced a concept now referred to by some as "weak Turing equivalence" in converting CA 110 rule operations into Turing machine operations that start on an infinite-specified initial tape but with (repeating) finite-size patterns.

$\endgroup$
  • 1
    $\begingroup$ The terms "infinite input" and "finite encoding of an infinite object" are clearly distinct, and elementary (every infinite regular language with its minimal DFA is an example). They should not be confused here. $\endgroup$ – Raphael Oct 19 '15 at 6:26
  • 2
    $\begingroup$ yes DFAs can be used for the encoding described. as sketched out a tape with a finite encoding of an infinite length string (via repeating finite patterns) is both different/ similar in capability to a tape with only finite strings. $\endgroup$ – vzn Oct 19 '15 at 14:56
1
$\begingroup$

In formal languages, a string is, by definition, a finite sequence of symbols. A classic Turing Machine has an infinite tape with a finite input string. As such, while there is no limit to how long the input can be, it cannot be infinite.

Having said that, there are many alternative machines that work similarly to a TM but with infinite input sequences.

Whether it makes sense to have input of infinite length depends on the purpose. Strictly within the context of Turing Machines, it makes no sense (since it is not possible), but in the context of Turing-like Machines, it does make sense and it has many applications.

$\endgroup$
  • 4
    $\begingroup$ It's perfectly possible to have infinite strings. Indeed, there's a whole branch of automata theory that deals with this exact situation. And, given that the only change needed to the definition of Turing machines to allow them to deal with infinite inputs is to delete the condition that says the input must be finite, I disagree that it "makes no sense" to talk about Turing machines and infinite strings. $\endgroup$ – David Richerby Oct 18 '15 at 17:47
  • 1
    $\begingroup$ @DavidRicherby: we seem to be in agreement. Feel free to let me know how I can rephrase the last paragraph to make it more clear that it is only strictly in the context of original, classic, unadulterated Turing Machines (where the inputs are by definition finite), that it makes no sense to talk about infinite length input. As soon as we delete the condition, it's no longer strictly a TM, but (what I termed) a Turing-like Machine. $\endgroup$ – everybody Oct 19 '15 at 22:13
  • 1
    $\begingroup$ I disagree that the device stops being a Turing machine just because you start it with infinite stuff on the tape. The machine is still the same machine; you just changed the initial conditions. The definitions of how Turing machines relate to langauges of finite strings (e.g., decidable or semi-decidable langauges) are in terms of finite inputs but that doens't mean the machine requires it. Similarly, your computer wouldn't stop being a computer if you put an infinite pile of CDROMs next to it. $\endgroup$ – David Richerby Oct 19 '15 at 23:44
  • 1
    $\begingroup$ @DavidRicherby Well, technically a Turing machine is a machine that takes finite input. If you change this restriction in the definition, you define something else. The idea behind computing is still the same, in some sense, but how do you express complexity now? Very different issues. $\endgroup$ – Raphael Oct 20 '15 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.