Is it possible for a non-deterministic turing machine to solve the halting 
problem of deterministic turing machines?  That is, can I use a NDTM as an 
oracle for DTMs?  I don't think so, right?  There's no way to check your 
guess is correct, basically?

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

On 11/10/2010 7:23 PM, Darren New wrote:
> Is it possible for a non-deterministic turing machine to solve the
> halting problem of deterministic turing machines? That is, can I use a
> NDTM as an oracle for DTMs? I don't think so, right? There's no way to
> check your guess is correct, basically?
>

Since you can simulate a NDTM with a DTM (at the expense of an 
exponential increase in time), no.

Post a reply to this message

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.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

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

Kevin Wampler wrote:
> As a sort of philosophical point,

It actually came up during an argument someone was making, pointing out that 
an omniscient god is contradictory to free will.  I simply pointed out that 
an omniscient god is contradictory to logic at all, free will or not, so 
trying to use logic to disprove the existence of an omniscient god is silly.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

On 11-11-2010 21:34, Darren New wrote:
> Kevin Wampler wrote:
>> As a sort of philosophical point,
>
> It actually came up during an argument someone was making, pointing out
> that an omniscient god is contradictory to free will. I simply pointed
> out that an omniscient god is contradictory to logic at all, free will
> or not, so trying to use logic to disprove the existence of an
> omniscient god is silly.
>

So you are trying use logic to show that you can not use logic? Let's 
take this outside to the next metalevel.

Post a reply to this message

On 11/11/2010 12:34 PM, Darren New wrote:
> Kevin Wampler wrote:
>> As a sort of philosophical point,
>
> It actually came up during an argument someone was making, pointing out
> that an omniscient god is contradictory to free will.

To the best of my knowledge this argument was first dealt with (IIRC) by 
St. Augustine.  The analogy with the way in that that my knowledge of 
your *past* actions doesn't mean that they weren't made freely.  If 
you're willing at accept a view of God existing outside of time, then it 
doesn't seem to unreasonable to also posit that God's knowledge doesn't 
conflict with free will in much the same way.

It's been a while since I heard the argument though, so I'm probably 
missing some elements.


> an omniscient god is contradictory to logic at all

How so?  I only see an obvious argument like that for a particular sort 
of omnipotent God, rather than a merely omniscient one.

Post a reply to this message

andrel wrote:
> So you are trying use logic to show that you can not use logic? Let's 
> take this outside to the next metalevel.

No, my stance was that arguing logically about religion at all is silly. :-)

Primarily because you're talking about a supernatural being who by 
definition is outside the realm in which logic works.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

Kevin Wampler wrote:
> On 11/11/2010 12:34 PM, Darren New wrote:
>> Kevin Wampler wrote:
>>> As a sort of philosophical point,
>>
>> It actually came up during an argument someone was making, pointing out
>> that an omniscient god is contradictory to free will.
> 
> To the best of my knowledge this argument was first dealt with (IIRC) by 
> St. Augustine.  The analogy with the way in that that my knowledge of 
> your *past* actions doesn't mean that they weren't made freely.  If 
> you're willing at accept a view of God existing outside of time, then it 
> doesn't seem to unreasonable to also posit that God's knowledge doesn't 
> conflict with free will in much the same way.

That's generally the argument I've heard, yes. Or succinctly, it's not that 
God knows what you'll do, it's that God will always have known what you did. :-)

>> an omniscient god is contradictory to logic at all
> 
> How so?  I only see an obvious argument like that for a particular sort 
> of omnipotent God, rather than a merely omniscient one.

If God is omniscient, then he knows whether every program will halt or not.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

On 11/11/2010 1:23 PM, Darren New wrote:
>>
>> How so? I only see an obvious argument like that for a particular sort
>> of omnipotent God, rather than a merely omniscient one.
>
> If God is omniscient, then he knows whether every program will halt or not.
>

Sure, but I don't see how that's a logical contradiction.  All it means 
is that God has abilities/knowledge that are non-algorithmic (an 
assertion I'm sure would be agreed with by almost any theist).  It's 
still possible to logically reason to a degree about things which are 
non-computable, and certainly no logical contradiction in asserting the 
existence (at least in a Platonic sense) of things which aren't computable.

The furthest I can see your argument being pushed would be to limit the 
sort of reasoning we can apply when talking about God, where it implies 
that we can't know *everything* about God through logic, but I don't see 
how it implies that we can't know *anything*, or that the sort of 
omniscience you describe is incompatible with logic.

Perhaps I am misunderstanding the point you are making?

Post a reply to this message