1
vote
Definition of semi-infinite tape Turing machine
There are several ways how the definition can go. Besides having a special symbol marking the boundary of the tape as in GKxx’s answer, some possibilities are:
Define one step of the computation of ...
- 2,222
1
vote
Accepted
Definition of semi-infinite tape Turing machine
I think the definition must be attached with a definition of the language that it accepts. I come up with a definition similar to that of LBA (linear bounded automata):
A semi-infinite tape Turing ...
- 126
1
vote
Find an s-grammar for L={a^nb^2n : n>=2}
First, there is the problem of the empty word. For that, just consider:
$S\to aaAbbbb\mid aabbbb$
$A \to aAbb \mid abb$
There is still the problem of multiple rules from the same variable beginning ...
- 16.9k
Only top scored, non community-wiki answers of a minimum length are eligible