+?HAJA KIL=>EEJO HAIKJI

Concrete unsolvability results

• Unfortunately most of computer science problems are unsolv- able!

• Rice's theorem: nearly all problems about functionalities of programs (their semantic properties) are unsolvable.

Halting problem of Turing machines

• Only partially solvable, i.e. recursively enumerable but not recursive

• Idea: We can always nd out with universal machine, if the other machine halts, but we will never nd out, if it doesn't

• To prove the unsolvability, we reduce the problem to a known unsolvable problem (U)

1

H is recursively enumerable but not recursive

Theorem: Language

H = {c_Mw | M halts on input w}

is recursive enumerable but not recursive.

Proof: i) H is recursive enumerable:

• Universal machine M_U can be easily modied to a machine c_Mw, which simulates computation of M on input w and which halts on accepting state, if the simulated computation halts at all.

ii) H is not recursive:

• Suppose that we had H = L(M_H) for some total Turing machine M_H.

• Let's also assume that machine M_H leaves the original input on the tape, when it halts.

• Let M_U be the universal machine, we constructed earlier.

• Now we could construct a total machine for U by combining machines M_H and M_U in the following way:

MH

cMw MU

• But we know that such total universal machine for language U doesn't exist! Contradiction ⇒ H cannot be recursive. 2

3

This means that the complement problem, Non-halting problem is totally unsolvable:

⇒ Corollary: Language

H˜ = {c_Mw | M doesn't halt on x}

is not recursive enumerable. 2

The same result by Pascal

Correspondence between Turing machines and common programs:

Turing machine formalism ∼ programming language

Turing machine ∼ program

Code of Turing machine ∼ assembler representation Universal machine ∼ assembler interpretator

• Because every TM can be implemented as Pascal program and vice versa, the results for TM's hold directly for also Pascal programs.

• For example halting problem interpreted by Pascal notation:

there doesn't exist total Pascal program, which decides if the given Pascal program P halts on given w.

5

The proof by Pascal:

Let's suppose we could make a total Pascal function:

function H(p, w : text) : Boolean,

which gets value true, if the procedure described by string pa- rameter p halts on input esittämä w, and false otherwise.

Let's now write another Pascal-procedure Hˆ: procedure Hˆ(p : text);

function H(p, w : text) : Boolean;

begin {Function H } . . .

end;begin {Main program}

if H(p, p) then while true do;

end.

hˆ=code of Hˆ

Computation of Hˆ by its own code causes contradiction:

Hˆ(ˆh) halts ⇔ H(ˆh,h) =ˆ false

⇔ Hˆ(ˆh) doesn't halt.

So a total halting checker program H cannot exist.

General contradiction method for proving un- solvability

Other properties of Turing machines can be proved unsolvable in the same way. The general idea is following:

Problem: is property P solvable?

1. Suppose it is. Thus we have a tota Turing machine M_P, which solves it.

2. Construct a new machine M_P⁰ , which perform property P, if the input machine does not have the property:

MP Perform P

M P’

C M w

3. Give to M_P as input the code of M_P⁰ and test, what happens.

4. If you get contradiction, then such M_P does not exist!

7

Unsolvability of semantic properties

• Semantic property of a Turing machine M is any property S, which depends on only the language recognized by M.

• It does not depend on the structure of M = syntactic prop- erties.

• A semantic property S = any collection of recursive languages in alphabet {0,1} and machine M has property S, if L(M) ∈ S.

Examples of semantic properties:

• M accepts empty string.

• M accepts some string.

• M accepts innitely many strings.

• the language recognized by M is regular.

Examples of syntactic properties:

• M contains transition δ(q, a) = (q⁰, b, R)

• If M starts with empty tape, it reaches state q with at most 5 steps.

• With some computation M reaches state q

• With some computation M reaches state q⁰ q

Some denitions

• A property is called trivial, if no Turing machine or all Turing machines have it. I.e. properties S_∅ (no machine has) andS_RE (all machines have).

• A property S is solvable, if given the Turing machine code c_M, we can computationally conclude, if M has the property.

I.e. set

codes(S) = {c | L(M_c) ∈ S}

is recursive.

• Syntactic properties can be easily recognized computationally But there are no computational means to recognize (nontriv- ial) semantic properties! = Rice's therem.

• ⇒ All run-time properties of computer programs are unsolv- able!

Rice's theorem

Rice's theorem: All nontrivial semantic properties of Tur- ing machines are unsolvable.

*Proof: See e.g. Hopcroft Ullman.

9

Other unsolvable problems

• Unsolvability of predicate calculus;

Church/Turing 1936

There isn't algorithm, which solves, if the given 1. order pred- icate calculus equation φ is valid (logical true, can be proved from axioms of calculus.)

2

• Hilbert's 10. problem ;

Matijasevitsh/Davis/Robinson/Putnam 195370 There isn't algorithm, which solves, if the given integer fac- tored polynom P(x₁, . . . , x_n) is nullable by integer values of

variables. (i.e. such (m₁, . . . , m_n) ∈ Zⁿ, for whichP(m₁, . . . , m_n) = 0)). Already unsolvable if the number of variables n = 15 or

degree of polynom deg(P) = 4. 2

• Some important problems about formal languages are un- solvable. Let's have grammars G and G⁰ in some level i of the Chomsky hierarchy and string w. In the table R ∼ solvable, E ∼ not solvable, T ∼ always true.

Taso i:

Problem: is 3 2 1 0

w ∈ L(G)? R R R E L(G) = ∅? R R E E L(G) = Σ^∗? R E E E L(G) = L(G⁰)? R E E E L(G) ⊆ L(G⁰)? R E E E L(G) ∩ L(G⁰) = ∅? R E E E

L(G) regular? T E E E

L(G) ∩ L(G⁰) of type i? T E T T L(G) of type i? T E T E

11

Some funny unsolvable problems

Busy beaver: Given number of states k, invent a k-state TM, which writes as many 1's onto tape before it halts (it has to halt nally)!

E.g. the following 3-state machine writes maximum 6 characters:

1/1,L 1/1,R

</1,L 1/1,R

0 1 2 ok

</1,L

</1,R

Post correspondence problem (PCP): Given a collection P = [_s^t1

1],[_s^t2

2], ...,[_s^tk

k], is there any index sequence i₁, i₂, ..., i_n, such that s_i1s_i2...s_in = t_i1t_i2...t_in?

E.g. if we have domino tiles [_ca^b ],[_ab^a],[^ca_a ],[^abc_c ], can you construct a sequence, which has the same string in both rows? One solution is [_ab^a ][_ca^b ][^ca_a ][_ab^a ][^abc_c ].

Tiling problem: Giving a collection of tile types and a tiling pattern, can you ll any size of square-formed oor?

Kuva 1: With these three tile types you can ll any square oor, when we demand that the same coloured sides are always next to each other.

Kuva 2: Example tiling.

Kuva 3: With these three tile types you cannot ll any square oor. Try e.g. 3×3 oor!

13

HEURISTIC RULES FOR PROVING SOLV- ABILITY / UNSOLVABILITY

1. PROVE PROBLEM SOLVABLE (LANGUAGE RE- CURSIVE)

• invent a total Turing machine (it can be also multiple track or multiple tape or nondetermiministic TM), which solves the problem (or nite automata, pushdown automaton, regular expression, context-free or context-sensitive grammar). OR

• invent some Turing machine for both problem A and its com- plement A OR

• combine solution machine from total submachines OR

• reduce to some known solvable problem

2a. PROVE THAT PROBLEM IS AT LEAST PAR- TIALLY SOLVABLE (LANGUAGE REC. ENUMER- ABLE)

• invent some Turing machine (it can be also multiple track or multiple tape or nondeterministic TM), which solves problem (it doesn't have to halt always, in language recognition only

"yes-cases).

→ can be made from universal TM : simulate other machines to study their properties OR

• give unstricted grammar OR

• combine solution machine from some submachines OR

• reduce to some known partially solvable problem

2b. PROVE THAT PROBLEM IS ONLY PARTIAL- LY UNSOLVABLE (LANGUAGE RECURSIVE ENU- MERABLE, BUT NOT RECURSIVE)

• show that its complement problem (language) is totally un- solvable (not recursive enumerable) OR

• reduce some known partially solvable problem (e.g. universal language U) to unknown one in question OR

• show that if solving machine is total, it causes contradiction

15

COUNTER EXAMPLE METHOD Is property P solvable?

1. suppose it is. Then we have total TM M_P, which solves it.

2. construct a new machine M_P⁰ , which performs P if the input machine doesn't.

MP Perform P

M P’

C M w

3. test M_P with code of M_P' as its input.

4. if contradiction, then such machine M_P cannot exist !

EXAMPLE: total halting tester machine M_H : cannot exist :

H H^

:

Now c⁰ causes problem for M_H !

3. PROVE UNSOLVABLE

• show that problem concerns some nontrivial semantic prop- erty of TM's. (Rice)

→ can be partially solvable

→ if complement is partially unsolvable, then it must be to- tally unsolvable (if it is sem. property) OR

• reduce some known totally unsolvable problem (e.g. diagonal language D) to unknown one OR

• show that its solvability (such TM) would cause contradiction Meditate this:

UNSOLVABILITY OF A PROBLEM IS COMPUTA- TIONALLY UNSOLVABLE PROBLEM!

17

Final words

What can you say about the time complexity of problems in dierent classes of Chomsky hierarchy?

{a b c | i=j tai j=k }i j k

kielet äärelliset

tunnistus:

äärellinen automaatti (rajall. muisti) k k

k {a b }

{a } kontekstiton kielioppi

tunnistus:

epädeterministinen pinoautomaatti

{ww }R

kielet, joilla on yksiselitteinen rajoitettu

i i i {a b c | >=0 } tunnistus: Turingin kone, jonka tyotila lineaarisesti

Kontekstiset kielet

Kontekstittomat kielet

Säännölliset kielet =lineaariset kielet

deterministiset

pinoautomaatti kontekstittomat kielet

tunnistus: deterministinen Ratkeamattomat ongelmat ei ole olemassa edes hyvaksyvassa tapauksessa

pysahtyvaa Turingin konetta Universaalikielen komplenmentt:i

kone−syote−parit, missa kone ei hvaksy syotetta

Rekursiivisesti numeroituvat kielet tunnistus: Turingin kone, joka pysahtyy ainakin

hyvaksyvassa tapauksessa

Universaalikieli:

kone−syote−parit, missa kone hyvaksyy syotteen

tunnistus:

universaalikone Rekursiiviset kielet

tunnistus: totaalinen Turingin kone