Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

To downgrade the human mind is bad theology. -- C. K. Chesterton


devel / comp.theory / Re: NDTM == DTM ?

SubjectAuthor
* NDTM == DTM ?wij
+* NDTM == DTM ?Richard Damon
|`- NDTM == DTM ?wij
`- NDTM == DTM ?Ben Bacarisse

1
NDTM == DTM ?

<6d759399-31f3-4f2a-a096-6422a139e603n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=37633&group=comp.theory#37633

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:6214:20a8:b0:477:1882:3e7 with SMTP id 8-20020a05621420a800b00477188203e7mr10916637qvd.44.1660500465598;
Sun, 14 Aug 2022 11:07:45 -0700 (PDT)
X-Received: by 2002:a81:5443:0:b0:329:cd12:e96 with SMTP id
i64-20020a815443000000b00329cd120e96mr10421869ywb.68.1660500465421; Sun, 14
Aug 2022 11:07:45 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sun, 14 Aug 2022 11:07:45 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=A1PyIwoAAACCahK0CVYFlDZG8JWzz_Go
NNTP-Posting-Host: 124.218.76.41
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <6d759399-31f3-4f2a-a096-6422a139e603n@googlegroups.com>
Subject: NDTM == DTM ?
From: wynii...@gmail.com (wij)
Injection-Date: Sun, 14 Aug 2022 18:07:45 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1306
 by: wij - Sun, 14 Aug 2022 18:07 UTC

Is NDTM computationally equivalent to DTM?
https://en.wikipedia.org
wiki/Nondeterministic_Turing_machine#DTM_simulation_of_NTM
Average books say yes, but I doubt. Reason is simple. The decision problems
DTM compute have to terminate, while NDTM is not required. The 'no' answer for
a NDTM is not required to compute, how can a DTM simulate such a case?

Re: NDTM == DTM ?

<19bKK.772052$zgr9.120054@fx13.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=37637&group=comp.theory#37637

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx13.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0)
Gecko/20100101 Thunderbird/91.12.0
Subject: Re: NDTM == DTM ?
Content-Language: en-US
Newsgroups: comp.theory
References: <6d759399-31f3-4f2a-a096-6422a139e603n@googlegroups.com>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <6d759399-31f3-4f2a-a096-6422a139e603n@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 27
Message-ID: <19bKK.772052$zgr9.120054@fx13.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sun, 14 Aug 2022 14:28:13 -0400
X-Received-Bytes: 2088
 by: Richard Damon - Sun, 14 Aug 2022 18:28 UTC

On 8/14/22 2:07 PM, wij wrote:
> Is NDTM computationally equivalent to DTM?
> https://en.wikipedia.org
> wiki/Nondeterministic_Turing_machine#DTM_simulation_of_NTM
> Average books say yes, but I doubt. Reason is simple. The decision problems
> DTM compute have to terminate, while NDTM is not required. The 'no' answer for
> a NDTM is not required to compute, how can a DTM simulate such a case?

Generally, a Non-Deterministic Turing Machine is defined to accept if
ANY of the multiple paths reaches an accept state.

One way to simulate a NDTM is to keep the history of states that you
have come from as you do a breadth first seach of states to see if you
find an accept state.

Note, a NDTM that isn't required to halt isn't a DECIDER, but just a
RECOGNIZER, and a DTM RECOGNIZER isn't required to halt either.

If you need a NDTM DECIDER, then ALL the branches DO need to reach an
explicit REJECT state for it to answer with REJECT.

It is just that DTM are more apt to be talked of as Deciders vs
Recognizers, while NDTM are more apt to just be talked about as a
Recognizer.

Thus, they can do exactly the same set of computations with the same
defined requirements, just at a different complexity level.

Re: NDTM == DTM ?

<8735dyabks.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=37647&group=comp.theory#37647

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: NDTM == DTM ?
Date: Sun, 14 Aug 2022 20:07:15 +0100
Organization: A noiseless patient Spider
Lines: 30
Message-ID: <8735dyabks.fsf@bsb.me.uk>
References: <6d759399-31f3-4f2a-a096-6422a139e603n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader01.eternal-september.org; posting-host="c77c5c3545a0b8a7133ba8ee9c2a9952";
logging-data="3408592"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/+Jw2wuAb7+gZP2HER/7oHTHCXgB6UqKQ="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:5hPAPKM7TG1CzrkcHsLXyq20u1U=
sha1:0va3icrlJvVzUfC/NzEMF61GhoI=
X-BSB-Auth: 1.0ee3597c453dfa16a08e.20220814200715BST.8735dyabks.fsf@bsb.me.uk
 by: Ben Bacarisse - Sun, 14 Aug 2022 19:07 UTC

wij <wyniijj2@gmail.com> writes:

> Is NDTM computationally equivalent to DTM?
> https://en.wikipedia.org
> wiki/Nondeterministic_Turing_machine#DTM_simulation_of_NTM
> Average books say yes, but I doubt. Reason is simple.

That should give you pause. Unless you think there is a deliberate,
decades-long conspiracy between thousands of authors, editors,
professors and researchers to hide the truth, simple mistakes like the
one you think you've spotted are not going go unnoticed.

> The decision problems DTM compute have to terminate, while NDTM is not
> required. The 'no' answer for a NDTM is not required to compute, how
> can a DTM simulate such a case?

A NDTM rejects an instance if, and only if, all paths lead to final
reject state. I think was it bothering you is that there is no way to
tell if this will ever happen. And you are right. Since halting is
undecidable for NDTMs and DTMs alike, there is no algorithm by which a
deterministic TM, simulating a non-deterministic TM, can tell when to
stop trying.

But every NDTM /decider/ either accepts or rejects. So an equivalent
DTM can just keep going because it will, also, eventually accept or
reject not matter what the input is. Any NDTM decidable set it
therefore also DTM decidable.

--
Ben.

Re: NDTM == DTM ?

<fdeb60d2-dfd1-4792-ba9c-887080440da7n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=37703&group=comp.theory#37703

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a37:43d2:0:b0:6b9:a7e2:ca24 with SMTP id q201-20020a3743d2000000b006b9a7e2ca24mr11004739qka.338.1660557599920;
Mon, 15 Aug 2022 02:59:59 -0700 (PDT)
X-Received: by 2002:a5b:289:0:b0:68b:73d6:79f4 with SMTP id
x9-20020a5b0289000000b0068b73d679f4mr1113335ybl.99.1660557599658; Mon, 15 Aug
2022 02:59:59 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 15 Aug 2022 02:59:59 -0700 (PDT)
In-Reply-To: <19bKK.772052$zgr9.120054@fx13.iad>
Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=A1PyIwoAAACCahK0CVYFlDZG8JWzz_Go
NNTP-Posting-Host: 124.218.76.41
References: <6d759399-31f3-4f2a-a096-6422a139e603n@googlegroups.com> <19bKK.772052$zgr9.120054@fx13.iad>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <fdeb60d2-dfd1-4792-ba9c-887080440da7n@googlegroups.com>
Subject: Re: NDTM == DTM ?
From: wynii...@gmail.com (wij)
Injection-Date: Mon, 15 Aug 2022 09:59:59 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2520
 by: wij - Mon, 15 Aug 2022 09:59 UTC

On Monday, 15 August 2022 at 02:28:16 UTC+8, richar...@gmail.com wrote:
> On 8/14/22 2:07 PM, wij wrote:
> > Is NDTM computationally equivalent to DTM?
> > https://en.wikipedia.org
> > wiki/Nondeterministic_Turing_machine#DTM_simulation_of_NTM
> > Average books say yes, but I doubt. Reason is simple. The decision problems
> > DTM compute have to terminate, while NDTM is not required. The 'no' answer for
> > a NDTM is not required to compute, how can a DTM simulate such a case?
> Generally, a Non-Deterministic Turing Machine is defined to accept if
> ANY of the multiple paths reaches an accept state.
>
> One way to simulate a NDTM is to keep the history of states that you
> have come from as you do a breadth first seach of states to see if you
> find an accept state.
>
> Note, a NDTM that isn't required to halt isn't a DECIDER, but just a
> RECOGNIZER, and a DTM RECOGNIZER isn't required to halt either.
>
> If you need a NDTM DECIDER, then ALL the branches DO need to reach an
> explicit REJECT state for it to answer with REJECT.
>
> It is just that DTM are more apt to be talked of as Deciders vs
> Recognizers, while NDTM are more apt to just be talked about as a
> Recognizer.
>
> Thus, they can do exactly the same set of computations with the same
> defined requirements, just at a different complexity level.

OK, that makes sense, thanks.

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor