|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |