Section 9.4.1. of Ethereum paper (Petersburg version 41c1837 — 2021-02-14), states that:
The machine state μ is defined as the tuple (g,pc,m,i,s) which are the gas available, the program counter pc ∈ N_256, the memory content, the active number of words in memory (counting continuously from position 0), and the stack contents. The memory contents μ_m are series of zeros of size 2^256.
Further in this documentation, a machine state is said to be prone to change from block to block according to a pre-defined set of rules and can execute arbitrary machine code. The specific rules of changing state from block to block are defined by the EVM.
Also in the documentation, there is an external resource that illustrates machine state as part of volatile memory in the EVM.
So what is a machine state, what are pre-defined rules that can change machine state, and what it has to do with EVM?