Un autómata es solo una máquina que puede hacer cosas por sí mismo.
O quizás de una manera más relatable, es un modelo abstracto de una computadora. ¡Un modelo matemático de una computadora! En teoría computacional, básicamente queremos saber cómo se pueden calcular las cosas, qué se puede calcular y qué tan rápido se pueden calcular.
Qué tan rápido se pueden calcular:
- ¿Qué es una explicación intuitiva del mecanismo de Laplace?
- ¿Por qué no hay muchas mujeres exitosas en el campo de la informática?
- ¿Se puede aplicar el aprendizaje automático a cualquier producto? En caso afirmativo, ¿qué sectores tienen más sentido?
- ¿Qué son MDA y UML ejecutable? ¿Quién los usa? ¿Son realmente útiles para la industria del software o no software? ¿Cómo puedo aprender esto? ¿Hay algún buen libro que pueda descargar?
- ¿Dónde está la fruta de bajo perfil en Machine Learning?
Cómo se pueden calcular las cosas: lo que se hizo es que se crearon modelos. Diferentes modelos de autómatas. DFA, PDA, máquinas de Turing y, de hecho, muchas otras. Los tres en particular funcionan de manera un poco diferente el uno del otro. Almacenan información de una manera diferente. DFA solo almacena realmente el estado activo. Si hubiera 1000 formas diferentes de llegar a cualquier estado, no habría forma de averiguar qué camino tomó. Los PDA en realidad tienen memoria, por lo que se pueden calcular más tipos de cosas.
Pero podemos demostrar que los PDA todavía tienen algunas limitaciones serias. Se cree que las máquinas de Turing son capaces de cualquier cosa que se pueda calcular.
Una razón por la que usamos autómatas es porque nos ayuda a visualizar y crear algún tipo de sistema que sea capaz de computar cosas. Si podemos simular un DFA, por ejemplo, entonces podemos construir algún tipo de máquina automática. Si podemos simular una máquina de Turing, entonces probablemente descubriremos que nuestra computadora es capaz de hacer cualquier cosa que pueda computarse.
Qué se puede calcular: si tenemos una computadora que puede simular un DFA, entonces podemos demostrar matemáticamente que ciertas cosas no son computables. De hecho, la mayoría de las cosas no lo son. Si tenemos una computadora que puede simular una máquina de turing, podemos probar cosas similares.
Por ejemplo, básicamente podemos codificar una máquina de Turing y pretender que es un programa para otra máquina de Turing. Esto es muy parecido a una computadora.
Estudiamos autómatas porque nos ayuda a desarrollar modelos sobre cómo calcular cosas, y porque nos permite probar ciertas cosas sobre lo que se puede o no calcular.
