Codex Wiki
OurBigBook.com
Site
Source code
Totality problem
...
Mathematics
Area of mathematics
Foundations of mathematics
Computability theory
Arithmetical hierarchy
Pi-2 set
OurBigBook.com
Words: 36
For an effective enumeration of computably enumerable languages
W
v
, the totality problem is
Tot
=
{
v
:
W
v
=
W
}
.
(32)
It is
Π
2
-complete: a
Π
2
condition
w
∈
P
⟺
∀
x
f
(
w
,
x
)
↓
maps effectively to a program whose domain is
{
x
:
f
(
w
,
x
)
↓
}
.
Ancestors
(7)
Pi-2 set
Arithmetical hierarchy
Computability theory
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(1)
Solution