Mathematics is often referred to as the "study of patterns." What I'm wondering is whether there is somehow a technical way to describe a pattern. For the length of this question let's assume that we're considering integer patterns (i.e. some set of integer sequences $(a_n)_{n \in \mathbb N}$).
A bit more formally, we have a subset $P \subset \mathbb{Z}^\mathbb{N}$ consisting of all patterns. Since $\mathbb{Z}^\mathbb{N}$ is uncountable, it seems desirable that $P$ be countable.
A few examples of patterns are as follows:
- The prime numbers
- The outputs of any polynomial with integer coefficients
- Any recursive formula
The key to these examples is that they are finitely described. So my naive thought is that we wish to have a bijection between some set of finite strings (i.e. descriptions of some sort) (this is a countable set) and the sequences which are described by those strings.
My first solution was to make the following definition:
A pattern is any sequence of integers $(a_n)_{n \in \Bbb{N}}$ such that there exists a Turing machine $M$ which on input $n$ returns $a_n$. Or, essentially, a pattern is any sequence of integers which can be computed by an algorithm.
This ends up failing since the following should be a pattern: Order the set of all Turing machines, and let $t_i$ be the integer describing the $i$th Turing machine that does not halt on a possible input. The sequence $(t_i)_{i \in \Bbb N}$ is inherently not computable, but seems to be a perfectly reasonable pattern.
So I guess my question is, is there a way of making rigorous the notion of a sequence being "finitely described" which would then serve to be a natural definition of pattern?
