On 11/10/2010 9:31 PM, Darren New wrote:
> Kevin Wampler wrote:
>> Since you can simulate a NDTM with a DTM (at the expense of an
>> exponential increase in time), no.
>
> That's what I thought, but I'd figure I'd check.
>

As a sort of philosophical point, if you believe the Church-Turing 
thesis, then anything which could solve the halting problem for DTMs 
wouldn't resemble an "algorithm" and would instead have to be either a 
black box or quite bizarre.  You can often use this intuition to 
correctly eliminate whole classes of architectures since they still look 
"algorithmy", like NDTMs or QBIT-based quantum computers etc.  If you're 
interested in more, the keyword you're looking for is "hypercomputation".

Post a reply to this message