RACSO
DFA
CFG
Operations:
Reg
,
CF
PDA
Reductions:
K
,
WP
,
CFG
,
NP
,
SAT
ANTLR:
lexical
,
syntactic
Exams
log in
,
register
,
become guest
This site uses cookies only for the purpose of identifying user sessions. This is required to properly register actions.
Exercise
‹
2
›
:
K
‾
≤
{
p
∣
∀
y
:
M
p
(
y
)
↓
}
\overline{K}\;\leq\;\{ p \mid \forall y:\;M_p(y){\downarrow} \}
K
≤
{
p
∣
∀
y
:
M
p
(
y
)
↓
}
Reduce
K
‾
\overline{K}
K
to the set of natural numbers such that the program codified by them halts with any input (roughly, the set of programs that halt with any input), in order to prove that such set is not semi-decidable (not recursively enumerable).
Authors:
Carles Creus, Guillem Godoy /
Documentation:
input y { // Write the code for program 'p' here... }
To be able to submit you need to either
log in
,
register
, or
become a guest
.