Levenshtein Distance

Matlab, 177 163 bytes

function l=c(a,b);m=nnz(a)+1;n=nnz(b)+1;for i=0:m-1;for j=0:n-1;z=max(i,j);try;z=min([l(i,j+1)+1,l(i+1,j)+1,l(i,j)+(a(i)~=b(j))]);end;l(i+1,j+1)=z;end;end;l=l(m,n)

This is a straightforward implementation of this formula:

Ungolfed:

function l=l(a,b);
m=nnz(a)+1;
n=nnz(b)+1;
for i=0:m-1;
    for j=0:n-1;
        z=max(i,j);
        try;
            z=min([l(i,j+1)+1,l(i+1,j)+1,l(i,j)+(a(i)~=b(j))]);
        end;
        l(i+1,j+1)=z;
    end;
end;
l=l(m,n)

Pyth, 34 bytes

J]wf}z=Jsmsm++.DdkXLdkGXLkdGhld-Jk

Demonstration

This is not particularly well golfed, and very slow. It can't handle anything past 2 changes in a reasonable period of time.

Python 2, 151 140 138 bytes

Slow recursive implemention of the Levenshtein distance based on Wikipedia (Thanks to @Kenney for shaving of 11 chars and @Sherlock9 for another 2).

def l(s,t):
 def f(m,n):
  if m*n<1:return m or n
  return 1+min([f(m-1,n),f(m,n-1),f(m-1,n-1)-(s[m-1]==t[n-1])])
 return f(len(s),len(t))

Giving the correct answers for the presented test cases:

assert l("tar", "tarp") == 1
assert l("turing", "tarpit") == 4
assert l("antidisestablishmentarianism", "bulb") == 27        
assert l("atoll", "bowl") == 3