HP-15C Turing Complete?



#26

Searching around the web, you can find many sites that repeat the identical quote that the 15C's "programming model is not turing complete."

However, I have not been able to find any information to back up that assertion, and I can't see why the 15C would not be considered turing complete.

Does anyone have more information?


#27

This is a typical case of someone adding incorrect information to Wikipedia, which then gets copied to a zillion other web sites. Even if the Wikipedia article gets fixed (which it hasn't), it's just about impossible to get any of the copies fixed.

The worst part is that once misinformation in a Wikipedia article is corrected, people "correct" it back, citing the other web pages that were copied from Wikipedia as references.

I've been through this several times, for instance, fixing the articles on the Viking and Voyager space missions, which incorrectly claimed that those spacecraft used the RCA CDP1802 "COSMAC" microprocessor.


#28

Quote:
The worst part is that once misinformation in a Wikipedia article is corrected, people "correct" it back, citing the other web pages that were copied from Wikipedia as references.

I've been through this several times, for instance, fixing the articles on the Viking and Voyager space missions, which incorrectly claimed that those spacecraft used the RCA CDP1802 "COSMAC" microprocessor.


It sounds like the process described here in xkcd.

#29

Like I've said before:

$#$@#$ wikipedia


#30

I think Wikipedia is a great, but it is not an authoritative source, and neither are web sites that just host outdated copies of it. Wikipedia is sometimes good for finding authoritative sources, though, as many articles do contain good references.

#31

It appears that the Wikipedia article (as of this writing) is only claiming that the HP-10C and HP-12C are not Turing Complete, as they lack any form of indirect addressing. That does not extend to the HP-11C, 15C, and 16C, though I wouldn't be surprised if other web sites misinterpret it.


#32

HP-10C supports conditional branching which can be used to emulate indirect addressing as far as I know.

Can someone explain why an HP-10C (<with more memory preferably) would not be able to run the same programs as an HP-11C?


#33

Can you give an example of how the HP-10C can emulate indirect addressing?

To answer your question, the HP-10C lacks subroutines, labels, and flags, to name a few features.

Namir


#34

Everywhere you want to do an indirect RCL, you would have to have a chain of comparisons, GTOs, and direct RCLs, to get the equivalent effect (from a limited number of possible data registers). Similarly for STO. It's obviously not going to work for any real problem-solving, due to the very limited amount of program memory available. It's only a theoretical argument for Turing Completeness, and not about any practical capability.

#35

Although "Turing Complete" generally disregards the amount of memory available, by the time you use conditional branching in a program to emulate even just a few registers of indirect addressing, you're out of memory. But I guess technically it probably does qualify as being Turing Complete.


#36

I'm confused. If the ability to address over 20 registers is the problem, then my Mac is Turing incomplete too. Turing machines need infinite memory. All real machines have architectural limits on the amount of addressable memory. For the 10C, it's 20 locations. For my Mac it's 264 locations. Am I missing something?


#37

This is not the problem. No real machine has indeed infinite memory but they (or any language) are considered Turing complete if they had so.

Another way is to look at the question is this: let's consider a problem which can be implemented by a Turing machine using N "memories" (or tape spaces). Can a give machine, given sufficient memory solves this problem for any value of N?
If so, it is equivalent to a Turing machine.

Now, let's suppose an HP10C with more memory and more registers and let's check if we can implement an NxN Game Of Life.

We store the status of Cell x/y in register x*N+y obviously and then for each cell, we write the code which computes its next state (and stores it in register N*N+x*N+y).
Basically, we write N*N times the same code adressing different registers.

Then we write the code to copy the new state over the old one. Once again, N*N instructions but nothing complicated.

Basically, we unroll the loops we would have written if we had indirect register adressing.

Finally, we test for a counter or a condition and we exit or go back to instruction 0.

This implements the Game of Life on a HP-10C with a lot of memory.

As the Game of Life is proved to be a Turing machine, the HP-10C is too...

Unless I'm wrong of course.

#38

It's absolutely Turing Complete. Have you ever wrote programs for a hypothetical machine as described by Turing himself? There's no indirect addressing, subroutines, mathematical operations, or anything else. The only thing that there is is conditional branching --- with unlimited memory, of course!


#39

Of course a Turing Machine has indirect addressing. That's the ONLY form of addressing it has for the data memory (tape); there is no "direct" addressing. The tape location pointed to by the head (which is equivalent to the indirect register) is the only accessible location. The only changes that can be made to that "indirect register" are to increment or decrement it.

Edited: 30 Nov 2011, 2:11 a.m.


#40

I was thinking of more conventional indirect addressing. Calling a Turing machine's addressing "relative" would be a better term, however.

Going back to the 12C, it has both relative addressing (via STO/RCL CFj) and conventional indirect addressing (via STO N followed by STO/RCL CFj).

Edited: 30 Nov 2011, 2:55 a.m.

#41

Quote:
Of course a Turing Machine has indirect addressing. That's the ONLY form of addressing it has for the data memory (tape); there is no "direct" addressing. The tape location pointed to by the head (which is equivalent to the indirect register) is the only accessible location. The only changes that can be made to that "indirect register" are to increment or decrement it.

What is the point? We are not talking about the Turing machine itself but about being "Turing complete", i.e. being able to compute the same set of functions as a Turing machine.
And it can be done without "indirect adressing", i.e. RCL i/STO i for instance.

In fact, it can be done in many ways (see above about the Game of Life).


#42

Quote:
What is the point?

The point of describing characteristics of the Turing Machine is that it defines Turing Completeness.

#43

Quote:

The point of describing characteristics of the Turing Machine is that it defines Turing Completeness.


No. You repeat the same thing but you are making a confusion between the construction of the Turing machine and the set of functions it can compute.

The 2nd is a consequence of the first but the inverse is not true. Fortunately.

So indirect addressing is not necessary to be Turing complete.


#44

According to Wikipedia:

Quote:
In computability theory, a system of data-manipulation rules (such as an instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer.

It is thus relevant to discuss the characteristics of a Turing Machine. There are other Turing Complete machines that have the same computational ability as a Turing Machine, and thus these machines can, like a Turing Machine compute all partial recursive functions. If the Church-Turing Thesis holds, this is the set of all computable functions.

One way to show that a machine is Turing Complete is to show that the set of functions it can compute is identical to the set of partial recursive functions. For example, a Post tag machine with at least two tags is Turing Complete. It is in some cases easier to show that a machine can both simulate and be simulated by a Turing machine than to directly show that it can compute exactly the set of partial recursive functions.

Certainly there are machines that can be shown to be Turing Complete yet lack a direct equivalent to the type of indirect addressing found in some HP RPN calculators.

Showing that an HP-10C is Turing Complete by the method you suggest seems to have some difficulties. There is some lower bound to the universe size required for Conway's Life cellular automata to be universal, and the HP-10C is not likely to be capable of simulating that. A more promising approach would be to show that it can simulate Wolfram's Rule 110, which is the simplest known universal CA.


#45

The subject is not the space required to simulate a Turing machine using a Life Game.
Because if we go this way, no computer and of course no HP calculator is even close of doing so.

The point was that indirect addressing is not necessary to be Turing Complete and if your only objection to my demonstration is the memory size, then thanks for your validation.


#46

While memory size is not normally considered for Turing Equivalence, since no real computer has an infinite tape, it is required for Turing Equivalence that the candidate computer has to be able to simulate at least one single-tape Turing machine that uses only a finite amount of tape storage.

If I built a piece of hardware that could perform the Life CA with a 3x3 universe, no one would consider it Turing Complete, even though the Life CA is universal, because that size universe doesn't make it capable of simulating a Turing machine with even a two state program that uses only two tape locations, the smallest possible non-trivial Turing machine program.

#47

For another example, Wolfram's Rule 110 CA is proven to be universal. I can implement one cell of Rule 110 with seven NAND gates and one flip-flop. However, no one would claim that the circuit with seven NAND gates and one flip-flop is Turing Complete. Some larger collection of such circuits would be.

It's a matter of a lower bound. Turing Complete systems are not required to match the upper bound of what a Turing Machine can do, because that's obviously impossible, but they have to at least reach a lower bound of doing *something* non-trivial that a Turing machine can do.

If you don't have any lower bound, then you can say that *any* system is Turing Complete, because it can simulate a trivial Turing Machine, for instance, a Turing Machine that ignores its input, writes a single bit to the tape, and halts.


#48

Once again, you are changing the subject which was about indirect indexing, not the amount of memory needed...

Have fun by yourself, you probably think you can be right by talking about something else...


#49

I didn't say indexed addressing is necessary. However, if you don't have it, you'll have to use some other mechanism that provides the equivalent. On an HP calculator like the 10C, there is no indirect addressing, and doing the equivalent as a series of tests, branches, and RCL/STO uses up so much of the limited program memory that I don't think it is possible to make a credible claim that the 10C is Turing Complete.

For example, to have programmatic RCL access to just *three* selectable memory locations requires 14 program steps out of the 80 available. A programmatic STO access would also require 14 program steps. Since there are no subroutines, those RCL and STO sequences would need to occur multiple times.

#50

Quote:
...HP-12C are not Turing Complete, as they lack any form of indirect addressing

Could this behaviour of HP-12c be considered as Indirect addressing? Addressing an indirect register through n and Cfj. RCL(CFj) increases "n" value by one before calling the corresponding Register.

for an example

n=-1

RCL(CFj) returns R(0)

n=4

RCL(CFj) returns R(5)

n=1

CFj stores x value in R(2)

n=2

CFj stores x value in R(3)

and so on...

Also you can use additional 21 registers besides R(x)for values that are positive, integer and less than 100: n for location (0-20) "Nj" to store x, RCL(Nj) to recall that register in to x.

Regards, Kerem


Possibly Related Threads...
Thread Author Replies Views Last Post
  SandMatrix Released - The trilogy is complete. Ángel Martin 3 388 08-30-2013, 05:35 PM
Last Post: Marcel Samek
  The 'Complete' Collection Keith Midson 8 842 05-12-2013, 09:52 PM
Last Post: Namir
  My Mostek collection is complete Michael de Estrada 15 1,210 04-10-2013, 10:01 PM
Last Post: Michael de Estrada
  Complete list of PPC members Gonzalo Fernandez 0 175 01-04-2013, 03:01 PM
Last Post: Gonzalo Fernandez
  HP12C 'complete' collection Keith Midson 9 892 08-07-2012, 07:51 PM
Last Post: Keith Midson
  The Turing Machine Comes True Gilles Carpentier 1 191 06-26-2012, 09:26 AM
Last Post: Rory Molinari (USA)
  (OT) Lego Turing machine BruceH 9 470 06-22-2012, 08:14 AM
Last Post: Bill (Smithville, NJ)
  Nov-64: Complete Newbie Needs Help Les Wright 16 765 05-06-2012, 08:38 AM
Last Post: Luiz C. Vieira (Brazil)
  Complete 12C collection Keith Midson 3 200 02-22-2012, 11:31 PM
Last Post: Keith Midson
  Photo of my HP 15c | 15c LE DigiGal 2 285 10-12-2011, 12:34 PM
Last Post: DigiGal

Forum Jump: