Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #59163

Re: [No longer about] Olcott

Show all headers | View raw

Richard Damon <Richard@Damon-Family.org> writes:

> On 10/22/22 2:07 AM, wij wrote:
>> On Saturday, October 22, 2022 at 8:09:12 AM UTC+8, richar...@gmail.com wrote:
>>> On 10/21/22 6:32 PM, Andy Walker wrote:
>>>> On 21/10/2022 01:26, Richard Damon wrote:
>>>> [I wrote:]
>>>>>> [...] Your computer /is/ a TM, [...].
>>>>> But it becomse a Turing Machine with such a large number of states
>>>>> that you can't actually think about it.
>>>>
>>>>      It doesn't "become" one, it /is/ one.  Yes, it has a lot of states;
>>>> yet somehow we do manage to think about it, and even program it.  But we
>>>> mostly [for the past 60-odd years, anyway] do so in high-level languages.
>>>> Only a few of us even bother normally about the assembler produced when
>>>> such languages are compiled, and the actual bit patterns involved are even
>>>> less usually a consideration.
>>> Except we didn't program it AS a Turing Machine. To program it as a
>>> Turing Machine, we need to specify the large number of tuples that
>>> define the Turing Machine.
>>>
>>> Yes, we can ATTEMPT to look at it as a Turing Machine, at which point we
>>> will find it uninteligable.
>>>
>>> Just like you COULD think of this message as a long stream of 0s and 1s
>>> just strung together, but then to actually read it (unless you ARE a
>>> computer that reads binary) you would first convert it to the text
>>> representation that directly represents its meaning.
>>>
>>> And the Turing Model is worse, as looking at it as a Turing Machine is a
>>> lossy transformation, as the "value" of the states becomes irrelevent,
>>> and lost.
>>>
>>> Turing machines don't treat their states as a 'value' but as arbitrary
>>> lables, so we loss all the logical inter-relationships between the
>>> states. The fact that two states differ by only 1 bit change in this
>>> representation is a meaningless fact to the analysis of the Turing Machine.
>>>
>>> The bit pattern of the instructions may be mostly meaningless, but the
>>> pattern to the "numbers" used in the computation, especially for things
>>> like the Program Counter and index registers ARE quite important.
>>>>
>>>>>                        Even a computer with only 256
>>>>> bytes of memory (and no registers) becomes a FSM with 2**2048 states,
>>>>> which is roughly 10**600. Totally unmanagable.
>>>>
>>>>      Yet we manage such FSMs!  As you are about to point out, there is
>>>> a /lot/ of pattern.  So what that 256 bytes have 2^2048 states?  That's
>>>> just a mathematical fact, and it enables those 256 bytes of storage to
>>>> hold any [binary] pattern -- it would be a lot less manageable if only
>>>> some patterns were acceptable [apart, of course, from parity bits and
>>>> similar].
>>> Except that when we look at it as a Turing Machine, each state is an
>>> individual thing, treated seperately from every other state. The
>>> "patterns" of the program get lost (and vastly replicated by all the
>>> "state" that doesn't actually affect it).
>>>
>>> You end up with untold copies of the logic most repeated, but with
>>> untold variations on a vast number of different axis representing each
>>> thing that interacted with each other thing.
>>>>
>>>>> And thinking of it that way, makes it HARDER to analyize, as it
>>>>> overlook that there is a LOT of pattern in the Transistion table.
>>>>
>>>>      So don't think of it that way.  When was the last time you looked
>>>> at the detailed bit patterns of your entire computer and tried to work
>>>> out what the computer was doing?  Even when debugging a compiler problem,
>>>> usually only a few words need to be considered.
>>> I don't, but that is what you would need to do to analyise it as a
>>> Turing Machine.
>>>
>>> The fact that memory location 5 changed from 00000000 to 00000001 means
>>> the analysis of the loop while the Program counter cycles through a
>>> couple of bytes elsewhere in the code, needs to be redone, as we are now
>>> in a completely different set of states.
>>>
>>> This is the problem of treating a modern computer as a Turing Machine,
>>> the analysis just becomes "impossible".
>>>
>>> Note, even "a few words" if treated actually as a piece of a Turing
>>> Machine ends up with an enormous number of states.
>>>>
>>>>>> Yes, arbitrarily large but finite storage is simply internal state.
>>>>>> But that
>>>>>> is what your computer /is/!  Yes, it's difficult to describe all that
>>>>>> state
>>>>>> as TM quintuples, and it's more convenient instead to group parts of
>>>>>> that
>>>>>> state into terms of "instruction" and "registers", etc., as described
>>>>>> in the
>>>>>> processor manual.
>>>>> Which means that each version of a gien function with different state
>>>>> is a DIFFERENT Turing Machine.
>>>>
>>>>      ??? Your computer is /one/ FSM [or TM].  Loading a different program
>>>> corresponds to setting a different initial state, not to changing
>>>> transitions
>>>> [which are determined by the processor manual].  But again, that is what
>>>> your
>>>> computer /is/;  how you view or understand it is up to you.  Most people
>>>> will
>>>> understand that state better by thinking of some of its parts as
>>>> instructions
>>>> or registers or whatever than by thinking of the entire storage as one
>>>> binary
>>>> number with billions of digits;  but the two are logically equivalent.
>>> Yes, you CAN look at it as one giant FSM, but that hides much of the
>>> useful details. The NORMAL way to look at a computer is a smallish FSM
>>> for the control/sequencing logic, which is augmented with inputs from
>>> the data paths/ALU modules. This gives a much easier way to analyise the
>>> behavior, as the parts that work as "numbers" can be treated as numbers,
>>> and those parts that are more statelike can be treated as states.
>>>
>>> When you do that, you are NOT treating it as a Turing Machine.
>>>>
>>>>> If you save a bit of state inside a function, then that function
>>>>> becomes two different functions, with the state set the two ways, and
>>>>> everything that calls it gets duplicated, moving the "internal" state
>>>>> of the function into dividing the program into two vaiants with the
>>>>> differing state value.
>>>>
>>>>      ??? Saving state inside a function is a high-level activity, not
>>>> something directly present in either the binary of your program [inc the
>>>> data and disc storage], nor [for it is the same thing] in the state of
>>>> the equivalent FSM.
>>>>
>>> In a typical programmers model, the saving of state within the low level
>>> function is an implementation detail of that function, and not something
>>> seen at a higher level. This may (or might not) have impact on the
>>> "Pureness" of the fuction and things that call it (it might be a pure
>>> implementation detail to cache values to not require recomputation, so
>>> has no actual affect on its API).
>>>
>>> The Turing Like model make this a piece of the outermost logic.
>>>
>>> Remember, you said that the state of the FSM includes the ENTIRE
>>> contents of the memory (and registers) of the machine, and thus IS
>>> something directly present in this "Turing" model of the computer.
>> Computers always does TM-equivalent operations. No matter in what language you
>> think they are and programming.
>
> AS A TOTAL.

Which seems to be what's being talked about above.  (I've left it
un-edited because I'm not entirely sure what's relevant and what is not.

I wanted to make another point:

> You CAN write "snippets" that do not represent a TM-equivalent operation.
>
> For instance, you can not write a TM that is the equivalent of this function:
>
> int counter() {
>     static int count = 0;
>     return count++;
> }
>
> This is a function that returns an increasing value for each call
> within a bigger program.

And vice-versa: given part of a TM, you (usually) can't write C code
that is equivalent.  But then you can't write a TM that is equivalent to
this C function either

  int inc(inc x) { return x + 1; }

simply because it's a function and not a program.  You can't even write
a C /program/ that is equivalent to this C function!

I don't think asserting the non-equivalence of parts to wholes is going
to be very fruitful here.

Defining computational equivalence between wildly different models (like
C and TMs) is tricky to get right.  This is why the theory is usually
phrased in terms of decidable subsets of N rather than of a TM that
"does that same thing" as some C code.

A model based on some abstract version of C is equivalent to the TM
model when there are no subsets of N (suitably encoded) that are
decidable by one and not the other.  A TM decides by accepting or
rejecting based on the initial content of the tape, and a C program
decides when its main function returns 1 or 0 based on the content of
argv[1].

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Olcott lies Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-10-16 01:28 +0100
  Re: Olcott proves that he is correct olcott <polcott2@gmail.com> - 2022-10-15 20:37 -0500
  Re: Olcott lies Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-10-18 16:17 +0100
    Re: Olcott is proven to be correct to all those paying attention (hardly any) olcott <polcott2@gmail.com> - 2022-10-18 10:37 -0500
    Re: Olcott lies Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-10-20 02:44 +0100
      Re: Olcott is provably correct to anyone that pays attention olcott <none-ya@beez-waxes.com> - 2022-10-19 20:51 -0500
      Re: Olcott lies Richard Damon <Richard@Damon-Family.org> - 2022-10-19 22:00 -0400
        Re: Olcott is proven to be correct. olcott <polcott2@gmail.com> - 2022-10-19 22:58 -0500
        Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-20 10:08 +0100
          Re: [No longer about] Olcott Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-10-20 12:09 +0100
          Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-20 07:22 -0400
            Re: [No longer about] Olcott wij <wyniijj5@gmail.com> - 2022-10-20 06:08 -0700
            Re: Turing machines and practical computation Spiros Bousbouras <spibou@gmail.com> - 2022-10-20 14:11 +0000
              Re: Turing machines and practical computation Richard Damon <Richard@Damon-Family.org> - 2022-10-20 17:25 -0400
            Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-20 15:18 +0100
              Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-20 16:28 -0400
                Re: [No longer about] Olcott olcott <polcott2@gmail.com> - 2022-10-20 15:50 -0500
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-20 18:23 -0400
                Re: [still about] Olcott olcott <polcott2@gmail.com> - 2022-10-20 18:07 -0500
                Re: [still about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-20 20:16 -0400
                Re: [still about] Olcott olcott <polcott2@gmail.com> - 2022-10-20 19:45 -0500
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-21 00:40 +0100
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-20 20:26 -0400
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-21 23:32 +0100
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-21 20:09 -0400
                Re: [No longer about] Olcott wij <wyniijj5@gmail.com> - 2022-10-21 23:07 -0700
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-22 10:06 -0400
                Re: [No longer about] Olcott wij <wyniijj5@gmail.com> - 2022-10-22 08:45 -0700
                Re: [No longer about] Olcott Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-10-22 20:05 +0100
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-22 16:13 -0400
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-24 17:45 +0100
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-24 22:46 -0400
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-29 18:44 +0100
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-29 14:50 -0400
                Re: [No longer about] Olcott wij <wyniijj5@gmail.com> - 2022-10-30 05:19 -0700
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-11-02 20:28 +0000
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-11-02 18:15 -0400
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-11-07 20:54 +0000
                Re: [No longer about] Olcott olcott <polcott2@gmail.com> - 2022-11-07 15:04 -0600
                Re: [No longer about] Olcott Richard Damon <news.x.richarddamon@xoxy.net> - 2022-11-07 18:26 -0500
                Re: [No longer about] Olcott olcott <polcott2@gmail.com> - 2022-11-07 19:02 -0600
                Re: [No longer about] Olcott Jeff Barnett <jbb@notatt.com> - 2022-10-21 18:11 -0600
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-21 21:25 -0400
          Re: [No longer about] Olcott olcott <polcott2@gmail.com> - 2022-10-20 09:54 -0500
            Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-20 16:25 +0100
              Re: [No longer about] Olcott olcott <none-ya@beez-waxes.com> - 2022-10-20 11:05 -0500
                Re: [No longer about] Olcott olcott <polcott2@gmail.com> - 2022-10-20 11:09 -0500
                Re: [No longer about] Olcott Richard Damon <Richard@Damon-Family.org> - 2022-10-20 18:36 -0400
              Re: [No longer about] Olcott Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-10-20 20:18 +0100
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-21 00:52 +0100
                Re: [No longer about] Olcott Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-10-21 02:08 +0100
                Re: [No longer about] Olcott André G. Isaak <agisaak@gm.invalid> - 2022-10-20 19:58 -0600
                Re: [No longer about] Olcott olcott <polcott2@gmail.com> - 2022-10-20 21:08 -0500
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-22 01:00 +0100
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-22 00:32 +0100
                Re: [No longer about] Olcott Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-10-23 20:34 +0100
                Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-24 00:29 +0100
            Re: [No longer about] Olcott Wasell <wasell@example.com> - 2022-10-21 11:12 +0200
              Re: [No longer about] Olcott Andy Walker <anw@cuboid.co.uk> - 2022-10-21 13:04 +0100
              Re: [No longer about] Olcott [High level TM generators] olcott <polcott2@gmail.com> - 2022-10-25 09:29 -0500
                Re: [No longer about] Olcott [High level TM generators] Wasell <wasell@example.com> - 2022-10-26 06:06 +0200
                Re: [No longer about] Olcott [High level TM generators] olcott <polcott2@gmail.com> - 2022-10-26 10:32 -0500
                Re: [No longer about] Olcott [High level TM generators] Wasell <wasell@example.com> - 2022-10-27 08:20 +0200
                Re: [No longer about] Olcott [High level TM generators] olcott <polcott2@gmail.com> - 2022-10-27 11:16 -0500
                Re: [No longer about] Olcott [High level TM generators] Wasell <wasell@example.com> - 2022-10-27 18:46 +0200
                Re: [No longer about] Olcott [High level TM generators] olcott <polcott2@gmail.com> - 2022-10-27 12:06 -0500
                Re: [No longer about] Olcott [High level TM generators] Wasell <wasell@example.com> - 2022-10-27 20:45 +0200
                Re: [No longer about] Olcott [High level TM generators] olcott <polcott2@gmail.com> - 2022-10-27 13:56 -0500
                Re: [No longer about] Olcott [High level TM generators] Richard Damon <Richard@Damon-Family.org> - 2022-10-27 18:27 -0400
                Re: [No longer about] Olcott [High level TM generators] olcott <polcott2@gmail.com> - 2022-10-27 17:53 -0500
                Re: [No longer about] Olcott [High level TM generators] Richard Damon <news.x.richarddamon@xoxy.net> - 2022-10-27 19:27 -0400

csiph-web