Restricted Boltzmann machines are stochastic neural networks. The neurons form a complete bipartite graph of visible units and hidden units. The "restricted" is exactly the bipartite property: There may not be a connection between any two visible units and there may not be a connection between two hidden units.
Restricted Boltzmann machines are trained with Contrastive Divergence (CD-k, see A Practical Guide to Training Restricted Boltzmann Machines).
Now I wonder: How are non-restricted Boltzmann Machines trained?
When I google for "Boltzmann Machine", I only finde RBMs.