1. Forum
  2. Usenet
  3. COMP.AI.NAT-LANG

  • =?UTF-8?Q?Simply_defining_G=c3=b6del_Incompleteness_and_Tarski_Unde?= =

    From olcott@21:1/5 to All on Fri Aug 14 12:35:35 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    An abstract machine that has a tape head that can be advanced in 0 to 0xffffffff increments an unlimited number of times does specify a model
    of computation that has access to unlimited memory. The technical name
    for memory addressing based on the displacement from the current memory
    address is relative addressing.

    32-bit x86 function calls already use signed 32-bit relative addressing.

    void Bar(int N)
    {
    Foo(5);
    }


    void Foo(int N)
    {
    Bar(6);
    }

    101: 55 push ebp
    102: 8BEC mov ebp, esp
    104: 6A05 push 0x5
    106: E823000000 call 0x12e ; +23h bytes little endian
    10b: 83C404 add esp, 0x4 ; of 00000023h
    10e: 5D pop ebp
    10f: C3 ret

    12e: 55 push ebp
    12f: 8BEC mov ebp, esp
    131: 6A06 push 0x6
    133: E8C9FFFFFF call 0x101 ; -37h bytes little endian
    138: 83C404 add esp, 0x4 ; of FFFFFFC9h
    13b: 5D pop ebp
    13c: C3 ret


    The x86 architecture already specifies a Turing complete model of
    computation for its control flow operations:

    Signed 32-bit relative addressing for function calls. (shown above).
    Signed 32-bit relative addressing for unconditional branches.
    Signed relative addressing for all conditional branches.

    It can also be understood (although more difficult) that the above
    Turing complete model of computation applied to the control flow of the
    x86 architecture can be leveraged to provide access to unlimited data.
    It can do this within the current x86 instruction set.

    I won't provide the details of this to avoid getting into endless debate
    with people that do not understand that they do not understand. Those
    capable of understanding can easily figure out for themselves how this
    would work, and those that cannot figure out for themselves how this
    would work may be incapable of understanding. I already provided the
    full basis in my discussion of control flow.

    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Fri Aug 14 13:36:50 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    An abstract machine that has a tape head that can be advanced in 0 to 0xffffffff increments an unlimited number of times does specify a model
    of computation that has access to unlimited memory. The technical name
    for memory addressing based on the displacement from the current memory
    address is relative addressing.

    32-bit x86 function calls already use signed 32-bit relative addressing.

    void Bar(int N)
    {
    Foo(5);
    }


    void Foo(int N)
    {
    Bar(6);
    }

    101: 55 push ebp
    102: 8BEC mov ebp, esp
    104: 6A05 push 0x5
    106: E823000000 call 0x12e ; +23h bytes little endian
    10b: 83C404 add esp, 0x4 ; of 00000023h
    10e: 5D pop ebp
    10f: C3 ret

    12e: 55 push ebp
    12f: 8BEC mov ebp, esp
    131: 6A06 push 0x6
    133: E8C9FFFFFF call 0x101 ; -37h bytes little endian
    138: 83C404 add esp, 0x4 ; of FFFFFFC9h
    13b: 5D pop ebp
    13c: C3 ret


    The x86 architecture already specifies a Turing complete model of
    computation for its control flow operations:

    Signed 32-bit relative addressing for function calls. (shown above).
    Signed 32-bit relative addressing for unconditional branches.
    Signed relative addressing for all conditional branches.

    It can also be understood (although more difficult) that the above
    Turing complete model of computation applied to the control flow of the
    x86 architecture can be leveraged to provide access to unlimited data.
    It can do this within the current x86 instruction set.

    Any software engineer of ordinary skill in the art of x86 programming
    would be able to leverage this Turing complete control flow to obtain
    Turing complete access to data.


    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Fri Aug 14 14:32:17 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    An abstract machine that has a tape head that can be advanced in 0 to 0xFFFFFFFF increments an unlimited number of times specifies a model of computation that has access to unlimited memory. The technical name for
    memory addressing based on the displacement from the current memory
    address is relative addressing.

    32-bit x86 function calls already use signed 32-bit relative addressing.

    void Bar(int N)
    {
    Foo(5);
    }


    void Foo(int N)
    {
    Bar(6);
    }

    101: 55 push ebp
    102: 8BEC mov ebp, esp
    104: 6A05 push 0x5
    106: E823000000 call 0x12e ; +23h bytes little endian
    10b: 83C404 add esp, 0x4 ; of 00000023h
    10e: 5D pop ebp
    10f: C3 ret

    12e: 55 push ebp
    12f: 8BEC mov ebp, esp
    131: 6A06 push 0x6
    133: E8C9FFFFFF call 0x101 ; -37h bytes little endian
    138: 83C404 add esp, 0x4 ; of FFFFFFC9h
    13b: 5D pop ebp
    13c: C3 ret


    The x86 architecture already specifies a Turing complete model of
    computation for its control flow operations:

    Signed 32-bit relative addressing for function calls. (shown above).
    Signed 32-bit relative addressing for unconditional branches.
    Signed relative addressing for all conditional branches.

    Data access is also based on relative addressing therefore: The x86
    language specifies an abstract model of computation that is Turing
    complete.


    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Mon Aug 17 19:20:54 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    The abstract model of computation specified by the x86 language already
    has access to unlimited memory when we assume the implementation detail
    that the underlying memory architecture of this abstract model is
    organized as an unlimited sequence of adjacent 4GB blocks.

    (1) signed 32-bit relative jumps
    // Jumps to the first address of the next 4GB block
    FFFFFFF0: E90B000000 ; signed 32-bit relative jumps

    (2) signed 32-bit relative offsets
    // Moves a 32-bit integer from the first address of the next 4GB block xxxxxxxx: BBFFFFFFFF mov ebx, 0xffffffff
    xxxxxxxx: 8B4301 mov eax, dword ptr [ebx+0x1]

    x86 Instruction Set Reference
    https://c9x.me/x86/



    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Tue Aug 18 15:43:31 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    The abstract model of computation specified by the x86 language already
    has access to unlimited memory when we assume the implementation detail
    that the underlying memory architecture of this abstract model is
    organized as an unlimited sequence of adjacent 4GB blocks.

    (1) signed 32-bit relative jumps
    // Jumps to the first address of the next 4GB block
    FFFFFFF0: E90B000000 ; signed 32-bit relative jumps

    (2) signed 32-bit relative offsets
    // Moves a 32-bit integer from the first address of the next 4GB block xxxxxxxx: BBFFFFFFFF mov ebx, 0xffffffff
    xxxxxxxx: 8B4301 mov eax, dword ptr [ebx+0x1]

    x86 Instruction Set Reference
    https://c9x.me/x86/

    The correctness of the above machine language instructions was verified
    with Intel XED.

    The X86 Encoder Decoder (XED), is a software library (and associated
    headers) for encoding and decoding X86 (IA32 and Intel64) instructions. https://intelxed.github.io/

    E9 cd JMP rel32
    Jump near, relative, displacement relative to next instruction.

    f0: E90B000000 jmp 0x100
    f5: 90 nop
    f6: 90 nop
    f7: 90 nop
    f8: 90 nop
    f9: 90 nop
    fa: 90 nop
    fb: 90 nop
    fc: 90 nop
    fd: 90 nop
    fe: 90 nop
    ff: 90 nop
    100: BBFFFFFFFF mov ebx, 0xffffffff
    105: 8B4301 mov eax, dword ptr [ebx+0x1]



    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Wed Aug 19 16:03:31 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    The abstract model of computation specified by the x86 language already
    has access to unlimited memory when we assume the implementation detail
    that the underlying memory architecture of this abstract model is
    organized as an unlimited sequence of adjacent 4GB blocks.

    E9 cd JMP rel32
    Jump near, relative, displacement relative to next instruction.

    A relative offset (rel8, rel16, or rel32) is generally specified as a
    label in assembly code, but at the machine code level, it is encoded as
    a signed 8-, 16-, or 32-bit immediate value. This value is added to the
    value in the EIP register.
    x86 Instruction Set Reference https://c9x.me/x86/

    (1) Signed 32-bit relative jumps
    // Jumps to the first address of the next 4GB block
    FFFFFFF0: E90B000000 ; signed 32-bit relative jump + 0x0B

    (2) Signed 32-bit relative offsets
    e4: BBFFFFFFFF mov ebx, 0xffffffff
    e9: 8B8300000080 mov eax, dword ptr [ebx-0x80000000]
    ef: 8B83FFFFFF7F mov eax, dword ptr [ebx+0x7fffffff]

    // Moves a 32-bit integer from the first address of the next 4GB block
    f5: 8B4301 mov eax, dword ptr [ebx+0x1]

    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Sun Aug 23 10:36:52 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    An abstract machine having a tape head that can be advanced in 0 to
    0x7FFFFFFF increments an unlimited number of times specifies a model of computation that has access to unlimited memory. The technical name for
    memory addressing based on displacement from the current memory address
    is relative addressing.

    The abstract model of computation defined by the x86 language already
    specifies access to unlimited memory. The implementation details of this abstract model are not directly an aspect of this model itself.

    If the implementation detail of the memory architecture of the x86
    language was an unlimited sequence of contiguous 4GB blocks and the
    absolute addressing modes of the 86 language only referred to addresses
    within the current 4GB block then it becomes rather obvious that the x86 language exactly as it currently exists specifies access to unlimited
    memory.

    It is the relative addressing of the x86 abstract model of computation
    defined by the x86 language that provides memory access and control flow
    access to an unlimited number of 4GB blocks of memory.

    It is only hardware implementations of this abstract model that place
    any limit on memory access. These hardware limits are implementation
    details that are not any aspect of the abstract model itself.

    The x86 language itself allows the instruction pointer and/or the data
    pointer to move forward in 1 to 0x7FFFFFFF increments an unlimited
    number of times from their current location, thus providing control flow
    and data access to unlimited memory.

    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Sun Aug 23 22:57:55 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    The abstract model of computation specified by the x86 language provides
    access to unlimited memory.

    The x86 language is defined by its instructions:
    (a) Exactly how each instruction is encoded as a sequence of bytes.
    (b) The primary change to the machine state caused by executing the instruction. (AKA the most basic semantics of the instruction).

    The syntax of this language specifies that relative jumps can be made to 0x7FFFFFFF bytes above the maximum value that the EIP register can hold.
    When this syntax is implemented having semantics that it specifies then:

    (a) Jumps could be made to memory location addresses that would not fit
    in the EIP register. This entails that the EIP register would have to
    roll over like an odometer.

    (b) This higher memory would have to exist.

    (c) This process could be repeated an unlimited number of times.


    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Tue Aug 25 11:54:52 2020
    XPost: comp.theory, comp.ai.philosophy, sci.lang.semantics

    "C" is not Turing Complete, but it could be: If we mapped the "C"
    programming language to the abstract model of computation of 32-bit
    signed RIP relative addressing that is implemented in the 64-bit machine architecture then "C" would have Turing Complete access to unlimited memory.

    To keep this abstraction pure the generated code would never directly
    refer to any machine address. This ensures that the actual generated
    code is always Turing Complete. Post processing could translate this
    generated code into specific hardware architectures.

    RIP relative addressing implemented in the 64-bit architecture is not
    directly tied to any fixed sized addressing. This same abstract model of computation could be implemented in an unlimited number of physical
    address sizes.

    By doing this theoretical computer science problems could be empirically validated using the much higher level abstraction of the "C" programming language. It is much easier to examine the overall structure of an
    algorithm using this much higher level of abstraction.


    --
    Copyright 2020 Pete Olcott

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)