Path: ...!buffer1.nntp.dca1.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 11 May 2022 22:29:37 -0500
Date: Wed, 11 May 2022 22:29:34 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
 transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
 <0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
 <rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
 <ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
 <adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
 <874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
 <87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
 <f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
 <ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
 <QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
 <eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
 <d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
 <t5gkl6$8og$1@gioia.aioe.org>
 <0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
 <t5hf7p$1kd4$1@gioia.aioe.org>
 <aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>
 <t5htes$1hb4$1@gioia.aioe.org>
From: olcott <NoOne@NoWhere.com>
In-Reply-To: <t5htes$1hb4$1@gioia.aioe.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <IIadnewQP-K84uH_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 138
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-30znopB1imvS8q6zU99myD+zCd/CydlLTy7LlMlk9yqVxvmfTzsXWRJlcjUqxrw/V8jx9m1cEBJpLTM!seT/UESBJmh6KhObhOxzKk68o+Drn7P+NQLQFxQYnxj2nMCpcDcTIppacXBWDMiSPMVuGsBJJT0=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 8825

On 5/11/2022 10:03 PM, Mike Terry wrote:
> On 12/05/2022 01:05, olcott wrote:
>> On 5/11/2022 6:01 PM, Mike Terry wrote:
>>> On 11/05/2022 22:30, Malcolm McLean wrote:
>>>> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote:
>>>>> On 11/05/2022 10:19, Malcolm McLean wrote:
>>>>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>>>>>
>>>>>>> But what you suggest is quite workable...
>>>>>>>
>>>>>>> I think if I were interested in ultimate efficiency, I might go 
>>>>>>> with Jeff's "chained blocks" with a
>>>>>>> comfortably large chosen page size. (But efficiency really isn't 
>>>>>>> an issue for this task!)
>>>>>>>
>>>>>> The tape is unbounded. And even some very simple machines will 
>>>>>> fill it up to infinity.
>>>>>> If you stop the machine when the process runs out of memory, which 
>>>>>> is a reasonable
>>>>>> strategy, you don't want O(N) tape write operations.
>>>>>>
>>>>>> Chained blocks are probably the best model. They don't scale up, 
>>>>>> so a machine that was written
>>>>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern 
>>>>>> desktop. If you know
>>>>>> the approximate szie of your tape, however, then blocks are a good 
>>>>>> solution.
>>>>>>
>>>>> I don't get why you say a chained block approach doesn't scale up. 
>>>>> Such a design works well until
>>>>> the logical (user) address space is filled, which is absolutely 
>>>>> huge on a modern 64-bit machine with
>>>>> page files etc.. When the tape gets very large, only a small 
>>>>> portion of it needs to be in the
>>>>> working set for the process to avoid paging.
>>>>>
>>>>> The only design I can think of that might scale up better would be 
>>>>> one using an output device larger
>>>>> than the logical address space limit. Maybe you were just saying 
>>>>> that a hard-coded small block size
>>>>> (for a ZX81?) is not as efficient as big blocks if you've got lots 
>>>>> of memory? I don't see that you
>>>>> would use a chained block approach on such a tiny machine! Perhaps 
>>>>> you meant to say the design
>>>>> doesn't scale /down/ rather than up? (And the size of chained 
>>>>> blocks can be dynamically decided at
>>>>> run time if we like.)
>>>>>
>>>>> Other designs, e.g. using vector or strings will involve copying 
>>>>> ever larger blocks of memory around
>>>>> when the vector/string is extended, so perhaps you meant to say 
>>>>> that /those/ designs don't scale up,
>>>>> but the chained blocks scale up?
>>>>>
>>>> I was thinking that the chained block degenerates into effectively a 
>>>> linked list when block size becomes
>>>> small in relation to tape length. However that isn't really a 
>>>> problem - it still works more effectively
>>>> than a contiguous model.
>>>
>>> Yes, for a fixed block length it will be like a tape element linked 
>>> list, but only some small fraction of the allocation overhead.  
>>> Bigger blocks resulting in a smaller fraction.  Or we could have some 
>>> kind of exponential block size growth, so we start with, say, 1 
>>> allocation cost for the first 50000 tape elements, then getting 
>>> smaller as blocks get bigger - but 1 allocation per 50000 tape 
>>> elements is already a pretty small overhead for most purposes.  E.g. 
>>> writing/testing PO's Even TM, we could make do with one single fixed 
>>> block of just 20 tape elements!!! I'd think the key thing for PO 
>>> should be to get on with the exercise, rather than playing with TM 
>>> emulator efficiency.
>>>
>>> Mike.
>>
>> It is more cost-effective to make it right the first time rather than 
>> have to go back and fix it.
>>
>> My adaptation of David's approach to the TM tape also seems to be an 
>> objectively better way to implement std::deque.
>>
>> I can't possibly do the exercise until I see 100% exactly how the 
>> transition function works. Although it is exactly the same idea as a 
>> DFA state transition, its seems to not be working that way.
> 
> Yes the idea is the same but slightly more complicated.  What seems not 
> to be working that way?
> 
> You could think of a TM as a DFA that's been functionally enhanced to 
> allow at each computation step
> i)  left/right (single) stepping of its input tape head
> ii) rewriting of the symbol under the tape head
> whereas a DFA is restricted to work with strictly right stepping of its 
> "input tape head" so it only sees each character once (and so no concept 
> of rewriting anything because it couldn't be reread anyway).
> 
> So compared to a DFA transition rule, a TM rule still takes the same 
> input as a DFA (current state, input character), but has to specify two 
> additional data items:
> i)  the direction to move the tape head.
> ii) the character to write back to the tape and
> 
> For completeness, if you're familiar with DFAs but TMs not so much, I'll 
> add:
> 
> A) The DFA/TM termination conditions are a bit different.  A DFA halts 
> naturally at the end of the input string, so it's fine (and typical) to 
> have accept/reject states that are entered multiple times during a 
> computation, i.e. those states aren't "final" states in the TM sense.  A 
> TM clearly needs some other way to explicitly indicate it's finished.  
> Typically (e.g. Linz) some TM states are designated "final" states that 
> halt the TM - if it has accept/reject states those are final, so can 
> only be entered once.  (If we converted a DFA to a TM, we would need 
> some obvious fiddling when we get to the DFA accept/reject states - 
> simply designating them as TM final states wouldn't work...)
> 
> B) The TM input tape is /potentially infinite/ in extent so there needs 
> to be the rule for what's on the tape outside of its designated "input 
> string" at the beginning of a computation.  That's what the TM BLANK 
> symbol is for.  (DFA's by design can't get "beyond their input string", 
> so no concept of a special BLANK symbol arises.)
> 
> 
> Mike.

I think that I already knew all that stuff. I have two patents on DFA's 
so I know them well. They match screen pixels to recognized characters.
The second patent is a patentable memory optimization of the first.

I only got an very detailed looks at TM's in the last few days on the 
basis of this system: http://www.lns.mit.edu/~dsw/turing/turing.html
I am rewriting it so that it has a three minute learning curve.

-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer