hoary hatch
I somehow can come up with an algorithm but I find it hard to prove the correctness( in pseudocode):
Input: w
Output : 1
n <- 0
if w is a proper encoding of a Turing Maschine then{
while (T(M_w) \cap {0,1}^n != empty set){
n <- n + 1
}
}
return 1;
On the other hand, I tried a reduction TO the Halting Problem, A<=HP, but somehow I can't connect the idea of halting and accepting at the end. Maybe somebody can give me some insight into this. I am starting to believe it is not semi-decidable.
raven harness