I am going through notes on Computability theory and Galosis Theory by Russel Miller. In it, many times the phrase "set of all programs" is used. Could someone give a formal definition of what the set of all programs are?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Assuming these are the notes you are talking about, the author informally described a Turing machine with the following excerpt
For our purposes, a Turing machine is an ordinary computer, operating according to a finite program, which accepts a natural number as input and runs its program in discrete steps on that input.
Usually (e.g. in Sipser's Introduction to the Theory of Computation), a Turing machine is formally defined as some variation on the following:
Generally in computability and complexity theory, we think of the alphabets $\Sigma$ and $\Gamma$ as simply being $\{0,1\}$, and Turing machines as being uniquely specified by their state sets $Q$ and transition functions $\delta$. This part of the tuple is what Miller refers to as the "program" of a Turing Machine in the informal definition excerpted from his notes above. As such, the terms "program" and "Turing machine" are often used interchangeably to mean the same object.
The set of all programs is then understood to mean the set of all possible state sets and transition functions.
