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
‹
14
›
:
K
≤
{
⟨
p
,
q
⟩
∣
∃
y
:
(
M
p
(
y
)
↓
∧
M
q
(
y
)
↓
)
}
K\;\leq\;\{ \langle p,q\rangle \mid \exists y:\;(M_p(y){\downarrow} \,\wedge\, M_q(y){\downarrow}) \}
K
≤
{⟨
p
,
q
⟩
∣
∃
y
:
(
M
p
(
y
)
↓
∧
M
q
(
y
)
↓
)}
Reduce
K
K
K
to the set of pairs of natural numbers codifying programs halting with a common input (roughly, the set of pairs of programs which stop with the same common 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... } input y { // Write the code for program 'q' here... }
To be able to submit you need to either
log in
,
register
, or
become a guest
.