(Particular, individual) regular expressions can be implemented with O(1) space. Regular expressions can do lots of useful things.

This is incorrect, under deliriums pedantic interpretation of space complexity. Some regular expressions require one to accept a certain number of examples of a character. This means that storage space for the count is required, which scales logarithmically in the count.

This is why my comment began with the words "particular, individual". A regex like (1{5}0{3})\* can be implemented in constant space, but a language like

    matches(n, m, string):
        return matches((1{n}0{m})\*, string)

cannot.

Just think about it -- the former is just a DFA, and so of course you can do it in constant space (provided your input stream is abstracted away, or you use a TM.

int x = 0;

x++;

would be two examples.

How many times would you need to execute line 2? The more times you need to do this, the more values x needs to be able to represent. So running x++ in O(n) time means the space needed to store the accumulation grows as O(n log_2 n)... under delirium's "pedantic" interpretation of space complexity.

Unknowingly you have allowed me to stumble onto an actual algorithm with O(1) storage pace, that is, one where there are n numbers, and you want to calculated the modulo-k sum. In this case, the algorithm scales logarithmically in the constant parameter k, but O(1) in n.