Author Archives: demensdeum

Apresento a sua atenção uma tradução das primeiras páginas do artigo de Alan Turing – “SOBRE NÚMEROS COMPUTÁVEIS COM APLICAÇÃO AO PROBLEMA DE RESOLUÇÃO” 1936. Os primeiros capítulos contêm uma descrição dos computadores, que mais tarde se tornaram a base da computação moderna.

A tradução completa do artigo e a explicação podem ser lidas no livro do divulgador norte-americano Charles Petzold, intitulado “Reading Turing. Uma viagem pelo artigo marcante de Turing sobre computabilidade e máquinas de Turing – (ISBN 978-5-97060-231-7, 978-0-470-22905-7)

Artigo original:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf

—

SOBRE NÚMEROS COMPUTÁVEIS COM APLICAÇÃO AO PROBLEMA DE RESOLUÇÃO

A. M. TURING

[Recebido em 28 de maio de 1936 – lido em 12 de novembro de 1936]

Os números computáveis ​​podem ser brevemente descritos como números reais cujas expressões como frações decimais são calculáveis ​​de um número finito de maneiras. Embora à primeira vista este artigo trate os números como computáveis, é quase tão fácil definir e explorar funções computáveis ​​de uma variável inteira, uma variável real, uma variável computável, predicados computáveis ​​e similares. Contudo, os problemas fundamentais associados a estes objetos computáveis ​​são os mesmos em cada caso. Para uma consideração detalhada, escolhi números computáveis ​​como objeto computável porque o método de considerá-los é o menos complicado. Espero descrever em breve a relação entre números computáveis ​​e funções computáveis ​​e assim por diante. Paralelamente, serão realizadas pesquisas no campo da teoria das funções de uma variável real expressa em termos de números computáveis. Pela minha definição, um número real é computável se a sua representação como uma fração decimal puder ser escrita por uma máquina.

Nos parágrafos 9 e 10 apresento alguns argumentos para mostrar que os números computáveis ​​incluem todos os números que são naturalmente considerados computáveis. Em particular, mostro que algumas grandes classes de números são computáveis. Incluem, por exemplo, as partes reais de todos os números algébricos, as partes reais dos zeros das funções de Bessel, os números π, e e outros. No entanto, os números computáveis ​​não incluem todos os números definíveis, como evidenciado pelo seguinte exemplo de um número definível que não é computável.

Embora a classe dos números computáveis ​​seja muito grande e em muitos aspectos semelhante à classe dos números reais, ela ainda é enumerável. No §8 considero certos argumentos que parecem argumentar o contrário. Quando um destes argumentos é aplicado corretamente, tiram-se conclusões que, à primeira vista, são semelhantes às de Gödel*. Esses resultados têm aplicações extremamente importantes. Em particular, conforme mostrado abaixo (§11), o problema de resolução não pode ser resolvido.

Em seu artigo recente, Alonzo Church** introduziu a ideia de “calculabilidade efetiva”, que é equivalente à minha ideia de “computabilidade”, mas tem uma definição completamente diferente. Church também chega a conclusões semelhantes em relação ao problema da resolução. A prova da equivalência entre “computabilidade” e “capacidade de ser efetivamente contada” é apresentada no apêndice deste artigo.

1. Computadores

Já dissemos que números computáveis ​​são aqueles números cujas casas decimais são contáveis ​​por meios finitos. Uma definição mais clara é necessária aqui. Este artigo não fará nenhuma tentativa real de justificar as definições aqui dadas até chegarmos ao §9. Por enquanto, observarei apenas que a justificativa (lógica) para isso é que a memória humana é, por necessidade, limitada.

Vamos comparar uma pessoa no processo de cálculo de um número real com uma máquina que é capaz de cumprir apenas um número finito de condições q1, q2, …, qR; Vamos chamar essas condições de “m-configurações”. Esta máquina (isto é, assim definida) está equipada com uma “fita” (análoga ao papel). Esta correia que passa pela máquina é dividida em seções. Vamos chamá-los de “quadrados”. Cada um desses quadrados pode conter algum tipo de “símbolo”. Em qualquer momento, existe apenas um desses quadrados, digamos o enésimo, contendo o símbolo que está “nesta máquina”. Vamos chamar esse quadrado de “símbolo digitalizado”. Um “caractere digitalizado” é o único caractere do qual a máquina está, por assim dizer, “diretamente consciente”. No entanto, ao alterar sua configuração m, a máquina pode efetivamente lembrar alguns dos caracteres que “viu” (digitalizou) anteriormente. O possível comportamento da máquina a qualquer momento é determinado pela configuração m qn e pelo símbolo digitalizado***. Vamos chamar esse par de símbolos de qn, “configuração”. A configuração assim designada determina o comportamento possível de uma determinada máquina. Em algumas dessas configurações em que o quadrado digitalizado está em branco (ou seja, não contém nenhum caractere), a máquina escreve um novo caractere no quadrado digitalizado e em outras configurações apaga o caractere digitalizado. Esta máquina também é capaz de se mover para escanear outro quadrado, mas desta forma só pode se mover para o quadrado adjacente à direita ou à esquerda. Além de qualquer uma destas operações, a configuração m da máquina pode ser alterada. Neste caso, alguns dos caracteres escritos formarão uma sequência de dígitos, que é a parte decimal do número real que está sendo calculado. O restante nada mais será do que marcas imprecisas para “ajudar a memória”. Neste caso, apenas as marcas imprecisas mencionadas acima podem ser apagadas.

Afirmo que as operações consideradas aqui incluem todas as operações usadas no cálculo. A justificativa para esta afirmação é mais fácil de entender para o leitor que conhece a teoria das máquinas. Portanto, na próxima seção continuarei a desenvolver a teoria em questão, com base na compreensão do significado dos termos “máquina”, “fita”, “digitalizado”, etc.

*Gödel “Sobre as sentenças formalmente indecidíveis dos Principia Mathematics (publicado por Whitehead e Russell em 1910, 1912 e 1913) e Sistemas Relacionados, Parte I”, Journal of Mathematics. Física, boletim mensal em alemão nº 38 (para 1931, pp. 173-198.
** Alonzo Church, “Um problema indecidível na teoria elementar dos números”, American J. of Math., No. 58 (1936), pp.*** Alonzo Church, “Uma nota sobre o problema da resolução”, J. of Symbolic Logic, No. 1 (1936), pp.