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

Groups > comp.theory > #22913

Re: Mapping "C" to a Turing equivalent abstract model of computation

Cross-posted to 2 groups.

Show all headers | View raw

olcott <NoOne@NoWhere.com> writes:
> On 9/5/2020 1:01 PM, Keith Thompson wrote:
>> [Dropping crossposts to comp.lang.c and comp.lang.c++
>> olcott <NoOne@NoWhere.com> writes:
>>> There is no possible way for any concrete implementation of "C" to be
>>> made equivalent to a Turing machine. If we used every atom in the
>>> whole universe to each store a single binary digit we would still be
>>> woefully short of unlimited memory.
>>>
>>> We can override and supersede the standard "C" and map its syntax and
>>> semantics to an abstract model of computation that is Turing
>>> equivalent. The RASP model of computation is a model that "C" can be
>>> mapped to.
>>> https://en.wikipedia.org/wiki/Random-access_stored-program_machine
>>>
>>> A variation of the RASP model is shown below that the x86/x64 language
>>> maps to. Since it is already known that "C" maps to the x86/x64
>>> concrete models of computation we know that "C" maps to the following
>>> abstract model:
>>>
>>> Instruction
>>>       : INTEGER ":" OPCODE                     // Address:Opcode
>>>       | INTEGER ":" OPCODE INTEGER             // Address:Opcode Operand
>>>       | INTEGER ":" OPCODE INTEGER "," INTEGER // Address:Opcode Operand, Operand
>>> HEXDIGIT [a-fA-F0-9]
>>> INTEGER  {HEXDIGIT}+
>>> OPCODE   HEXDIGIT{4}
>>>
>>> The above abstract machine maps the x86 language to machines with a
>>> fixed pointer size of the largest unlimited integer address that is
>>> actually needed by the computation. This provides the basis for
>>> recognizing the set of Turing equivalent x86/x64/C computations.
>>
>> That is not an "abstract machine",  It's a simple grammar.
>> It specifies no semantics, no behavior, no meaning.  I guess your
>> vague handwaving reference to x86 machine language is supposed to
>> do that.
>>
>> To be an abstract machine, it would have to include the semantics
>> of the OPCODEs.
>
> I assume some prerquisite knowledge. Anyone knowing the x86 language
> knows the semantics of its opcodes. Anyone knowing the RASP model of
> computation would know that this syntactical variation of this model
> could implement the semantics of the opcodes.

And anyone knowing what an abstract machine is knows that the simple
grammar you've presented simply is not an abstract machine.  If you're
trying to connect it to x86 opcodes, you have to do so explicitly if you
want to be taken seriously.

>> If your intent is to define a representation of x86 machine code --
>> well, x86 machine code is already a representation of x86 machine
>> code, so I don't see the point.  Your grammar doesn't restrict the
>> size of an integer, but you've said nothing about what that means.
>>
>>      1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF:BEEF 42,42
>>
>> The above line satisfies your grammar.  So what?  How is anyone
>> supposed to know what it means?
>>
>> And you probably haven't noticed yet that your grammar specifies
>> the syntax of a single "Instruction", but not for a sequence of
>> "Instructions"s.

And you just ignored this.  You have a grammar that specifies a single
"Instruction", and your only response is to criticize your critics for
not understanding the Deeper Meaning that you haven't bothered to state.

>>> Turing equivalent computations derive equivalent output or fail to
>>> halt on equivalent input between the concrete machine and its Turing
>>> machine equivalent.
>>>
>>> Some machines that (for example) count to infinity and store the
>>> counter at each increment do not map to any finite computation.
>
> The idea of this post is to elaborate the distinction between the
> (brand new?) concept of Turing equivalent computations from the
> existing concept of Turing equivalent machines and show that x86/x64/C
> programs define a set of Turing equivalent computations.

And it doesn't do so at all.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

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

Thread

Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 11:38 -0500
  Mapping x86/x64/C to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 11:41 -0500
    Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-05 21:11 +0100
      Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 15:40 -0500
        Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-06 00:27 +0100
          Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 20:22 -0500
            Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation André G. Isaak <agisaak@gm.invalid> - 2020-09-06 09:41 -0600
              Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-06 13:07 -0500
  Re: Mapping "C" to a Turing equivalent abstract model of computation Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-05 11:01 -0700
    Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 13:26 -0500
      Re: Mapping "C" to a Turing equivalent abstract model of computation Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-05 11:43 -0700
        Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 14:33 -0500
          Re: Mapping "C" to a Turing equivalent abstract model of computation Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-05 12:53 -0700
            Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 15:26 -0500
  Re: Mapping "C" to a Turing equivalent abstract model of computation Jeff Barnett <jbb@notatt.com> - 2020-09-08 11:18 -0600
    Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-08 12:30 -0500
      Re: Mapping "C" to a Turing equivalent abstract model of computation Jeff Barnett <jbb@notatt.com> - 2020-09-08 14:48 -0600
        Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-08 16:34 -0500

csiph-web