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-15 22:13

>>32
don't moronically contradict themselves and lie to the halting function

So you're supposed to already know whether or not the program halts before you pass it to the halting function?

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