CSC 341: April 16, 2007
From CSWiki
Instructor's notes for the class session
Data structures (constructors, selectors, and type predicates) for:
- Turing machines,
- transitions, and
- configurations.
There are some minor glitches that have to be accommodated. For instance, the number that encodes a string in a Turing machine's input alphabet is different from the number that encodes it in the same machine's tape alphabet, since the alphabets inevitably differ in size.
In addition to the selector that outputs a given Turing machine's transition function, we need a TM-transition-lookup procedure that takes as its arguments a Turing machine, a (non-stopping) state, and a tape symbol and returns the transition that the Turing machine will make when it is in that state with its read-write head on a cell containing that tape symbol.
A configuration comprises an indication of a Turing machine's current state, a string in its tape alphabet containing some finite, non-empty prefix of the tape that includes all of its non-blank symbols, and the position of its read-write head. We require that the head position be less than the length of the tape prefix in any valid configuration. For instance, we build the boot configuration from the Turing machine's start state, cell number 0, and the input string (re-encoded using the tape alphabet's size); but we make an exception when the input ins the null string, using a string containing one blank as the tape prefix, so that the invariant will be met.
The step procedure inputs a Turing machine and a configuration of it and outputs the next configuration (or the same configuration, if the current state is a stopping state). So we can start a Turing machine with its boot configuration and run it forward any specified number of steps; and we can perform an unbounded minimization to search for the smallest number of steps that convert the boot configuration into a configuration including qaccept.
By sectioning the unbounded minimization over the number of steps (fixing the input that specifies the encoding for the Turing machine), we get an acceptance function for the language that the Turing machine recognizes. So any Turing-recognizable language is recursively enumerable.
Given a partial recursive acceptance function, we can design a Turing machine that tries to compute that function and accepts just in case the computation terminates. So any recursively enumerable language is Turing-recognizable.
The essential equivalence of recursive sets and decidable languages follows as a corollary.
Study questions
- Prove that runs-forever? is not a partial recursive function.
- Prove that, for every natural number n, there is a binary, primitive recursive predicate hn that inputs the encoding for a Turing machine M and the encoding for an input string s to that machine and outputs 1 if M accepts s in n steps or fewer and 0 otherwise.
- A singulary function f is recursively reducible to a singulary function g if, and only if, there is a total, singulary, partial recursive function h such that, for any natural number n, g(n) = f(h(n)). Prove that, if f is recursively reducible to g, and g is not partial recursive, then f is not partial recursive.
