2 ms·
> there is no algorithm for deciding if an arbitrary given program halts. But can you prove that statement if I change it into: there is no algorithm for deci
by amelius 4y ago
> there is no algorithm for deciding if an arbitrary given program halts.
But can you prove that statement if I change it into:
there is no algorithm for deciding if an arbitrary given program with size less than N halts; for some suitable definition of size.
- xigoi 4y agoSince we're considering practicality, let's change the statement to: “There is no algorithm for deciding if an arbitrary given program with size less than 1000 bytes halts which can be implemented without solving several famous open mathematical problems”. I think my program pretty clearly shows that this is true.