Is instantiabilty of templated types decidable?

[Timon Gehr]

On 11/11/2012 09:40 PM, Nick Sabalausky wrote:
> On Sun, 11 Nov 2012 19:37:45 +0100
> Timon Gehr <timon.gehr at 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.