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 the-comp-K-1.
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 the-comp-K-1.
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 col-reducibility-1 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.
we can use the reducibility arguments to show that certain sets are not r.e. let
is not r.e.
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 :
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 prf-tot-not-re.
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 the-reducibility-compl we get and so by the-reducibility-1 we get and then by the-comp-enum-compl we get .
prove whether .
assume in contradiction that , then by the-reducibility-compl we have which would mean that by the-reducibility-1 because , then we have is recursive by the-comp-enum-compl 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.
to prove we consider the following reduction function: where:
we prove that this is indeed the desired reduction:
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 col-reducibility-1), 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).
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:
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 the-comp-enum-compl.
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 def-pairing-func-1.
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 the-bounded-min and so is primitive recursive aswell. and by def-prim-recurs-def-by-cases 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.