https:\/\/www.astro.puc.cl\/~rparra\/tools\/PAPERS\/turing_1936.pdf<\/a><\/p>\nSOBRE N\u00daMEROS COMPUT\u00c1VEIS COM APLICA\u00c7\u00c3O AO PROBLEMA DE RESOLU\u00c7\u00c3O<\/p>\n
AM TURING<\/p>\n
[Recebido em 28 de maio de 1936 – lido em 12 de novembro de 1936]<\/p>\n
Os n\u00fameros “comput\u00e1veis” podem ser brevemente descritos como n\u00fameros reais cujas express\u00f5es como fra\u00e7\u00f5es decimais s\u00e3o calcul\u00e1veis \u200b\u200bde um n\u00famero finito de maneiras. Embora \u00e0 primeira vista este artigo trate os n\u00fameros como comput\u00e1veis, \u00e9 quase t\u00e3o f\u00e1cil definir e explorar fun\u00e7\u00f5es comput\u00e1veis \u200b\u200bde uma vari\u00e1vel inteira, uma vari\u00e1vel real, uma vari\u00e1vel comput\u00e1vel, predicados comput\u00e1veis \u200b\u200be similares. Contudo, os problemas fundamentais associados a estes objetos comput\u00e1veis \u200b\u200bs\u00e3o os mesmos em cada caso. Para uma considera\u00e7\u00e3o detalhada, escolhi n\u00fameros comput\u00e1veis \u200b\u200bcomo objeto comput\u00e1vel porque o m\u00e9todo de consider\u00e1-los \u00e9 o menos complicado. Espero descrever em breve a rela\u00e7\u00e3o entre n\u00fameros comput\u00e1veis \u200b\u200be fun\u00e7\u00f5es comput\u00e1veis \u200b\u200be assim por diante. Paralelamente, ser\u00e3o realizadas pesquisas no campo da teoria das fun\u00e7\u00f5es de uma vari\u00e1vel real expressa em termos de n\u00fameros comput\u00e1veis. Pela minha defini\u00e7\u00e3o, um n\u00famero real \u00e9 comput\u00e1vel se a sua representa\u00e7\u00e3o decimal puder ser escrita por uma m\u00e1quina.<\/p>\n
Nos par\u00e1grafos 9 e 10 apresento alguns argumentos para mostrar que os n\u00fameros comput\u00e1veis \u200b\u200bincluem todos os n\u00fameros que s\u00e3o naturalmente considerados comput\u00e1veis. Em particular, mostro que algumas grandes classes de n\u00fameros s\u00e3o comput\u00e1veis. Incluem, por exemplo, as partes reais de todos os n\u00fameros alg\u00e9bricos, as partes reais dos zeros das fun\u00e7\u00f5es de Bessel, os n\u00fameros \u03c0, e e outros. No entanto, os n\u00fameros comput\u00e1veis \u200b\u200bn\u00e3o incluem todos os n\u00fameros defin\u00edveis, como evidenciado pelo seguinte exemplo de um n\u00famero defin\u00edvel que n\u00e3o \u00e9 comput\u00e1vel.<\/p>\n
Embora a classe dos n\u00fameros comput\u00e1veis \u200b\u200bseja muito grande e em muitos aspectos semelhante \u00e0 classe dos n\u00fameros reais, ela ainda \u00e9 enumer\u00e1vel. No \u00a78 considero certos argumentos que parecem argumentar o contr\u00e1rio. Quando um destes argumentos \u00e9 aplicado corretamente, tiram-se conclus\u00f5es que, \u00e0 primeira vista, s\u00e3o semelhantes \u00e0s de G\u00f6del*. Esses resultados t\u00eam aplica\u00e7\u00f5es extremamente importantes. Em particular, como mostrado abaixo (\u00a711), o problema de resolu\u00e7\u00e3o n\u00e3o pode ter solu\u00e7\u00e3o.<\/p>\n
Num artigo recente, Alonzo Church introduziu a ideia de \u201ccalculabilidade efectiva\u201d, que \u00e9 equivalente \u00e0 minha ideia de \u201ccomputabilidade\u201d, mas tem uma defini\u00e7\u00e3o completamente diferente. Church tamb\u00e9m chega a conclus\u00f5es semelhantes em rela\u00e7\u00e3o ao problema da resolu\u00e7\u00e3o. A prova da equival\u00eancia entre \u201ccomputabilidade\u201d e \u201cefetivamente calcul\u00e1vel\u201d \u00e9 apresentada no ap\u00eandice deste artigo.<\/p>\n
1. Computadores<\/p>\n
J\u00e1 dissemos que n\u00fameros comput\u00e1veis \u200b\u200bs\u00e3o aqueles n\u00fameros cujas casas decimais s\u00e3o cont\u00e1veis \u200b\u200bpor meios finitos. Uma defini\u00e7\u00e3o mais clara \u00e9 necess\u00e1ria aqui. Este artigo n\u00e3o far\u00e1 nenhuma tentativa real de justificar as defini\u00e7\u00f5es aqui dadas at\u00e9 chegarmos ao \u00a79. Por enquanto, observarei apenas que a justificativa (l\u00f3gica) (para isso) \u00e9 que a mem\u00f3ria humana \u00e9, por necessidade, limitada.<\/p>\n
Comparemos uma pessoa no processo de c\u00e1lculo de um n\u00famero real com uma m\u00e1quina que \u00e9 capaz de cumprir apenas um n\u00famero finito de condi\u00e7\u00f5es q1, q2, …, qR; Vamos chamar essas condi\u00e7\u00f5es de \u201cm-configura\u00e7\u00f5es\u201d. Esta m\u00e1quina (isto \u00e9, assim definida) est\u00e1 equipada com uma \u201cfita\u201d (an\u00e1loga ao papel). Esta correia que passa pela m\u00e1quina \u00e9 dividida em se\u00e7\u00f5es. Vamos cham\u00e1-los de \u201cquadrados\u201d. Cada um desses quadrados pode conter algum tipo de \u201cs\u00edmbolo\u201d. Em qualquer momento, existe apenas um desses quadrados, digamos o en\u00e9simo, contendo o s\u00edmbolo que est\u00e1 \u201cnesta m\u00e1quina\u201d. Vamos chamar esse quadrado de \u201cs\u00edmbolo digitalizado\u201d. Um “caractere digitalizado” \u00e9 o \u00fanico caractere do qual a m\u00e1quina est\u00e1, por assim dizer, “diretamente consciente”. No entanto, ao alterar sua configura\u00e7\u00e3o m, a m\u00e1quina pode efetivamente lembrar alguns dos caracteres que “viu” (digitalizou) anteriormente. O poss\u00edvel comportamento da m\u00e1quina a qualquer momento \u00e9 determinado pela configura\u00e7\u00e3o m qn e pelo s\u00edmbolo digitalizado***. Vamos chamar esse par de s\u00edmbolos de qn, \u201cconfigura\u00e7\u00e3o\u201d. A configura\u00e7\u00e3o assim designada determina o comportamento poss\u00edvel de uma determinada m\u00e1quina. Em algumas dessas configura\u00e7\u00f5es em que o quadrado digitalizado est\u00e1 em branco (ou seja, n\u00e3o cont\u00e9m nenhum caractere), a m\u00e1quina escreve um novo caractere no quadrado digitalizado e em outras configura\u00e7\u00f5es apaga o caractere digitalizado. Esta m\u00e1quina tamb\u00e9m \u00e9 capaz de se mover para escanear outro quadrado, mas desta forma s\u00f3 pode se mover para o quadrado adjacente \u00e0 direita ou \u00e0 esquerda. Al\u00e9m de qualquer uma destas opera\u00e7\u00f5es, a configura\u00e7\u00e3o m da m\u00e1quina pode ser alterada. Neste caso, alguns dos caracteres escritos formar\u00e3o uma sequ\u00eancia de d\u00edgitos, que \u00e9 a parte decimal do n\u00famero real que est\u00e1 sendo calculado. O restante nada mais ser\u00e1 do que marcas imprecisas para \u201cajudar a mem\u00f3ria\u201d. Neste caso, apenas as marcas imprecisas acima mencionadas podem ser apagadas.<\/p>\n
Afirmo que as opera\u00e7\u00f5es aqui consideradas incluem todas as opera\u00e7\u00f5es usadas no c\u00e1lculo. A justificativa para esta afirma\u00e7\u00e3o \u00e9 mais f\u00e1cil de entender para o leitor que conhece a teoria das m\u00e1quinas. Portanto, na pr\u00f3xima se\u00e7\u00e3o continuarei a desenvolver a teoria em quest\u00e3o, com base na compreens\u00e3o do significado dos termos \u201cm\u00e1quina\u201d, \u201cfita\u201d, \u201cdigitalizado\u201d, etc.<\/p>\n
*G\u00f6del \u201cSobre as Senten\u00e7as Formalmente Indecid\u00edveis dos Principia Mathematics (publicado por Whitehead e Russell em 1910, 1912 e 1913) e Sistemas Relacionados, Parte I,\u201d Journal of Mathematics. F\u00edsica, boletim mensal em alem\u00e3o n\u00ba 38 (para 1931, pp. 173-198.
\n** Alonzo Church, \u201cUm problema indecid\u00edvel na teoria elementar dos n\u00fameros\u201d, American J. of Math., No.
\n*** Alonzo Church, \u201cUma nota sobre o problema da resolu\u00e7\u00e3o\u201d, J. of Symbolic Logic, No. 1 (1936), pp.<\/p>\n","protected":false},"excerpt":{"rendered":"
Apresento a sua aten\u00e7\u00e3o uma tradu\u00e7\u00e3o das primeiras p\u00e1ginas do artigo de Alan Turing \u201cON COMPUTABLE NUMBERS WITH AN APPLICATION TO THE PROBLEM OF RESOLUTION\u201d de 1936. Os primeiros cap\u00edtulos cont\u00eam uma descri\u00e7\u00e3o dos computadores, que mais tarde se tornaram a base da computa\u00e7\u00e3o moderna. A tradu\u00e7\u00e3o completa do artigo e a explica\u00e7\u00e3o podem ser […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-70","post","type-post","status-publish","format-standard","hentry","category-notes"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"pt","enabled_languages":["en","ru","zh","de","ja","fr","es","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"es":{"title":false,"content":false,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":true,"content":true,"excerpt":false}}},"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/70","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/comments?post=70"}],"version-history":[{"count":1,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/70\/revisions"}],"predecessor-version":[{"id":73,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/70\/revisions\/73"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/media?parent=70"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/categories?post=70"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/tags?post=70"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}