# Theory of Computation - Undecidability

Homework Assigment for Theory of Computation

Nice opportunity to raise your **Coder Rating**!

**1**.Prove that the following properties are functional:

a) K1={

| P outputs 5 on the input 0 and does not halt on the input 5}.

b) K2={

| P does not halt on the input 5}.

**2**. Describe algorithms deciding the following properties defined:

a) M3= {

| starting on the empty tape, the program P reaches the given state q in at most 5 steps}.

b) M4={

| there exists a configuration of P with the given state p that yields a configuration with tthe given state q}.

**3**.Determine which of the following properties of programs are decidable. If property is decidable, briefly describe an algorithm deciding it. If property is undecidable, show that it is functional.

a) R1 = {

| P terminates on all even numbers}.

b) R5= {

| P contains no transition with the left-hand side (q,[_])}.

**4.** Convert the following transition to binary code:

a)((q3, a4) , (q4, -->))

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.

2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.

3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site).

## Platform

Word

( 5 comentários ) United States

ID do Projeto: #3004660

## Premiar a:

semaphoreinc

See private message.

\$38.25 USD em 2 dias
(7 Avaliações)
2.0

## 4 freelancers estão ofertando em média \$29 para este trabalho

jspsenthilvw

See private message.

\$25.5 USD in 2 dias
(22 Comentários)
3.9
hotsunvw

See private message.

\$29.75 USD in 2 dias
(7 Comentários)
3.2
icodeinc

See private message.

\$21.25 USD in 2 dias
(1 Comentário)
0.3