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


Habilidades: Programação C, Java, PHP

Ver mais: theory of algorithm, programming with algorithms, programming theory, code and theory, binary explained, binary code explained, binary algorithms, binary algorithm, algorithms-programs, algorithms programs, algorithms explained, algorithms defined, algorithm of programming, theory, theory of computation, tape, rating algorithm, M3, binary coder, opportunity prove, convert algorithm program, tape buyer, form complete computation, programming algorithms, convert algorithm php source code

Acerca do Empregador:
( 5 comentários ) United States

ID do Projeto: #3004660

Premiar a:


See private message.

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

4 freelancers are bidding on average $29 for this job


See private message.

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

See private message.

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

See private message.

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