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
,
is recursive by the-comp-enum-compl which 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.
its simply because if
was computable then by the reduction
with the reduction function being
, we would have that
is also computable (by the-reducibility-1) which it isnt, giving us a contradiction.
being
and
being
gives us a counter example.
a similar problem was in computability course homework 2.
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.