Modern computing systems based on the von Neumann architecture are built from silicon complementary metal oxide semiconductor (CMOS) transistors that need to operate under practically error free conditions with 1 error in $10^{15}$ switching events. The physical dimensions of CMOS transistors have scaled down over the past five decades leading to exponential increases in functional density and energy consumption. Today, the energy and delay reductions from scaling have stagnated, motivating the search for a CMOS replacement. Of these, spintronics offers a path for enhancing the functional density and scaling the energy down to fundamental thermodynamic limits of 100kT to 1000kT. However, spintronic devices exhibit high error rates of 1 in 10 or more when operating at these limits, rendering them incompatible with deterministic nature of the von Neumann architecture. We show that a Shannon-inspired statistical computing framework can be leveraged to design a computer made from such stochastic spintronic logic gates to provide a computational accuracy close to that of a deterministic computer. This extraordinary result allowing a $10^{13}$ fold relaxation in acceptable error rates is obtained by engineering the error distribution coupled with statistical error compensation.