Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Halting problem = undecidability of all program properties?

Name: Anonymous 2016-09-14 3:28

[i]UNDERGRAD QUALITY[/i] incoming: An old thread on /math/ got me thinking about this. We know the typical proof uses
func G(x): if Halts(x, x) then loop forever
else false

and G(G) as a counterexample. Would this
func P(x): if ReturnsOdd(x, x) then 2
else 1

mean you can't prove a program always returns odd numbers because of P(P)? What about any other simple property like ``returns alphanumeric character'' or ``returns a valid s-expression''? You can always construct a function that ends in a contradiction by just returning the opposite thing.

Name: Anonymous 2016-09-24 2:30

Not sure whether OP is trying to be witty here, but isn't this exactly what Rice's theorem is about?

How come this thread has 56 replies and not a single person has pointed out OP is a retarded undergrad who just failed his first Automata Theory 101 exam?

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List