  We show how the spectrum of normal discrete short-range infinite-volume
operators can be approximated with two-sided error control using only data from
finite-sized local patches. As a corollary, we prove the computability of the
spectrum of such infinite-volume operators with the additional property of
finite local complexity and provide an explicit algorithm. Such operators
appear in many applications, e.g. as discretizations of differential operators
on unbounded domains or as so-called tight-binding Hamiltonians in solid state
physics. For a large class of such operators, our result allows for the first
time to establish computationally also the absence of spectrum, i.e. the
existence and the size of spectral gaps. We extend our results to the
$\varepsilon$-pseudospectrum of non-normal operators, proving that also the
pseudospectrum of such operators is computable.
