Traduccion del articulo ¨los limites de la computabilidad"

Control
 de
 Lectura.
 


 

Jesús
 Iván
 Mercado
 Bareño
 

Los
 límites
 de
 la
 computabilidad
 

  La
 teoría
 de
 la
 computación
 moderna
 precede
 
 a
 la
 misma
 computadora
 moderna.
 En
 1936,
 Alan
  M.
 Turing
 ideo
 una
 maquina
 que,
 ejecutando
 instrucciones
 y almacenando
 datos,
 podría
 realizar
  cualquier
 algoritmo
 computacional
 imaginable.
 
 Turing
 y
 
 otros
 señalaron
 que:
 si
 la
 solución
 a
 un
  problema
 
 puede
 escribirse
 en
 forma
 de
 una
 receta
 matemática
 finita,
 entonces
 es
 computable
 en
  una
 maquina
 de Turing.
 
  Pero
 entre
 los
 problemas
 computables
 algunos
 
 son
 más
 que
 computables
 que
 otros.
  La
  máquina
  de
  Turing
  puede
  recurrir
  a
  una
  cantidad
  ilimitada
  de
  memoria
  y
  tomar
  el
  tiempo
  necesario
  para
 
  producir
  una
  respuesta.
  Las  computadoras
  reales,
  tienen
  almacenamiento
  finito,
  y
  la
  computabilidad
  teórica
  no
  es
  práctica
  para
  algoritmos
  que
  tomen
  mucho
  tiempo,
  para
  producir
  una
 respuesta.
  Los
 métodos
 de
 encriptación
 se
 basan
 en
 un
 algoritmo
 de
 factorización,
 en
 el cual
 
 
 la
 estrategia
 es
  probar
  todos
  los
  números
  pequeños
  en
  secuencia
  hasta
  encontrar
  un
  divisor
  exacto,
  pero
  el
  tamaño
 de
 la
 tarea
 incrementa
 exponencialmente
 
 con
 el
 número
 de
 dígitos
 de
 la
 llave.
 Para
 claves
  grandes,
  la
 factorización
 es
 teóricamente
 factible
 pero
 imposible
 en
 la
 práctica.
  La
  teoría
  de
  la
  complejidad
  surgió
  en
  los
  60´s
  como
  una
  manera
  de
  clasificar
  la
  dificultad
  de
  los
 
  problemas.
  Los
  problemas
  fáciles
  pertenecen
  a
  la
  complejidad  clase
  P,
  para
  tiempo
  polinómico,
  es
  decir,
  que
  el
  algoritmo
 
  produce
  una
  respuesta
  en
  un
  tiempo
  que
  no
  suba
  mas
  rápido
  que
  el
 
  tamaño
  de
  entrada.
 
  Tareas
  como
  ordenar
  y
  optimizar
 
  una
  lista
  por
 programación
  lineal,
 
  pertenecen
 a
 
 
 los
 problemas
 P.
 
 Una
 amplia
 variedad
 de
 problemas
 mas
 exigentes
 pertenecen
 a
  una
  clase
  llamada
  NP.
 
  La
  característica
  de
  estos
  problemas
  es
  que
  la
  validez
  de
  una
  solución
  propuesta
 puede
 comprobarse en
 un
 tiempo
 polinómico,
 a
 pesar
 de
 que
 no
 hay
 un
 algoritmo
 para
  generar
 esta
 solución.
 La
 factorización
 entra
 en
 esta
 clase,
 si
 estas
 presentando
 dos
 números
 que
  pretender
  ser
  los
  factores
  de
  un
  numero
  grande,
  es
  fácil
  de
 comprobar
  la
  veracidad
  de
  la
  afirmación.
  Una
  definición
  alternativa
  de
  problemas
  NP
  es
  que
  pueden
  ser
  resueltos
  en
  tiempo
  polinómico
 
  en
  una
  maquina
  de
  Turing
 
  no
  determinística.
 
  Esta
  máquina
  hipotética
  se
  va
  por
 ...