difference of 2 partial computable algorithms

32 Views Asked by At

I have 2 algorithms

Algorithm 1:

if( Condition1(input)==true )
   print(input);
else
   loop forever;

Algorithm 2:

if( Condition2(input)==true )
   print(input);
else
   loop forever;

for any arbitrary fully-computable condition 1 and 2.

We know both of this algorithm is partial computable.

i want to write a new algorithm (algorithm 3) by this definition.

Algorithm 3:

if (Condition1( input ) ==true) and (Condition2( input ) ==false) 
    print input;

Can i write algorithm3??? and how???

HINT: main problem is: can i write if( Condition2( input ) ==false )???

2

There are 2 best solutions below

3
On

If I didn't misunderstood you, what you require is not possible. If x is not printed by algorithm 1, then it will loop forever, never getting into condition 2, much less 3. Now, if you want to write algorith 3 by itself, I think the way you did it is correct.

1
On

Replaced: Sure you can do that. You have two conditions. The easiest way is to evaluate them first, evaluate the conjunction, print the input if the conjunction is true, then go on to the two loops you show. You alternate between steps of each algorithm. If they both terminate, you will evaluate the conjunction. Otherwise, you will be looping before the conjunction, but it appears that is what you want anyway.

Added: for the new main problem, sure you can. It will never be satisfied, because if Condition2 is false you loop forever in algorithm2. But you can write it. It is not a syntax error.