Deutsch English Français Italiano |
<vb6i8p$39fhi$1@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!news.misty.com!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko <mikko.levanto@iki.fi> Newsgroups: comp.theory Subject: Re: Defining a correct halt decider Date: Tue, 3 Sep 2024 11:44:09 +0300 Organization: - Lines: 22 Message-ID: <vb6i8p$39fhi$1@dont-email.me> References: <vb4npj$1kg8k$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 03 Sep 2024 10:44:10 +0200 (CEST) Injection-Info: dont-email.me; posting-host="4d0c86081244eebfddf3fd229f0dd949"; logging-data="3456562"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX194s7AXdrTpf5HR6VcmfQLJ" User-Agent: Unison/2.2 Cancel-Lock: sha1:DNKiSCQ6pHB8YEjVbUvAuwxlwTo= Bytes: 1796 On 2024-09-02 16:06:11 +0000, olcott said: > A correct halt decider is a Turing machine T with one accept state and > one reject state such that: > > If T is executed with initial tape contents equal to an encoding of > Turing machine X and its initial tape contents Y, and execution of a > real machine X with initial tape contents Y eventually halts, the > execution of T eventually ends up in the accept state and then stops. > > If T is executed with initial tape contents equal to an encoding of > Turing machine X and its initial tape contents Y, and execution of a > real machine X with initial tape contents Y does not eventually halt, > the execution of T eventually ends up in the reject state and then > stops. Your "definition" fails to specify "encoding". There is no standard encoding of Turing machines and tape contents. -- Mikko