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