4.1 Rice's Theorem, the Church-Turing Thesis and Time Complexity

What is a TM property?

A characteristic that is defined by the language it accepts, not the specific description of a machine itself.

What is a language property of a TM?

A property P, if for every TM M having a property P and every TM M’ with L(M) = L(M’), M’ has property P

Is “Λ ∈ L(M)” a language property? and why?

Yes.

Properties are about the strings that the TM accepts. If a TM accepts Λ, then another TM that has the exact same language must also accept Λ. And same if the first TM does not accept Λ.

“M halts on every input” is this a language property and why?

No. This is because it is about the behaviour of the machine, rather than the string it accepts.

When is a language property trivial?

If every TM has property P or no TM has property P or no TM has property P. i.e. if it is the same for all languages of all TMs

Is L(M) is semidecidable a trivial property?

Yes

What is a nontrivial language property?

Means there must be machines that must have the property and there must be other machines that do not have the property

Is “L(M) = ∅” trivial or nontrivial?

Non trivial - there is existing TMs that accept just ∅, and there are existing TMs that do not accept ∅.

Is “L(M) is regular” trivial or nontrivial?

Nontrivial

What is Rice’s Theorem?

Every nontrivial language property of TM is undecidable. For each property P, the P-problem is undecidable.

What is the P-Problem?

Input: TM M
Question: Does M have property P?

Proof if a TM M has a property P

We show that the Accept-Λ problem (A-Λ) is reducible either to P-P or to its complement P-P (with a line at the top). This is sufficient because P-P is decidable if and only if its complement is decidable.

Let M∅ be a TM which rejects every input. If M∅ does not have a property P, then we reduce A-Λ to P-P, otherwise reduce A-Λ to complement of P-P

What is a first-order formula?

A formal logical statement used to describe the behaviour and configurations of a tm using a specific language of variables, functions, predicates and logical operations.

What is the Entscheidungsproblem?

Input: A first-order formula F.
Question: Is F true in all structures? (Is F universally true)

Is the Entscheidungsproblem decidable, semidecidable, or undecidable?

Undecidable

What is the Finitary Entscheidungsproblem and is it decidable, semidecidable or undecidable?

Input: A first-order formula F.
Question: Is F true in all finite structures?

The finitary Entscheidungsproblem is undecidable.

What is the Church-Turing Thesis?

Every effective prodecure can be carried out by a Turing Machine.

What is the time complexity of a (possibly nondeterministic) TM?

the function τ_M : N → N, where τ_M(n) is the maximum number of transitions M can make on any input of length n.