computability practice problems

<2024-06-06 Thu 19:25:17> mahmood
cs college1
let . prove: isnt computable. ( is encoded, and are inputs to the program).
let . prove that this language isnt computable.
assume in contradiction that is computable and that the predicate is given, consider the following program:
this program acts as a computable predicate for , giving us a contradiction with computably_enumerable_set.html.
in we would define as:
we make sure the program we construct indeed accepts only 4 arguments so that , making the sub-program only diverge iff converges, i.e. . giving us a contradiction with computably_enumerable_set.html. hence .
if is decidable then we have a predicate that decides it. we can use that predicate to check whether a function with an input and the single instruction would halt, giving us a predicate for deciding which contradicts with computably_enumerable_set.html. hence .
we define . we prove that isnt computable.
assume in contradiction that is decidable set by . consider the following program
assume , then , then , then , then 1 is returned. assume , then , then , then , then 0 is returned. then this program behaves as a computable predicate for , giving us a contradiction with computably_enumerable_set.html.
prove that the following predicate isnt computable.
assume in contradiction that is computable by .
consider the following program:
we have
this program behaves as a characteristic predicate of , giving us a contradiction with computably_enumerable_set.html.
prove that the following predicate isnt computable.
assume in contradiction that is computable by .
consider the following program, which we prove is a computable predicate giving us :
we have
giving us the desired contradiction.
prove that the following predicate isnt computable.
assume in contradiction that is computable by , consider the following program that computes .
we have
giving us the contradiction.
given the relation
where is the set in the hierarchy of computability?
we prove that such that and is the complement of .
we prove that this is indeed the required reducibility:
we assume in contradiction that , by the reduction we get a contradiction.
given the relation
where does fit in the hierarchy of computability?
we prove that and prove that , we consider the following reduction and prove that it is the necessary reduction. consider a computable function that is used to apply the reduction. consider the following program :
assume , this gives .
assume , this gives .
assume in contradiction that , by the reduction we get a contradiction.
consider the relation
where is in the hierarchy of computability?
to prove that . we write a predicate that runs and in parallel, if one of them stops it stops.
to prove , by turing_reducibility.html it is sufficient to prove . consider the following reduction, :
we show that this is indeed the required reduction:
assume that , this gives . assume that , this gives . assume in contradiction that , by the given reduction we get a contradiction.
consider the function
this function acts as a reduction from to . for every program number (i.e. is the encoding of a program ), the function returns the code of the following program :
ignores its inputs and runs the given program on .
the given reduction function is computable: we can write an algorithm that receives and returns the encoding of the program (the encoding function should be computable).
we have :
we have shown the reduction from , since isnt computably enumerable, we have that is also not computably enumerable.
both and are m-complete.
this proof is for , the proof for is very similar.
we know that by definition, let , which gives us a program that accepts . we define such that:
we show that this is the necessary reduction:
is not recursively enumerable.
let
we have .
same as tot.html.
prove or disprove: there exists such that .
assume in contradiction that that exists a reduction function , there has to be some but because , but we have which means that is in the domain of which is , this gives us a contradiction, meaning that , otherwise there is no such a reduction function.
prove or disprove: let be -complete, let be nonrecursive, then isnt recursive.
counter example: , we have and is computable.
prove or disprove: given is a reduction function from to , and the same is a reduction function from to , then .
counter example: let be the even numbers, let be the odd numbers , the reduction function works for both directions, and we have .
prove or disprove: given and then .
because by turing_reducibility.html we get and so by turing_reducibility.html we get and then by computably_enumerable_set.html we get .
prove whether .
assume in contradiction that , then by turing_reducibility.html we have which would mean that by turing_reducibility.html because , then we have is recursive by computably_enumerable_set.html and this contradicts with the noncomputability of the halting problem.
prove or disprove: given , then .
since we have a computable function that tests for membership in . since there exists some and since there exists some , we define the following reduction function:
for some arbitrarily chosen , the given reduction function works in both directions.
disprove: .
counter example: let be the even numbers and the odd numbers, and let be multiples of 3.
let , where is in the hierarchy of computability?
. we prove this by showing : consider the reduction function where:
the reduction is shown to be correct by:
assume in contradiction that by the reduction we get which gives us the desired contradiction.
compare the problem above to this problem, where the number of values the functions in the given set is not strictly 2 but bigger or equal to 2, which gives us the ability to loop "in parallel" on all values in and run the input function on them using to check whether we've crossed 2 convergences or not, in the previous problem this wouldnt be a correct solution because we cant tell if we'd have come across more convergences than 2 if we would continue iterating.
let , where is in the hierarchy of computability?
, we run in parallel on every input from and count the number of inputs that converges on. if converges on 2 inputs we converge. if we would find out eventually and halt, otherwise we would diverge, which means that accepts , implying that is computably enumerable.
to show that isnt decidable, we show that , which means that since isnt computable, we have by turing_reducibility.html that is also not copmutable.
to prove we consider the following reduction function: where is defined by:
we prove that this is indeed a good reduction function:
define a primitive recursive function for which .
for , encoded with godel numbering.
if isnt enumerable and isnt enumerable, then isnt enumerable.
let . show where fits in the hierarchy of computability.
prove that the following function is primitive recursive.
let , we show that the function is primitive recursive and simply define . let , and
let be a non-empty recursively enumerable set, and let . is the set computably enumerable?
we can simply define the following function that accepts :
where is a computable function that accepts which has to exist because is recursively enumerable.
prove/disprove: let be a total noncomputable function, and let be a primitive recursive function, then the function isnt computable.
being (predicate for membership of ) and being gives us a counter example.
show where the following set belongs in the hierarchy of computability.
it isnt computable because (by turing_reducibility.html), it is computably enumerable because (we could iterate to find the value for which the functions converge using and use that to construct a function that converges on itself and diverges otherwise).
if then every broken link: blk:def-lang that is different from and from is \(\compNP\)-complete.
at first this seemed to be false, but after some thought, any NP-decidable set would have an NP-reduction from itself to any non-empty that isnt . take for example, the reduction function would use the NP-predicate of the NP-hard language to return 1 if the input is in the set and some other number otherwise.
where the set of functions that accept an odd number of inputs fits in the hierarchy of computability.
noncomputably enumerable, tot can be reduced to it.
specify where the following set fits in the hierarchy of computability.
prove that the computably enumerable sets are closed under union
given two computably enumerable sets, and , we have the program and , that accept and , respectively. for their union, we can construct the following program in S programming language that recognizes it.
the following problem i think is one of my favorites, it demonstrates how we can use bruteforce in a solution, like in computability_practice_problems.html.
let then .
if then there exists a computable predicate that checks whether . we write the following program that acts as a predicate for whether :
we construct the reduction function :
where is the following function:
prove/disprove: if is computably enumerable and is computably enumerable then is computably enumerable.
a counter example: . is basically which is not computably enumerable because otherwise would be decidable set (since we'd be assuming both and are enumerable and that implies is decidable) which isnt the case. (i guess we'd technically have to say since is a set of 2-tuples where program halts on input ), and is reducible to by the standard pairing function anyway wich makes it computably enumerable because is.
apparently a simpler example would be , we have which isnt computably enumerable because otherwise would be decidable set by computably_enumerable_set.html.
if is not m-complete then .
there are 3 cases:
  • is decidable (which means its not -complete), its easy to show a reduction .
  • is recursively enumerable but not -complete and not decidable, which means cannot be recursively enumerable (i cant find a reduction from to , although a reduction from to is trivial).
  • is not recursively enumerable.
im finding it hard to even think of a recursively enumerable set that isnt -complete.
is not r.e. but if it were reducible to then would be reducible to which would make r.e. but it isnt.
if then there exists no such that is NP-complete.
i cant see why the first statement would imply the non-existence of an NP-complete set, SAT problem would be NP-hard and hence NP-complete either way since every other problem in (and hence would still be reducible to it.
given the function for encoding two natural numbers is
we write and define . prove that is a primitive recursive function
it is shown in pairing_function.html.
prove that the following function is primitive recursive
we define the following primitive recursive function:
then we can derive the following function which would be primitive recursive aswell:
we have .
we define the function in the following manner:
prove that is primitive recursive.
we construct the primitive recursive function :
let , we have , therefore is recursive.
given
check where both and belong in the hierarchy of computability.
it is easy to show that isnt decidable by assuming it true in contradiction and showing that it would lead to a computable predicate for membership in .
at first, i thought the set was r.e. by reducing it to using the fact that its members converge on 0, but non-members could also converge on 0 if they dont diverge on 1, and so the reduction that i had shown was incorrect.
the given set is also non-r.e., we can show this using by showing a reduction or .
if is a primitive recursive relation then , defined as
is a primitive recursive function.
the function is primitive recursive
consider the function
is primitive recursive by unbounded_search_operator.html and so is primitive recursive aswell. and by primitive_recursive_predicate.html the function desired can be defined as:
is primitive recursive too.
the function
is primitive recursive.
consider the function
is primitive recursive because the relation is.
the function that generalizes the example because 3 is 11 in binary form, and 100 is 4 in binary, which gives 11100 in binary which is the binary representation of the decimal 28.
let denote the length of digits in the binary representation of . we have
we have is primitive recursive, and exponentiality is primitive recursive as well as addition and multiplication and so is primitive recursive by composition.
the function giving the fibonacci sequence, i.e. , is primitive recursive.
let , if we show that is primitive recursive then we can simply define .
because we were able to define in terms of and other p.r. functions we know is p.r.