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

Groups > comp.theory > #22835 > unrolled thread

Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations]

Back to article view | Back to comp.theory

Contents

  Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] olcott <NoOne@NoWhere.com> - 2020-09-02 23:00 -0500
    Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-02 23:22 -0700
      Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] olcott <NoOne@NoWhere.com> - 2020-09-03 09:49 -0500
        Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-03 10:49 -0700
          Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] olcott <NoOne@NoWhere.com> - 2020-09-03 12:52 -0500
      Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] olcott <NoOne@NoWhere.com> - 2020-09-03 09:51 -0500

#22835 — Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations]

When we map "C" to a Turing equivalent abstract model of compuation "C" 
becomes Turing equivalent.

Mapping x86 programs to a Turing equivalent abstract model
The following 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.

Instruction
      : INTEGER ":" OpCode
      | INTEGER ":" OpCode Integer
      | INTEGER ":" OpCode Integer "," Integer

HEXDIGIT [a-fA-F-0-9]
INTEGER  {HEXDIGIT}+
OPCODE   HEXDIGIT{4}

Address:OpCode
Address:OpCode Param
Address:OpCode Param, Param

All Intel x86/x64 programs that map to the above abstract model of 
computation would be provably Turing equivalent computations. This means 
that they would always produce equivalent output for equivalent input 
and have the same halting behavior.


-- 
Copyright 2020 Pete Olcott

[toc] | [next] | [standalone]

#22836

olcott <NoOne@NoWhere.com> writes:
> When we map "C" to a Turing equivalent abstract model of compuation
> "C" becomes Turing equivalent.
>
> Mapping x86 programs to a Turing equivalent abstract model
> The following 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.
>
> Instruction
>      : INTEGER ":" OpCode
>      | INTEGER ":" OpCode Integer
>      | INTEGER ":" OpCode Integer "," Integer
>
> HEXDIGIT [a-fA-F-0-9]
> INTEGER  {HEXDIGIT}+
> OPCODE   HEXDIGIT{4}
>
> Address:OpCode
> Address:OpCode Param
> Address:OpCode Param, Param
>
> All Intel x86/x64 programs that map to the above abstract model of
> computation would be provably Turing equivalent computations. This
> means that they would always produce equivalent output for equivalent
> input and have the same halting behavior.

Since you don't even mention C++, please don't cross-post this to
comp.lang.c++.

This:
    HEXDIGIT [a-fA-F-0-9]
should be:
    HEXDIGIT [a-fA-F0-9]

-- 
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 */

[toc] | [prev] | [next] | [standalone]

#22841

On 9/3/2020 1:22 AM, Keith Thompson wrote:
> olcott <NoOne@NoWhere.com> writes:
>> When we map "C" to a Turing equivalent abstract model of compuation
>> "C" becomes Turing equivalent.
>>
>> Mapping x86 programs to a Turing equivalent abstract model
>> The following 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.
>>
>> Instruction
>>       : INTEGER ":" OpCode
>>       | INTEGER ":" OpCode Integer
>>       | INTEGER ":" OpCode Integer "," Integer
>>
>> HEXDIGIT [a-fA-F-0-9]
>> INTEGER  {HEXDIGIT}+
>> OPCODE   HEXDIGIT{4}
>>
>> Address:OpCode
>> Address:OpCode Param
>> Address:OpCode Param, Param
>>
>> All Intel x86/x64 programs that map to the above abstract model of
>> computation would be provably Turing equivalent computations. This
>> means that they would always produce equivalent output for equivalent
>> input and have the same halting behavior.
> 
> Since you don't even mention C++, please don't cross-post this to
> comp.lang.c++.
> 
> This:
>      HEXDIGIT [a-fA-F-0-9]
> should be:
>      HEXDIGIT [a-fA-F0-9]
> 

Since "C" is the basis for "C++" my work applies to "C++".
Since some people on the C++ forum are responding that indicates 
interest. Because there is very little interest I only post my brand new 
material to C++ and not its corresponding dialogue.

-- 
Copyright 2020 Pete Olcott

[toc] | [prev] | [next] | [standalone]

#22845

olcott <NoOne@NoWhere.com> writes:
> On 9/3/2020 1:22 AM, Keith Thompson wrote:
[...]
>> Since you don't even mention C++, please don't cross-post this to
>> comp.lang.c++.
[...]
> Since "C" is the basis for "C++" my work applies to "C++".
> Since some people on the C++ forum are responding that indicates
> interest. Because there is very little interest I only post my brand
> new material to C++ and not its corresponding dialogue.

C and C++ are two different languages (yes, I know they're related),
and they have two different newsgroups for very good reasons.

When someone posts a followup to a cross-posted article, I'm not
sure you can tell where they responded from.  If you cross-post to
comp.theory and comp.lang.c++ and someone posts a followup while
reading comp.theory, the followup will show up in both with the
same headers.

If you're not talking about C++, please don't post to comp.lang.c++.

(I don't expect you to listen to reason.  If I don't respond further,
don't assume I agree with you.)

-- 
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 */

[toc] | [prev] | [next] | [standalone]

#22846

On 9/3/2020 12:49 PM, Keith Thompson wrote:
> olcott <NoOne@NoWhere.com> writes:
>> On 9/3/2020 1:22 AM, Keith Thompson wrote:
> [...]
>>> Since you don't even mention C++, please don't cross-post this to
>>> comp.lang.c++.
> [...]
>> Since "C" is the basis for "C++" my work applies to "C++".
>> Since some people on the C++ forum are responding that indicates
>> interest. Because there is very little interest I only post my brand
>> new material to C++ and not its corresponding dialogue.
> 
> C and C++ are two different languages (yes, I know they're related),
> and they have two different newsgroups for very good reasons.
> 
> When someone posts a followup to a cross-posted article, I'm not
> sure you can tell where they responded from.  

Unless the followup is only posted to comp.lang.c++

> If you cross-post to
> comp.theory and comp.lang.c++ and someone posts a followup while
> reading comp.theory, the followup will show up in both with the
> same headers.
> 
> If you're not talking about C++, please don't post to comp.lang.c++.
> 
> (I don't expect you to listen to reason.  If I don't respond further,
> don't assume I agree with you.)
> 


-- 
Copyright 2020 Pete Olcott

[toc] | [prev] | [next] | [standalone]

#22842

On 9/3/2020 1:22 AM, Keith Thompson wrote:
> olcott <NoOne@NoWhere.com> writes:
>> When we map "C" to a Turing equivalent abstract model of compuation
>> "C" becomes Turing equivalent.
>>
>> Mapping x86 programs to a Turing equivalent abstract model
>> The following 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.
>>
>> Instruction
>>       : INTEGER ":" OpCode
>>       | INTEGER ":" OpCode Integer
>>       | INTEGER ":" OpCode Integer "," Integer
>>
>> HEXDIGIT [a-fA-F-0-9]
>> INTEGER  {HEXDIGIT}+
>> OPCODE   HEXDIGIT{4}
>>
>> Address:OpCode
>> Address:OpCode Param
>> Address:OpCode Param, Param
>>
>> All Intel x86/x64 programs that map to the above abstract model of
>> computation would be provably Turing equivalent computations. This
>> means that they would always produce equivalent output for equivalent
>> input and have the same halting behavior.
> 
> Since you don't even mention C++, please don't cross-post this to
> comp.lang.c++.
> 
> This:
>      HEXDIGIT [a-fA-F-0-9]
> should be:
>      HEXDIGIT [a-fA-F0-9]
> 

Thanks for catching the typo.

-- 
Copyright 2020 Pete Olcott

[toc] | [prev] | [standalone]

Back to top | Article view | comp.theory

csiph-web