Talk:Linear bounded automaton

Origin and definition of LBA

From "The LBA Problem And Its Importance In The Theory of Computation", by J. Hartmanis and H. B. Hunt, III, p.2, in "Complexity of Computation", SIAM-AMS Proceedings, Vol. 7, Providence, RI: American Mathematical Society, 1974, R. M. Karp (Editor):

"Linear bounded automata were first defined and investigated by [the mathematician] John Myhill in 1960. As Myhill points out, the definition of a linear bounded automaton was motivated by an observation made by Rabin and Scott about two-way finite automata with erasing. [...] The observation was [...] that the equivalence problem for these automata is recursively undecidable."

Recursive undecidability is, of course, a topic in computability theory. This places in doubt the following quote from the notes of F. D. Lewis, which I removed from the article:

"Linear bounded automata were originally developed as models for actual computers rather than models for the computational process. They have become important in the theory of computation even though they have not emerged in applications to the extent which pushdown automata enjoy. Here is the motivation for the design of this class of machines. Computers are finite devices. They do not have unending amounts of storage like Turing machines. Thus any actual computation done on a computer is not as extensive as that which could be completed on a Turing machine. So, to mimic (or maybe model) computers, we must restrict the storage capacity of Turing machines."
-- r.e.s. 16:38, 22 September 2009 (UTC)

F.D.Lewis is a professor worked in computer science area. So I assumed his opinion is expert. Here are two other quotes to support it.

"...For instance, the model (LBA) applies to a personal computer where the input is supplied on a floppy disk. The abstraction is consistent with this example in that the input medium also serves as a storage medium since it can be written to as well as read." – Section LBA, from the book "Formal models of computation: the ultimate limits of computing".

"A form of deterministic LBA was first studied by Myhill in an attempt to find models of computation more realistic than the completely general Turing machines. (A deterministic LBA is logically equivalent to an ordinary stored-program computer with finite memory.)" – p. 53, book "Concise encyclopedia of computer science".

As to your quote I have to repeat it without removed parts to allow more objective interpretation. "As Myhill points out, the definition of a linear bounded automaton was motivated by an observation made by Rabin and Scott about two- way finite automata with erasing. This remark appeared in a technical report on which the well-known Rabin and Scott paper "Finite Automata and their Decision problems" was based. The observation was that two-way finite automata, which can erase input symbols, can accept non-regular sets and that the equivalence problem for these automata is recursively undecidable." Now that does not "place in doubt" the aforementioned quote.

Last thing. Your LBA definition with infinite tape is less clear than the one you removed and incorrect, in my opinion; because for an LBA, the tape is the input, and cannot be infinite since the input (and any input) is finite. --Oleg 02:25, 23 September 2009 (UTC)

It's fine that you filled out the ellipses in the quotation, because I wouldn't want anyone to think something relevant had been omitted (and it had not been, imo). Sometimes experts in their field are not authorities in the history of their field. The doubt concerning the Lewis quote stems from the fact that, contrary to what Lewis wrote, Myhill is said to have been concerned with computational models, abstract machines that are language acceptors. This directly contradicts the remark by Lewis that LBAs were "originally developed as models for actual computers rather than models for the computational process". Interestingly, the very encyclopedia quotation that you just posted also contradicts Lewis, as it states explicitly that "A form of deterministic LBA was first studied by Myhill in an attempt to find models of computation more realistic than the completely general Turing machines."

As to the quotes you posted that refer to machines with finite memory, this must obviously be understood in the finite-but-unbounded sense, which posits unlimited memory. A single LBA is by definition capable of taking arbitrarily large inputs, even though the accessible memory is finite for each input. Some authors call this type of memory finite-but-unbounded, others call it infinte; in any case, it is unlimited. I edited the definition in the article (which is the same as the Wikipedia definition) in order to clarify this.

Your "last thing" reflects a misunderstanding about what comprises an LBA. A single LBA is an abstract machine that takes arbitrarily large inputs, for which it requires a tape with an unlimited number of cells. You may not like this fact, but it's part of the definition (including the one at Wikipedia, of course). This is necessary for an LBA to be a language acceptor, such that its input may be any word in an infinite set of words.-- r.e.s. 15:29, 23 September 2009 (UTC)

More about that "last thing" ... The tape is not the same as its content. Aside from this, the issue has to do with whether there is one infinite-length tape or an infinite set of finite-length tapes. These are equivalent models. In both cases, the number of cells accessible by an LBA is infinite, because a single LBA takes arbitrarily large inputs. (Changing the input does not change the LBA.) All of the infinitely many cells, whether they're on one infinite tape or on all the finite tapes together, are accessible to a single LBA, because each cell is made accessible by some input to the LBA.

-- r.e.s. 17:07, 23 September 2009 (UTC)

I have built an LBA machine with the tape having exactly 100 cells. Is it an LBA? Yes. Does it have infinite memory? No. Can it interpret another LBA in polynomial order? Yes.

While copying the LBA definition from wikipedia, I think, you forgot to include the statement: "This limitation makes an LBA a more accurate model of computers that actually exist than a Turing machine in some respects."

Now about the infinite tape. Here is a quote from the book "Theory of Computer Science: Automata, Languages and Computation":

"A linear bounded automaton is a nondeterministic Turing machine which has a single tape whose length is not infinite but bounded by a linear function of the length of the input string."

By the way, my computer, which I use to type this message, has the infinite memory. I have not switched this memory on yet. So for this moment my messages are finite... --Oleg 05:07, 24 September 2009 (UTC)

First ... An LBA is an abstract machine. You may call your physical machine an LBA, but it would be imprecise and only "loosely speaking". About the remark you mention ... that's not part of the definition, which is why I included nothing like it -- I was focussed on getting the definition right. Although I do not suggest copying material from Wikipedia, I agree that something like that remark would be well-paced in the introduction.

Second ... Notice that in your latest quote, the "single tape whose length is not infinite", nevertheless has unlimited length, because it takes inputs of arbitrarily large size, as an LBA must do. That author is evidently referring to the finite-but-unbounded concept in a model with a variable-length tape, in which the tape is finite at every step, but its length is adjusted as required for each of the infinitely many inputs. It's a matter of terminology whether this constitutes one tape of variable length or an infinite set of tapes of various lengths. Please take a moment to grasp this. It is nothing new. These two alternative forms of description -- infinite vs. finite-but-unbounded -- are often used for other abstract machines as well, including Turing machines. I have used the word "unlimited" to refer to the situation in both cases.

-- r.e.s. 13:59, 24 September 2009 (UTC)

I've added a History section to the article, and inserted what I think are exceptionally relevant quotes from the Rabin and Scott paper. The earlier quote was to the effect that Myhill's introduction of LBAs was motivated by a particular undecidability problem concerning finite automata, as noticed by Rabin and Scott. However, that is apparently something much more specific than what these quotes discuss. -- r.e.s. 17:46, 24 September 2009 (UTC)

In my humble opinion, the original article here was simple, clear, correct, and different from Wikipedia page. If you want to be 100 percent correct why you did not copy the LBA definition from a textbook?

I will agree with you about the infinite tape if you can find any quote or at least another person’s opinion which states that "The tape itself has infinite length in order to accomodate arbitrary inputs" as you have written in the article. Because I do not believe it is true – in all definitions I have seen an LBA is always defined as a machine with a bounded tape and never seen that the same LBA has "to accommodate arbitrary inputs".

To allow pluralism it would be fair to add to the article all quotes above, including F.D.Lewis’s. --Oleg 00:37, 25 September 2009 (UTC)

"Arbitrary inputs" in the article meant "inputs of arbitary size", but I don't think your objection is about that quibble. Every LBA is a language acceptor, which requires it to take as input each of the infinitely many words defined on a given alphabet; i.e., a single LBA must take infinitely many inputs, ranging over all finite sizes. This is standard usage. In regard to this, and the use of the terminology of an infinite tape in the defintion of an LBA, here are just a few of the many sources:

PlanetMath: linear bounded automaton (see also the definition of a TM).

These use the definitions given in the book by J.E. Hopcroft, J.D. Ullman, "Formal Languages and Their Relation to Automata", Addison-Wesley, (1969). Notice that a TM is defined to have a tape of infinite length, and that a single LBA takes inputs of every finite size, with the accessible region of the tape restricted according to the input size.

I concede that my doubts about the Lewis quotation, in regard to what originally motivated development of LBA, may not have been reason enough to remove it from the article. If you put the Lewis quotation back, I suggest that it be shown as such, with proper attribution to him in the article.

-- r.e.s. 02:17, 26 September 2009 (UTC)

<--

You are repeating your interpretation. But I asked you to give at least one quote to support your view on LBA. You say "a single LBA must take infinitely many inputs", "This is standard usage", "here are just a few of the many sources". You give two references with no quotation.

PlanetMath: linear bounded automaton: says: "A linear bounded automaton, or LBA for short, is a restricted form of a non-deterministic Turing machine with a single tape and a single tape head, such that, given an input word on the tape, the tape head can only scan and rewrite symbols on the cells occupied by the initial input word. Formally, a linear bounded automaton is... ". Not a word about infinite tape.

The book by J.E. Hopcroft, J.D. Ullman, "Formal Languages and Their Relation to Automata", Addison-Wesley, (1969) Chapter 8, page 115 says "A linear bounded automaton (lba) is a nondeterministic single-tape Turing machine which never leaves those cells on which the input was placed. Formally, a linear bounded automaton is denoted...". Neither a word here.

Now I think that you are confusing an LBA with a Turing machine, which indeed has the infinite tape. Otherwise why would you refer to it in your message above: "see also the definition of a TM" and "TM is defined to have a tape of infinite length"? --Oleg 04:24, 26 September 2009 (UTC)

Your lack of comprehension is disheartening, to say the least. By giving online references (which you seem unable or unwilling to understand), I am not merely repeating myself. You say the LBA link has "not a word about infinite tape", when it defines an LBA in terms of a TM with infinite tape. The LBA's input is described as being given on such a tape. I went to the trouble of providing the TM link referenced in the LBA definition, just to make this point clear. Please read the LBA link again, and follow its links to the definintion of TM; unless you do this, naturally you won't understand the LBA definition. Do you understand now?

The main issue here is not whether the LBA definition uses the standard TM terminology of an infinite tape; rather, it's that a single LBA must accomodate inputs of arbitrary size. You've never responded to this point except to say that you've "never seen that the same LBA has "to accommodate arbitrary inputs". Please read the LBA link again, and note the statement that "A language is context-sensitive iff it can be accepted by an LBA." Do you understand, now that you have seen it?

-- r.e.s. 13:23, 26 September 2009 (UTC)

Lets try a simpler question. Can you provide a quote supporting that "a single LBA must accommodate inputs of arbitrary size" without your interpretation? Please, yes/no answer.

My misunderstanding of LBA is the following. An LBA is defined as a theoretical model, which has a finite bounded input on its finite bounded tape. It can accept a word of a context-sensitive language, which is the finite input if provided. An LBA is not a computer solving different tasks and processing different inputs. It is a model with the only purpose to analyze its computational power. Hence it needs only one finite and bounded input, not many. Think about it.

If I imagine an LBA with a tape of 100 cells, is it an LBA? Please, yes/no.

--Oleg 02:36, 27 September 2009 (UTC)

You are totally ignoring the main quote I just gave, together with the question I asked about it. Again, please try to understand this: "A language is context-sensitive iff it can be accepted by an LBA." Please think about an LBA that accepts the infinite context-sensitive language {aⁿ: n is a prime number}. Now please ask yourself how many input-sizes this single LBA must take. Please think about whether this single LBA "needs only one finite and bounded input", as you claim. Even more to the point, every single LBA is ordinarily regarded as a language acceptor, which requires it to take as input every one of the infinitely many words on a specified finite alphabet. Please, please think about this before replying.

-- r.e.s. 12:26, 27 September 2009 (UTC)