Is $K\times K$ in Turing machines semidecidable?

124 Views Asked by At

Classify as decidable, not decidable but semi-decidable, or nondecidable, this set: $K\times K$, the cartesian product.

$K$ is the set of words that halts with an input on Turing machine.

For example,

input y{
execute mx(y)
halt
}

If $Y$ belongs to $K$ it's going to halt. I know $K$ is not decidable but I don't know if $K\times K$ is semi decidable or not.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose we have a program that decides $K\times K$, e.g.

# Decider for K times K
def F(‹x,y›):
    if x in K and Y in K:
        return True
    else: return False

input = ‹x,y›
print(F(input))

Then we can use this program to decide $K$:

input = x
print(F(‹input,input›))