What is the criteria for Turing equivalence of modern programming languages ?

[olcott]

--
Copyright 2022 Pete Olcott

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

[Richard Damon]

Note, Turing Equivalence is a property of COMPUTATION SYSTEMS not
individual machines.

Maybe you should see
https://en.wikipedia.org/wiki/Turing_completeness#Formal_definitions

The short answer from there is:

A related concept is that of Turing equivalence – two computers P and Q
are called equivalent if P can simulate Q and Q can simulate P. The
Church–Turing thesis conjectures that any function whose values can be
computed by an algorithm can be computed by a Turing machine, and
therefore that if any real-world computer can simulate a Turing machine,
it is Turing equivalent to a Turing machine. A universal Turing machine
can be used to simulate any Turing machine and by extension the
computational aspects of any possible real-world computer.

To show that something is Turing-complete, it is enough to show that it
can be used to simulate some Turing-complete system. No physical system
can have infinite memory, but if the limitation of finite memory is
ignored, most programming languages are otherwise Turing-complete.

[Andy Walker]

On 02/10/2022 04:42, olcott wrote:
>

If you have a language that has sufficiently magical powers to
defeat the Church-Turing thesis, then that language is not Turing
equivalent. AFAIK, no-one has a practical proposal to this end.
Going the other way, if your language can increment and decrement
two arbitrarily large integers, and can test integers against zero,
it can simulate an arbitrary TM. Note that this may involve the
use of external storage in the event that programs exceed the disc
storage of your computer. If you have a language in mind that does
not have this capability, then it is not going to be very useful
except perhaps for very highly specialised use. For further info,
see, for example

http://www.cuboid.me.uk/anw/G12FCO/lect20.html

[but there are many other web pages with similar material].

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Favarger

[olcott]

I think that is a correct answer.

In my answer in another forum I mapped the x86 language to a RASP
machine showing that because C maps to the x86 machine now C maps to a
RASP machine. I was able to give C unlimited memory when it is mapped to
x64 RIP relative addressing through unlimited length linked lists.

In this case the hardware does not a fixed limit, yet the model of
computation does not.

[Richard Damon]

Yes, x86 assembly and RASP are both Turing Complete systems (the x86
needs the proviso of memory capacity).

Your idea ox x64 RIP doesn't fix the issue, this has been explained, but
was apparently over your head.

[olcott]

The abstract model of computation that x64 RIP relative addressing
defines specifies linked lists of unbounded length. It can always
reference a fixed offset from the current address an unlimited number of
times. Only physical hardware limitations reduce this.

https://eli.thegreenplace.net/2012/01/03/understanding-the-x64-code-models

[Richard Damon]

Right, but each linked list uses up space on every page between the
requesting page and the page with the data.

This allows you to EXTEND the space somewhat (especially if you use up a
register for offsets) but doesn't make it unlimited.

Try to sketch out how to access 2**128 different memory locations with
this system.

Then look what you did and see if it would have problems extending to
2**256 locations.

[olcott]

I am referring to a single linked list where each element is 4GB in
size. All addressing is relative to the 64-bit instruction pointer and
point to an address in the current block, prior block or next block. To
get to subsequent blocks the machine must make a relative jump into the
next block an unlimited number of times.

https://www.felixcloutier.com/x86/jmp

> This allows you to EXTEND the space somewhat (especially if you use up a
> register for offsets) but doesn't make it unlimited.
>
> Try to sketch out how to access 2**128 different memory locations with
> this system.
>
> Then look what you did and see if it would have problems extending to
> 2**256 locations.

[Richard Damon]

And how do you get to the block exactly 2**70 blocks later?

You just aren't thinking through the problem far enough.

This is you common problem, you just ignore the problems and assume they
don't exist, and then just claim you can do what can't be done.

YOU FAIL.

[olcott]

RIP relative addressing is the exact same idea as TM tape head movement
except that it can move its tape head in much larger increments.

[Richard Damon]

Nope, just shows you don't understand what you are talking about.

TM tape head movement gets to unbounded memory access even with a finite
amount of code.

Your RIP addrssing requires getting to different parts of the program to
access different parts of the data. A given instruction can only access
a finite amount of data, and you need to replicate your code to access
more memory, but this replicated code needs overhead in the finite space
that a given instruction can access, so you can only replicate the code
a finite number of times.

[olcott]

I don't care enough about this to continue. For my purposes every C
program that has enough memory to complete its computation is equivalent
to a TM performing the equivalent computation.

[Richard Damon]

Yes, and because all computations that return a result only need finite
memory, and things like the x86 architecture can be expanded to any
desired FINITE memory size (one way by just increasing the address size
of the memory, maybe adding oversized registers for indexing) you can
build the equivalent.

You just can't claim to make a given architecture unbounded.

Your thinking you can just shows you don't understand the basics of the
Theory.