No início do século XX, matemáticos freqüentemente usaram o termo informal efetivamente computável, então foi importante achar uma boa formalização do conceito. Matemáticos modernos usam, em seu lugar, o termo bem-definido Turing-computável (ou apenas computável). Já que a terminologia indefinida caiu em desuso, a questão de como definí-la é agora menos importante.
Provas na teoria da computabilidade comummente usam a tese de Church-Turing de um jeito informal para estabelecer a computabilidade de funções, evitando os detalhes (muitas vezes muito longos) que normalmente seriam mostrados em uma prova mais formal. Para estabelecer que uma função é computável usando uma máquina de Turing, normalmente é considerado suficiente dar uma descrição informal de como a função pode ser efetivamente computada, e então concluir "De acordo com a tese de Church-Turing" que a função é Turing computável. Dirk van Dalen (em Gabbay 2001:284[1]) dá o seguinte exemplo a fim de ilustrar esse uso informal da tese de Church-Turing:
A partir dessa lista, extraímos uma sublista crescente: faça m0=n0, após um número finito de passos acharemos um nk tal que nk > m0, faça m1=nk. Nós repetimos esse processo para achar m2 > m1, etc. Isso produz uma listagem eficaz do subconjunto B={m0,m1,m2,...} de A, com a propriedade mi < mi+1.
Reivindicação: B é decidível. Para testarmos k em B precisamos testar se k=mi para algum i. Já que a sequência de mi's está aumentando, nós temos que produzir no máximo k+1 elementos da lista e comparar com k. Se nenhum é igual a k, então k não está em B. Já que esse teste é eficiente, B é decidível e, de acordo com a tese de Church, recursivo.
A fim de tornar o exemplo acima completamente rigoroso, deveríamos cuidadosamente construir uma Máquina de Turing, ou função-λ, ou cuidadosamente usar axiomas recursivos, ou na melhor das hipóteses habilmente usar vários teoremas da teoria da computabilidade. Mas já que teoristas da computabilidade acreditam que a computabilidade de Turing corretamente captura o que se pode ser computado efetivamente, e porque um procedimento eficaz é dado em linguagem informal para decidir o conjunto B, teóricos da computabilidade aceitam isso como prova que o conjunto é de fato recursivo.