Page 7 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

7

CONCEPTOS

La computación: es el estudio de los fundamentos teóricos de la información que

procesan las computadoras, y las distintas implementaciones en forma de sistemas
computacionales. La computación como nuevas formas de proceso de datos se

fundamenta en la matemática, con influencia de la lingüística y la física. La computación
se enfoca principalmente en el estudio de nuevas formas de procesamiento de datos y no

con las computadoras ya que estas derivan de este proceso. En fin, la computación es una

ciencia que es muy importante para el desarrollo de las sociedades ya que puede
desarrollar maneras de simplificación de procesos para el manejo de la información a

través de sistemas computarizados.
Ciencias computacionales: para designar tanto el estudio científico como el aplicado en

computadores en el proceso de información.
Computabilidad: capacidad de realizar procesos o cálculos sobre algo a efectos de lograr

resultados de este proceso y/o cálculo. Existe lo que es computable y lo que no es

computable, lo que se puede calcular o someter a procesos de cálculos y lo que no lo es.
Complejidad algorítmica: se refiere a lo difícil y complejo del proceso lógico que lleva

a la solución de algo. Esto se relaciona con tiempo y espacio por lo difícil de la solución.

Complejidad computacional: se refiere a los recursos que utiliza el computador
(memoria, procesos de cálculo) para realizar un proceso.

Máquina de Turing: una Máquina de Turing (MT) es un modelo computacional que
realiza una lectura/escritura de manera automática sobre una entrada llamada cinta,

generando una salida en esta misma.
Problemas Decidibles: En teoría de la computación, un problema es un conjunto de frases

de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un

problema de decisión es un problema en donde las respuestas posibles son «sí» o «no».
Un problema de decisión también se puede formalizar como el problema de

decidir si una cierta frase pertenece a un conjunto dado de frases, también
llamado lenguaje formal.