Redutibilidade

Redutibilidade é o principal método de provar que problemas são computacionalmente insolúveis. Sabemos que a Máquina de Turing é um modelo de um computador de propósito geral e que existem diversos exemplos de problemas que são solúveis por máquinas de Turing como também problemas computacionalmente insolúveis. Ao se examinar problemas insolúveis introduzimos o método de redutibilidade que prova que alguns problemas são computacionalmente insolúveis.

A Redutibilidade não diz nada em resolver A ou B sozinhos, mas somente sobre a solubilidade de A na presença de um método para resolver B. Como exemplo de Redutibilidade em aspectos matemáticos podemos citar que a medição da área de um retângulo se reduz ao problema de se medir seu comprimento e largura. O Problema de se resolver um sistema de equações lineares se reduz ao problema de se inverter uma matriz. Quando A é redutível a B, resolver A não pode ser mais difícil que resolver B, porque uma solução para B dá solução para A. Em resumo, nosso método para provar que um problema é indecidível será mostrar que algum outro problema já conhecido como sendo indecidível se reduz a ele. Aborda uma determinada entrada para Máquina de Turing, estabelecendo uma relação de redução para definirmos se a máquina pára (aceitando ou rejeitando) sobre a entrada anteriormente definida.

Ex: Problema = {<M,w> | M é uma MT e M pára sobre a entrada w}.

A principal chave da questão é o problema de entrada e o de comportamento. Vemos que um faz a redução do outro (a entrada para uma máquina, definindo o estado de comportamento). A Redutibilidade é diretamente ligada com a indecidibilidade.Os teoremas ilustram as estratégias para provar que um problema é indecidível. O método da Redutibilidade faz uso de notações, exceto,quando nos referimos a própria Máquina de Turing,sendo essa provada através do método da diagonalização. Diagonalização é uma técnica de comparação de métodos ou problemas, envolvendo tamanhos,espaços ou quantidades. Indecidibilidade é um problema de decisão com conjunto de números naturais; o "problema" é determinar se um número em particular pertence ao conjunto ou notação, afetando em sua decisão. O método de história da computação é uma técnica importante para provar que uma entrada é redutível a certas linguagens.Esse método é freqüentemente útil quando o problema a ser mostrado como indecidível envolve testar a existência de algo. A história de computação para uma máquina de Turing sobre uma entrada é simplesmente a seqüência de configurações pelas quais a máquina passa à medida que processa a entrada. É um registro completo da computação dessa máquina.

Tomemos duas definições que descrevem essas vias:

Primeira Definição: Seja M uma máquina de Turing e w uma cadeia de entrada.Uma história de computação de aceitação para M sobre w é uma seqüência de configurações, C1, C2. . . Cn, onde C1 é a configuração inicial de M sobre w,Cn é uma configuração de aceitação de M, e cada Ci segue legitimamente de Ci-1 conforme as regras de M. Uma história de computação de rejeição para M sobre w é definida similarmente, exceto que Cn é uma configuração de rejeição.

Segunda Definição: Um autômato linearmente limitado é um tipo restrito de máquina de Turing na qual a cabeça de leitura-escrita não é permitida mover-se para fora da parte da fita contendo a entrada. Se a máquina tentar mover sua cabeça para além de qualquer uma das extremidades da entrada, a cabeça permanecerá onde está, da mesma maneira que a cabeça não se movimentará para além da extremidade esquerda da fita de uma máquina de Turing ordinária.

Traduzindo a segunda via, podemos dizer que um autômato limitado é uma Máquina de Turing com quantidade limitada de memória.Ela só pode resolver problemas que requerem memória que possa caber dentro da fita usada para entrada. A Indecidibilidade não está somente confinada a problemas relacionados a autômatos. É a formalização da Redutibilidade. A noção de reduzir um problema a outro pode ser definida formalmente de várias maneiras, a forma mais simples é definida por Mapeamento. De forma resumida, dizemos que ser capaz de reduzir um problema A ao problema B usando uma redução por mapeamento significa que existe uma função computável que converte instâncias do problema A para instâncias do problema B. Uma Máquina de Turing computa uma função iniciando com a entrada para a função sobre a fita e parando com a saída da função sobre a fita.

Redução

Uma Redução (complexidade) é uma maneira de converter um problema em outro de forma que uma solução para o segundo problema possa ser usada para resolver o primeiro. Essas redutibilidades aparecem frequentemente no dia-a-dia, mesmo que em geral não nos refiramos a ela dessa forma.

Por exemplo, supondo que uma pessoa deseje se orientar em uma cidade nova. Seria muito mais fácil se a pessoa em questão tivesse consigo um mapa. Consequentemente o problema pode ser reduzido ao problema de se obter um mapa da nova cidade em que se está.

A redutibilidade sempre envolve dois problemas, que denominamos A e B. Se A se reduz a B, podemos usar uma solução para B para resolver A. Assim no nosso exemplo, A é o problema de se orientar na cidade e B é o problema de se se obter um mapa da cidade. Notemos que a redutibilidade não diz nada sobre resolver A ou B separados, mas apenas sobre a solubilidade de A na presença de uma solução para B.

O que se segue são exemplos adicionais de redutibilidades. O problema de se viajar de Recife a Londres se reduz ao problema de se comprar uma passagem aérea entre as duas cidades. Esse problema, por sua vez, se reduz ao problema de ganhar o dinheiro para passagem. E esse último problema se reduz ao problema de se encontrar uma fonte de renda.

Problemas Matemáticos

A redutibilidade também se encontra em problemas matemáticos. Por exemplo, o problema de se medir a área de um retângulo se reduz ao problema de se medir seu comprimento e largura, assim como em um quadrado o problema se reduziria a encontrarmos a medida de um de seus lados. O problema de se resolver um sistema de equações lineares se reduz ao problema de se inverter uma Matriz.

Teoria da Complexidade

A redutibilidade desempenha um importante papel na classificação de problemas por decidibilidade e, posteriormente, em teoria da complexidade também.

Quando A é redutível a B, resolver A não pode ser mais difícil do que resolver B, porque uma solução para B dá uma solução para A. Em termos de teoria da computabilidade, se A for redutível a B e B for decidível, A também será decidível. Equivalentemente, se A for indecidível e redutível a B, B será indecidível. Essa última versão é a chave para provar que vários problemas são indecidíveis.

Em resumo, um excelente método para provar que um problema é indecidível será mostrar que algum outro problema já conhecido como sendo indecidível se reduz a ele

Redutibilidade por mapeamento em tempo polinomial

Uma linguagem A é redutível por mapeamento em tempo polinomial, ou simplesmente redutível em tempo polinomial, à linguagem B se existe uma função computável em tempo polinomial onde para toda w, w pertença a A se e somente se f(w) pertença a B. A função é denominada redução de tempo polinomial de A para B. Em alguns livros-texto redutibilidade por mapeamento também pode ser chamado de redutibilidade muitos-para-um.

A linguagem A é redutível por mapeamento à linguagem B, escrito A ≤_m B, se existe uma função computável ƒ: Σ → Σ, onde para toda w, w ∈ A ←→ ƒ(w) ∈ B. A função ƒ é denominada a redução de A para B.

Funções computáveis

Uma máquina de Turing computa uma função iniciando com a entrada para a função sobre a fita e parando com a saída da função sobre a fita. Uma função ƒ: Σ → Σ* é uma função computável se alguma máquina de Turing M, sobre toda entrada w, pára com exatamente ƒ(w) sobre a fita. Todas as operações aritméticas usuais sobre inteiros são funções computáveis. Por exemplo, podemos construir uma máquina que toma entrada <m,n> e retorna m+n, a soma de m e n.

Relações de redutibilidade

Uma relação de redutibilidade é uma relação binária em conjuntos de números naturais que são:

• Reflexiva : todo conjunto é redutível a ele mesmo.
• Transitiva : Se um conjunto A é redutível a um conjunto B e um conjunto B é redutível a um conjunto C, então A é redutível a C.

As noções de redutibilidade estudadas na teória da computação têm a propriedade informal de que A é redutível a B se e somente se algum (possivelmente até mesmo não efetivo) procedimento de decisão para B pode ser efetivamente convertido para um procedimento de decisão para A. As diferentes relações de redutibilidade variam de métodos para métodos, que permitem ou não o uso de processos de conversão.

Referências

• K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Unpublished preprint.
• P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. ISBN 0-444-87295-7
• P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier. ISBN 0-444-50205-X
• E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
• H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7
• Michael Sipser, Thomson Pioneira, ISBN 8522104999, 2007. (Tradução brasileira de Introduction to the Theory of Computation, Michael Sipser, Second Edition, PWS Publishing Company, February 2005, ISBN 0-534-95097-3.)
• Almeida, L. S. & Freire, T. Metodologia da investigação em psicologia e educação. Braga: Psiquilíbrios. 2003.
• Bessa- Oliveira. Níveis de ajustamento e auto-regulação académica em estudantes universitários. Universidade de Aveiro. Dissertação de Mestrado. 2000.
• Biggs, J. B. . Assessing study approaches to learning. Australian Psychologist, 23, 197-206.1988
• Biggs, J.B. Student Approaches to Learning and Stydying. Hawthorm: Australian Council for Educational Research. 1987.
• Boekaerts, M.; Pintrich, P. e Zeidner,M.(Eds.) Handbook of Self-Regulation. Academic Press. Sage. 2000.
• Cross, S. E. & Markus, H. R. Self-schemas, possible selves, and competent performance,Journal of Educational Psychology, 86, 423-438.1994.
• Entwistle, N. J. La comprensión del aprendizaje en el aula. Barcelona: Paidós.1988.
• Marton, F. Hounsel, D. e Entwistle,N. (Eds.) The Experience of Learning. Edinburgh: Scottish Academic Press. 1997.
• McCombs, B. L. & Marzano, R. J. Putting the self in self-regulated learning: The self as agent in integring will and skill. Educational Psychologist, 25, 51-69.
• Pascarela, E.T. e Terenzinni,P.T. How College affect students. San Francisco: Jossey-Bass Publishers. 1991.
• Pintrich, P. R. & Schrauben, B. Students´ motivational beliefs and their cognitive engagement in classroom academic task. In D. H. Schunk & J. L. Meece (Eds.), Student perceptions in the classroom. Hillsdale, NJ: Erlbaum. 1992
• Rosário (2000).
• Santos, L. Adaptação académica e rendimento escolar: estudo com alunos universitários do 1ºano. Braga. Universidade do Minho.Grupo de Missão para a Qualidade do Ensino / Aprendizagem. 2001
• Schunk, D.H. e Zimmerman, B.J. Self-regulation of learning performance: issues and educational applications. Hillsdale: Erlbaum Associates. 1994.
• Soares, A.P.; Osório, A.; Capela, J.V.; Almeida, L. ; Vasconcelos, R.M.; Caíres, S.M. Transição para o Ensino Superior. Braga: Universidade do Minho. 2000.
• Tavares, J. e Santiago, R. (Orgs.) Ensino Superior: (in)sucesso académico. Porto: Porto Editora. 2000.
• Tinto, V. Leaving College: Rethinking the causes and cures of student attrition. Chicago,IL: University of Chicago Press. 1991.
• Upcraft, M.L. e Gardner, J.N. (Eds.) The Freshman Year Experience. San Francisco: Jossey-Bass Publishers. 1989.