Technically everything that a computer does can be simulated using any medium, pen and paper for example, or rocks and sand (relevant XKCD).
As for actually creating the parts needed, well a modern computer is just a very advanced Turing Machine which only requires 3 parts to operate: a tape for storing memory, a read/write head for reading/altering the data in memory, and a state transition tape to instruct the head to move left/right on the memory tape.
The memory and state transition tapes themselves can be anything, even a pen or rocks as in the previous examples. The read/write head could be anything as well. In previous iterations of computers we used the state of and turning on and off of vacuum tubes as a read/write head.
So conceptually, any time that humans were intellectually capable of reasoning out the logic. Their computer would just run much slower and be less useful the farther back in time you go.