If your programming language of choice has no arrays (like most of the languages implemented in one of the many, many, many "How to write your own interpreter/simple compiler" tutorials out there) but supports variables, then you can use this technique to kinda implement them anyway, Okasaki-style:

    var arr0, arr1, arr2, arr3, arr4, ..., arr65535 : int;

    func get_arr(index: int): int {
        if index < 0 or index > 65535 { exit(); }
        if index < 32768 {
            if index < 16384 {
                if index < 8192 {
                    ...
                        if index < 2 {
                            if index < 1 {
                                return arr0;
                            } else {
                                return arr1;
                            }
                        } else {
                            if index < 3 {
                                return arr2;
                            } else {
                                return arr3;
                            }
                        }
                    ...
                }
                else {
                    ...
                }
            } else {
                ...
            }
        } else {
            ...
        }
    }

    proc set_arr(index: int, value: int) {
        if index < 0 or index > 65535 { exit(); }
        if index < 32768 {
            if index < 16384 {
                if index < 8192 {
                    ...
                        if index < 2 {
                            if index < 1 {
                                arr0 = value;
                            } else {
                                arr1 = value;
                            }
                        } else {
                            if index < 3 {
                                arr2 = value;
                            } else {
                                arr3 = value;
                            }
                        }
                    ...
                }
                else {
                    ...
                }
            } else {
                ...
            }
        } else {
            ...
        }
    }

It even has O(log n) access time which is actually the same complexity as accessing a RAM by a pointer anyway! Just replicate this code for any array variable you need to simulate and pre-allocate enough of the memory, it's totally free with that .bss trick anyhow.

So technically, languages without arrays are about as Turing-complete as those with limited-size pointers/array indices (funnily enough Brainfuck — where the pointer is invisible to the progammer — actually is Turing-complete).