[ExI] The second step towards immortality

[Anders Sandberg]

On 11/01/2014 12:01, Ben wrote:
> I don't understand your 'nontrivial' example.  It does add two
> numbers(int z=x+y;), then it goes into a loop which goes round a few
> times until w is equal to 1, then it returns z.  So all we get is a
> delay in returning the answer.  If the answer is big enough, it may take
> a very long time to return it (disregarding things like the maximum size
> of an integer in the system executing the function), but it always does
> the calculation.  What have I missed?

https://en.wikipedia.org/wiki/Collatz_conjecture

Basically, it is not known whether that loop ever ends. For most numbers 
it quickly ends up at 1, but sometimes it rushes off to very large 
numbers. And Conway proved that fairly simple generalisations are 
algorithmically undecidable: you can literally turn software programs 
into rule sets like the above, and then the Halting Problems applies. So 
we know that in the general case there is no way to prove that the 
looping ever reaches 1. But we do not know if it applies in this 
particular case!

I find that very neat. I can write a program that I know I cannot 
predict (if I used the full Halting Problem case), but I can also write 
a program that I do not know if I can know whether I can predict (this 
one).


-- 
Anders Sandberg,
Future of Humanity Institute
Oxford Martin School
Faculty of Philosophy
Oxford University