On 11/11/2012 09:40 PM, Nick Sabalausky wrote:
On Sun, 11 Nov 2012 19:37:45 +0100
Timon Gehr <timon.g...@gmx.ch> wrote:
On 11/11/2012 03:45 PM, Peter Alexander wrote:
Collatz sequence.
struct Collatz(int n)
{
enum next = n % 2 == 0 ? n / 2 : 3 * n + 1;
Collatz!(next)* foo;
}
It's an unsolved problem in mathematics whether or not this
instantiates an infinite number of templates.
The possible inputs are finite, so the property is decidable.
Technically, yea, but I think upwards of ~4 billion template
instantiations is quite unrealistic, to the point of being effectively
undecidable.
Undecidability has a precise definition in theoretical computer science.
It means that there is no algorithm that implements the given predicate.
It is a lot stronger than impracticality of implementation.
I claim that the following, very simple algorithm decides whether or not
the template above terminates instantiation without errors with the
given parameter:
bool collatzTerminates(int n){ return true; }
Therefore, a conforming D compiler implementation could evaluate the
template above lazily.
