RACSO
R
DFA
CFG
Operations:
Reg
,
CF
PDA
Reductions:
K
,
WP
,
CFG
,
NP
,
SAT
ANTLR:
lex
,
syn
Exams
log in
,
register
,
guest
This site uses cookies only for the purpose of identifying user sessions. This is required to properly register actions.
Exercise 1
›
:
K
≤
{
p
∣
∃
y
:
M
p
(
y
)
↓
}
K\;\leq\;\{ p \mid \exists y:\;M_p(y){\downarrow} \}
K
≤
{
p
∣
∃
y
:
M
p
(
y
)
↓
}
Reduce
K
K
K
to the set of natural numbers codifying programs such that the program halts with some input (roughly, the set of programs that halt with some input), in order to prove that such set is undecidable (not recursive).
Authors:
Carles Creus, Guillem Godoy /
Documentation:
input y { // Write the code for program 'p' here... }
To be able to submit you need to
log in
,
register
, or
become a guest
.