![](/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) |
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) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Kevin Wampler wrote:
> 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
I didn't say it was impossible. I said it was illogical, by which I meant
logically contradictory. I don't think you can use algorithmic logic to
disprove the existence of everything that isn't algorithmic logic.
> still possible to logically reason to a degree about things which are
> non-computable,
Sure.
> and certainly no logical contradiction in asserting the
> existence (at least in a Platonic sense) of things which aren't computable.
Logical inevitability, actually, since we've already proven such things
exist logically.
> 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.
Well, the usual argument is that God can't exist because the following
features of God are logically contradictory: Omniscience, free will,
omnipotence, etc etc etc.
I'm pointing out that if you accept God is omniscient at all, then you have
proven that God is not constrained by (formal) logic, at which point trying
to prove his nonexistence via logic isn't going to work. Or you're going to
have to use some other form of logic (maybe one that's paraconsistent) in
order to reason logically about omniscient creatures.
--
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) |