Does a gun exert enough gravity on the bullet it fired to stop it? My question is set in the following situation:


*

*You have a completely empty universe without boundaries. 

*In this universe is a single gun which holds one bullet. 

*The gun fires the bullet and the recoil sends both flying in opposite directions. 


For simplicity I'll take the inertial frame of reference of the gun. The gun fired the bullet from its center of mass so it does not rotate. We now have a bullet speeding away from the gun. There is no friction. The only thing in this universe to exert gravity is the gun and the bullet.
Would, given a large enough amount of time, the bullet fall back to the gun? Or is there a limit to the distance gravity can reach?
 A: The gun's gravity will always exert a force on the bullet. The bullet will keep slowing down more and more forever. The rate of its deceleration is inversely proportional to the square of the distance from the gun. The further it is, the slower the deceleration.
It is logical to think that something that keeps slowing down forever will eventually stop. But that is not always true.
As the bullet slows down it loses kinetic energy. This can be calculated as the integral of force acting on it while it moves from distance $r_1$ to $r_2$.
$$\Delta K = -\int_{r_1}^{r_2} \frac{GMm}{r^2}\,dr$$
This loss of energy is never zero, yet its total sum is bounded. (By logic similar to how a geometric series can be convergent.) If the initial kinetic energy was greater than the bound on the energy loss, there will be some left no matter how much time has passed. In other words the bullet will slow down continuously, but never fall below a certain speed.
The escape velocity mentioned in the other answers is the initial velocity where the bullet has just as much kinetic energy as the bound of the energy lost. If this is exactly the initial velocity, then the bullet will slow down and its speed will tend to zero. If the initial velocity is higher, the bullet's velocity will tend to a positive value. If the initial velocity is lower, the bullet will lose all its speed after some finite time and start falling back.
A: As mentioned by Stephen Mathey in the comments, for each body with mass $M$ and radius $r$, there is a velocity one has to attain to completely escape the body's gravity well. This is the escape velocity
$$v_e=\sqrt{\frac{2GM}{r}}$$
where $G$ is Newton's constant of gravity, $M$ is the mass of the body you are escaping from, and $r$ is the distance from the center of mass at which the escape velocity has to be reached.
Usually, one apply this concept to planets (or moons) where $r$ is the planet's (moon's) radius and the escape velocity is the velocity a rocket would need (in terms of Delta-v) to escape the planet (moon). Here you could take the distance from the gun's center of mass to the opening of the barrel. While still in the barrel, the bullet might still accelerate due to expanding gases. Say that distance is $10~\mathrm{cm}$. Let's also assume the gun weighs one kilogram. Then, the escape velocity is as small as $37~\mu\mathrm{m}/\mathrm s$.
So, yeah, that bullet sure ain't coming back.
A: Making an assumption that the mass of the gun ($M$) is much greater than that of the bullet ($m$) , the net force on the bullet is: (From the gun's frame.)
$$m \frac{d^2r}{dt^2}=mv\frac{dv}{dr}=-\frac{GMm}{r^2}$$
The equality is obtained from the fact that acceleration is $\frac{dv}{dt}$, which equals $\frac{dv}{dr}\frac{dr}{dt}$, (via the chain rule) the second term being the velocity.
After integrating this, we get: 
$$\frac {mv^2}{2}-\frac{GMm}{r}=c$$
If we assume that the bullet stops at an infinite distance (i.e, it escapes the gun, never to return), its energy at that time would be zero. 
From this, we get:
$$v_i=\sqrt\frac{2GM}{r}$$ (where $r$ is the distance from the center of mass of the gun to the point where it left the gun.)
This is the escape velocity of the bullet. (like @Jonas and @Steven Mathey and @John Duffield have mentioned.)
For all initial velocities greater than this, the gravitational force from the gun would be unable to draw the bullet back. Considering how small the value of $v_i$ generally is compared to average bullet speeds, the bullet mostly will escape.
(The initial assumption helps make the math easier, but it is not an absurd assumption. This assumption is the mathematical equivalent of saying that the gun would not move at all because of the force exerted by the bullet on it.)
A: For a somewhat extreme answer: How massive should the gun be to have an escape velocity larger than the bullet speed? I am assuming we're using a 357 Magnum fired from a Desert Eagle, which is actually on the low to mid end of the muzzle velocity scale:

source: http://wredlich.com/ny/2013/01/projectiles-muzzle-energy-stopping-power/
A Desert Eagle has a 15 cm barrel. Using the formula provided in other answers:
$$v_\mathrm e=\sqrt{\frac{2GM}{r}}$$
Fill in the numbers:
$$v_\mathrm e=\sqrt{\frac{2\times G\times M}{0.15\ \mathrm m}}$$
$$(410\ \mathrm{m/s})^2=\frac{2\times G\times M}{0.15\ \mathrm m}$$
$$1.68\times10^5\ \mathrm{m^2\ s^{-2}}=13\ \mathrm{m^{-1}}\times G\times M$$
$$M=1.9\times10^{14}\ \mathrm{kg}$$
Note: I am not sure how accurate this number is. I entered these variables in 2 online calculators. 1 of them came up with this answer (http://calculator.tutorvista.com/escape-velocity-calculator.html), the other one came up with a number which is the same numbers, but many orders of magnitude smaller: $1889.4434\ \mathrm{kg}$ (https://www.easycalculation.com/physics/classical-physics/escape-velocity.php). I am not sure why these 2 numbers are so different.
A: 
Does a gun exert enough gravity on the bullet it fired to stop it?

No. 

Would, given a large enough amount of time, the bullet fall back to the gun? 

No.

Or is there a limit to the distance gravity can reach?

No. 
But the bullet's velocity exceeds escape velocity. See Wikipedia where you can read that escape velocity at a given distance is calculated by the formula
$$v_e = \sqrt{\frac{2GM}{r}}$$
Imagine you play this scenario in reverse. You have a bullet and a gun, a zillion light years apart, motionless with respect to another. You watch and wait, and after a gazillion years you notice that they're moving towards one another due to gravity. (To simplify matters we'll say the gun is motionless and the bullet is falling towards the gun). After another bazillion years you've followed the bullet all the way back to the gun, and you notice that they collide at 0.001 m/s. You check your sums and you work out that this is about right, given that if the gun was as massive as the Earth's 5.972 × 10$^{24}$ kg, the bullet would have collided with it at 11.7 km/s. Escape velocity is the final speed of a falling body that starts out at an "infinite" distance. If you launch a projectile from Earth with more than escape velocity, it ain't ever coming back. 
OK, now let's go back to the original scenario. You fire the gun, and the bullet departs at 1000 m/s. When the bullet is a zillion light years away, its speed has reduced to 999.999 m/s. Because the gun's escape velocity is 0.001 m/s. The gun's gravity is never going to be enough to stop that bullet, even if it had all the time in the world and all the tea in China.      
