programming language P

  Consider the following simple programming language P — which can be used to write programs to decide membership in languages L ⊆ Σ ⋆ . As usual, it is assumed that ⊔ ∈/ Σ. Programs written in this language access a single infinite array A (with registers, or “containers” A[i] for i ∈ N) that can store symbols in an alphabet Γ resembling the tape alphabet of a Turing machine: Σ ⊆ Γ, ⊔ ∈ Γ, and Γ can also include a finite number of additional symbols that are not in Σ ∪ {⊔}. When a program is executed on an input string ω = σ0σ1 . . . σn−1 ∈ Σ ⋆ with length n, the register A[i] initially contains σi , for 0 ≤ i ≤ n − 1, and A[i] contains ⊔ if i ≥ n. The program also access a single integer variable i, whose initial value is 0 and whose value is never negative.