Talk:Read-only Turing machine

Page started

Created article, as per request. Modelled on queue machine and pushdown automaton. Will finish tonight. SamuelRiv 14:51, 6 November 2007 (UTC)[reply]

Read-only isn't the same as 2DFA?

I think the opening phrase, which seems to indicate that "read-only TM" and "2DFA" are synonyms, is misleading. They are certainly not intensionally equivalent; the equivalence between the two in the case of 1-tape, read-only TMs is a theorem (not hard to prove, but still a theorem, not true-by-definition). And in the case of multitape read-only TMs the situation is much more complicated: with the input duplicated on 3 or more tapes, read-only TMs become Turing-complete, and with 2 tapes, it seems characterizing their power is an open question (https://cstheory.stackexchange.com/q/41920/129).

And for 2DFAs, it seems most of the content of this page is redundant with the page on 2DFAs: .

I'm not quite sure the best way to proceed here; maybe try to merge some of the content of this page on 2DFAs into https://en.wikipedia.org/wiki/Two-way_finite_automaton, and instead have this page discuss what I mentioned above, and for the 2DFA part just link to the 2DFA page? I don't want to clobber a bunch of other people's writing, but also I really think "read-only TM" is quite a different concept - both by definition and in terms of how it generalizes to multiple tapes - than 2DFA. — Preceding unsigned comment added by Joshuagmath (talk • contribs) 23:03, 21 September 2025 (UTC)[reply]

pushdown 2NFA and CFGs

It seems you don't need nondeterminism - a 2DFA with a stack should be able to parse context-free grammars, unless I'm missing something. Is that directly from your source? SamuelRiv (talk) 05:00, 26 November 2007 (UTC)[reply]

Mmm. The obvious approach I thought up doesn't work, since a 2DFA can't tell where it needs to backtrack to in general (for parsing, say, palindromes). Wagner and Wechsung doesn't actually say anything about the matter, except that "1:k-NPDA" (one-way nondeterministic pushdown automata with k heads) is a subset of "2:3k-DPDA" (two-way deterministic automata with 3k heads and a stack). For the k=1 case, they cite "Separating tape bounded auxiliary pushdown automata classes" 9th STOC (1977) by I H Sudborough. I'm just assuming they would have mentioned a better result if there were one (unless of course it was only developed after the book was published in 1986). Ben Standeven (talk) 05:15, 26 November 2007 (UTC)[reply]

A 2DFA with stack should be able to parse a palindrome - if we know the start and end points of our palindrome, we can easily calculate the length by pushing a counting marker for every other symbol from front to back, then popping every symbol from front to back (which leaves us at the halfway point), then pushing backwards from the halfway point to the front, and then popping if equal from the back. Another method is to push the first symbol and pop it when it repeats. If there's still string left after the repetition, run back to the beginning and push a "skip" marker" for every repeat of that symbol in the backwards run. Recurse.

This will work if we have regular or DCFGs before and after the palindrome, as we can parse both forwards and backwards and quickly get rid of any confusion those might cause. If there are two or more palindromes, it might be a problem... I'll have to think about it, but either way, I think the nondeterministic case is too general, and it's misleading to begin with because it's not equivalent to CFG machines - it's more powerful. SamuelRiv (talk) 06:27, 26 November 2007 (UTC)[reply]