1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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:

tmdef

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.