HP15C Turing Complete?  Printable Version + HP Forums (https://archived.hpcalc.org/museumforum) + Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum1.html) + Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum2.html) + Thread: HP15C Turing Complete? (/thread205825.html) 
HP15C Turing Complete?  Marcel Samek  11292011 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?
Re: HP15C Turing Complete?  Eric Smith  11292011 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.
Re: HP15C Turing Complete?  Eric Smith  11292011 It appears that the Wikipedia article (as of this writing) is only claiming that the HP10C and HP12C are not Turing Complete, as they lack any form of indirect addressing. That does not extend to the HP11C, 15C, and 16C, though I wouldn't be surprised if other web sites misinterpret it.
Re: HP15C Turing Complete?  pascal_meheut  11292011 HP10C supports conditional branching which can be used to emulate indirect addressing as far as I know.
Can someone explain why an HP10C (<with more memory preferably) would not be able to run the same programs as an HP11C?
Re: HP15C Turing Complete?  SteveH  11292011 Quote:
It sounds like the process described here in xkcd.
Re: HP15C Turing Complete?  Namir  11292011 Can you give an example of how the HP10C can emulate indirect addressing? To answer your question, the HP10C lacks subroutines, labels, and flags, to name a few features.
Namir
Re: HP15C Turing Complete?  Eric Smith  11292011 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.
Re: HP15C Turing Complete?  Eric Smith  11292011 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 problemsolving, 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.
Re: HP15C Turing Complete?  Howard Owen  11292011 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 2^{64} locations. Am I missing something?
Re: HP15C Turing Complete?  pascal_meheut  11292011 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? 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). 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 HP10C with a lot of memory. As the Game of Life is proved to be a Turing machine, the HP10C is too...
Unless I'm wrong of course.
Re: HP15C Turing Complete?  Kerem Kapkin (Silicon Valley, CA)  11292011
Quote: Could this behaviour of HP12c 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 (020) "Nj" to store x, RCL(Nj) to recall that register in to x.
Regards, Kerem
Re: HP15C Turing Complete?  Katie Wasserman  11292011 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!
Re: HP15C Turing Complete?  Eric Smith  11302011 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.
Re: HP15C Turing Complete?  Katie Wasserman  11302011 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.
Re: HP15C Turing Complete?  pascal_meheut  11302011 Quote:
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.
In fact, it can be done in many ways (see above about the Game of Life).
Re: HP15C Turing Complete?  Eric Smith  11302011 Quote:The point of describing characteristics of the Turing Machine is that it defines Turing Completeness. Re: HP15C Turing Complete?  pascal_meheut  11302011 Quote: 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.
Re: HP15C Turing Complete?  bill platt  11302011 Like I've said before:
$#$@#$ wikipedia
Re: HP15C Turing Complete?  Eric Smith  11302011 According to Wikipedia: Quote: 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 ChurchTuring 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 HP10C 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 HP10C 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.
Re: HP15C Turing Complete?  pascal_meheut  12012011 The subject is not the space required to simulate a Turing machine using a Life Game. 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.
Re: HP15C Turing Complete?  Eric Smith  12012011 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 singletape 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 nontrivial Turing machine program.
Re: HP15C Turing Complete?  Eric Smith  12012011 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 flipflop. However, no one would claim that the circuit with seven NAND gates and one flipflop 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* nontrivial 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.
Re: HP15C Turing Complete?  pascal_meheut  12012011 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...
Re: HP15C Turing Complete?  Eric Smith  12012011 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.
Re: HP15C Turing Complete?  Eric Smith  12022011 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.
