▼
Posts: 735
Threads: 34
Joined: May 2007
We're not obliged to use a backtracking algorithm. We can use brute force and cycle through all the combinations. Let's assume we have variables a, b, c, d ... representing the position of the queens then the condition to come true would be something like:
a#b & a#c & a#d & ...
b#c & b#d & ...
c#d & ...
...
|a-b|#1 & |a-c|#2 & |a-d|#3 & ...
|b-c|#1 & |b-d|#2 & ...
|c-d|#1 & ...
...
There are several ways to cycle through all the possible positions. One would be to have a counter i from where the positions a, b, c, d ... can be calculated. This is basically representing the counter i in base N.
Given the limitation of ~2,400 cycles I'm afraid we can only solve N = 4 as 44 = 256 and 55 = 3,125. But maybe this idea can be improved.
I'm sure Katie had a reason to use INV(A) on both sides of the equation. My guess is it tricks the solver into solving the equation numerically. The disadvantage is that we need the same conditional on both sides. So finding another equation that can't be solved algebraically by the solver would refrain us from typing the same stuff twice.
Of course using an error condition to stop the program would be another solution.
Cheers
Thomas
Edited: 31 Jan 2011, 3:53 a.m.
▼
Posts: 858
Threads: 80
Joined: Feb 2009
Since few days I have an HP17B2+ (instead of an emulated HP-35S). Seems it will take me some more weekends to understand your N-queens problem - or solution. Where should I start?
Best.....Mike
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
Where should I start?
For the N-queens problem I'd recommend Google or Wikipedia. This is a quiet well known problem. For the solver see Don's message #38 below:
Quote:
This manual is on the museum DVD set (2719tech.pdf).
HTH
Thomas
Posts: 735
Threads: 34
Joined: May 2007
Here's the solution for the 4-queens problem:
QUEENS:
Z=P+Q+R+S+
\GS(A:1:4:1:
\GS(B:1:4:1:
IF(A<>B:
IF(SQ(A-B)<>1:
\GS(C:1:4:1:
IF(A<>C:
IF(SQ(A-C)<>4:
IF(B<>C:
IF(SQ(B-C)<>1:
\GS(D:1:4:1:
IF(A<>D:
IF(SQ(A-D)<>9:
IF(B<>D:
IF(SQ(B-D)<>4:
IF(C<>D:
IF(SQ(C-D)<>1:
L(P:A)xL(Q:B)xL(R:C)xL(S:D)/0
:0):0):0):0):0):0))
:0):0):0):0))
:0):0)))
After entering the equation which is quiet a pain you get the following menu:
[ Z ][ P ][ Q ][ R ][ S ]
Enter 0 to P, Q, R and S and solve for Z. After a while you get an error message:
SOLUTION NOT FOUND
Now you can recall the solution:
P = 2
Q = 4
R = 1
S = 3
This corresponds to the following configuration:
[ ][ ][ # ][ ]
[ # ][ ][ ][ ]
[ ][ ][ ][ # ]
[ ][ # ][ ][ ]
Please don't make me type this for the 8-queens problem. I had to type this on an iPhone.
Cheers
Thomas
Edited: 31 Jan 2011, 9:02 a.m.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Congratulations Thomas. There are more IF's and sigma's in there than you can shake a stick at!
I'm not familiar enough with this problem to know whether your work can be enhanced to do the 8-queens problem. Can it?
Don
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
I'm not familiar enough with this problem to know whether your work can be enhanced to do the 8-queens problem. Can it?
I assume so. Just counted the amount of characters and got something very close to 1,000. So the memory shouldn't be an issue. But who wants to enter all these? I've expanded the equation to solve the 5-queens problem and I got {1, 3, 5, 2, 4}.
The algorithm isn't very complicated. It's basically what you would do on a physical board: put the 1st queen at the first possible position, then the 2nd to the next possible position and so on. Whenever you can't proceed go one step backwards and try the next possible position. So we have 4 (or 8) nested for-loops but since some are enclosed within if-statements we don't really execute them all. I'd say it's pretty much the same algorithm as used in the other programs. When a legal position is reached the program stops due to an error condition (division by zero). It turned out to be much easier than using Katie's trick.
How do we you want to proceed? Any volunteers to enter that beast into a HP-17BII? I could provide the listing but not before the end of the week. But I think it should be possible to extrapolate the listing for the case of 8-queens.
As I'm not very familiar with the solver I still have the following question: Am I right that the variable of a summation is only visible within this scope? I circumvented this by assigning this value to a global variable. Are there better ways to do it?
Cheers
Thomas
Edited: 31 Jan 2011, 2:43 p.m. after one or more responses were posted
▼
Posts: 1,248
Threads: 33
Joined: Aug 2007
Quote:
Am I right that the variable of a summation is only visible within this scope?
Thomas, can you explain what you mean here? Thanks.
▼
Posts: 735
Threads: 34
Joined: May 2007
Let's assume we have a simple equation:
A=B+C
Now all of these three variables will be displayed in the solver menu. Compare that to a summation:
A=\GS(I:1:4:1:SQ(I))
Now only the variable A is displayed in the menu which makes perfectly sense: the variable I is a local variable to the summation. But I need to get exactly that value out and all I could think of was to use another global variable P and copy the local variable I to it. So my question was whether there's a better solution to that problem.
Thanks in advance
Thomas
Posts: 1,392
Threads: 142
Joined: Jun 2007
Quote: Am I right that the variable of a summation is only visible within this scope? I circumvented this by assigning this value to a global variable. Are there better ways to do it?
It seems the solver knows that the index to a sigma function is probably something that the user does not want to see in the menu, because your menu does not include your loop indexes A, B, C, and D. So, yeah, the way you did it is probably the best way.
That's great work, Thomas, as is usual for you. I don't think I have the patience to extend it to the 8-queens myself, but I am curious as to how long that execution would take. Perhaps Mark will pickup the ball and try his hand at "extreme HP17bii+ programming"!
Don
▼
Posts: 100
Threads: 1
Joined: Aug 2010
LOL...
Perhaps if I pick up a 17bII+ first... I've used them before; however, I've never owned one. :^)
Mark
Posts: 735
Threads: 34
Joined: May 2007
It took 6'24.1" to solve the 8-queens problem with my HP-17BII. Don't ask me how long it took me to enter the equation. Here's the solution:
{ 1, 5, 8, 6, 3, 7, 2, 4 }
Cheers
Thomas
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Is that 6 hours and 24 minutes or 6 minutes and 24 seconds? I'm guessing the former.
don
▼
Posts: 1,248
Threads: 33
Joined: Aug 2007
Standard notation indicates 6 minutes 24.1 seconds.
Posts: 1,392
Threads: 142
Joined: Jun 2007
Thomas, many thanks for your supreme effort here in proving that the 17bii is truly a "programmable" calculator. It may not be fast, certainly not like the 30b is fast, and it may be cumbersome to write programs in the solver, but you have proven that it does have the basic functions to support programming.
Did you contact Xerxes to add this to the n-queens benchmark timing list?
Mark, now you can see that the 17bii+ can support programmable functions like this. Personally, I like the challenge of seeing how much all of these programmable calculators can do. My favorite in this regards is probably the HP-65 I got a few years ago, with its limited registers and programming space and conditionals and no indirect addressing. But I am amazed at what it can do sometimes, with crafty programming. Same with the 12c. Same with the 17bii.
Don
▼
Posts: 100
Threads: 1
Joined: Aug 2010
Yes, indeed I can. Quite honestly, I wanted the 17bII+ to be able to do this, too. I think it is absolutely fantastic that Thomas pulled it off.
Mark
Posts: 136
Threads: 7
Joined: Jun 2007
Thank you Thomas, I'm really impressed. I see that I've underestimated the capabilities of the solver. I've updated the benchmark list with your result and the 4-queens-equation as example.
▼
Posts: 735
Threads: 34
Joined: May 2007
Equation for the 8-queens problem
QUEENS:
Z=A+B+C+D+E+F+G+H+
\GS(I:1:8:1:
\GS(J:1:8:1:
IF(I<>J:IF(SQ(I-J)<>1:
\GS(K:1:8:1:
IF(I<>K:IF(SQ(I-K)<>4:
IF(J<>K:IF(SQ(J-K)<>1:
\GS(L:1:8:1:
IF(I<>L:IF(SQ(I-L)<>9:
IF(J<>L:IF(SQ(J-L)<>4:
IF(K<>L:IF(SQ(K-L)<>1:
\GS(M:1:8:1:
IF(I<>M:IF(SQ(I-M)<>16:
IF(J<>M:IF(SQ(J-M)<>9:
IF(K<>M:IF(SQ(K-M)<>4:
IF(L<>M:IF(SQ(L-M)<>1:
\GS(N:1:8:1:
IF(I<>N:IF(SQ(I-N)<>25:
IF(J<>N:IF(SQ(J-N)<>16:
IF(K<>N:IF(SQ(K-N)<>9:
IF(L<>N:IF(SQ(L-N)<>4:
IF(M<>N:IF(SQ(M-N)<>1:
\GS(O:1:8:1:
IF(I<>O:IF(SQ(I-O)<>36:
IF(J<>O:IF(SQ(J-O)<>25:
IF(K<>O:IF(SQ(K-O)<>16:
IF(L<>O:IF(SQ(L-O)<>9:
IF(M<>O:IF(SQ(M-O)<>4:
IF(N<>O:IF(SQ(N-O)<>1:
\GS(P:1:8:1:
IF(I<>P:IF(SQ(I-P)<>49:
IF(J<>P:IF(SQ(J-P)<>36:
IF(K<>P:IF(SQ(K-P)<>25:
IF(L<>P:IF(SQ(L-P)<>16:
IF(M<>P:IF(SQ(M-P)<>9:
IF(N<>P:IF(SQ(N-P)<>4:
IF(O<>P:IF(SQ(O-P)<>1:
L(A:I)xL(B:J)xL(C:K)xL(D:L)xL(E:M)xL(F:N)xL(G:O)xL(H:P)/0
:0):0):0):0):0):0):0):0):0):0):0):0):0):0))
:0):0):0):0):0):0):0):0):0):0):0):0))
:0):0):0):0):0):0):0):0):0):0))
:0):0):0):0):0):0):0):0))
:0):0):0):0):0):0))
:0):0):0):0))
:0):0)))
The names of the variables have been changed: now you get the result in A-H whereas the local variables I-P are used in the summations. The result { 1, 5, 8, 6, 3, 7, 2, 4 } corresponds to the following configuration:
A B C D E F G H
+---+---+---+---+---+---+---+---+
1 | # | | | | | | | |
+---+---+---+---+---+---+---+---+
2 | | | | | | | # | |
+---+---+---+---+---+---+---+---+
3 | | | | | # | | | |
+---+---+---+---+---+---+---+---+
4 | | | | | | | | # |
+---+---+---+---+---+---+---+---+
5 | | # | | | | | | |
+---+---+---+---+---+---+---+---+
6 | | | | # | | | | |
+---+---+---+---+---+---+---+---+
7 | | | | | | # | | |
+---+---+---+---+---+---+---+---+
8 | | | # | | | | | |
+---+---+---+---+---+---+---+---+
I think this example shows both the capabilities and limitations of this nice calculator. Of course you'd prefer decent subroutines to what is named "call by editor". On the other hand you're able to solve some hard problems.
Using the solver is a little like using Excel and that's probably something business people are more familiar with than procedural programming. On the other hand it reminds me also of a functional programming language like Haskell.
As for the handling of such a huge equation I was surprised of the good support. The characters I needed most (:<>) were easy to access. Of course I made some typos but these could easily be fixed as the "debugger" just stopped at the right position. It took nearly 2 minutes for VERIFYING the EQUATION though. But I think the speed of the solver is quiet okay considering what we really do here. I was afraid to fry the batteries running the calculator for hours.
As for the timing: 00:06:23.5 is my 2nd measurement. I suppose my reaction was a little better as I expected the solver to finish at that time.
Kind regards and thanks for the interesting challenge
Thomas
Edited: 1 Feb 2011, 10:02 p.m. after one or more responses were posted
▼
Posts: 136
Threads: 7
Joined: Jun 2007
Thank you very much for your effort and the additional informations.
Schönen Gruß, Pascal
▼
Posts: 735
Threads: 34
Joined: May 2007
There was a closing parenthese missing in the last line of my listing above. Could you please correct that in your list as well?
Sorry for that lapsus
Thomas
Posts: 735
Threads: 34
Joined: May 2007
Today I realized that I could use AND instead of nested IF-statements. With this change it takes only 00:03:28.8 to solve the 8-queens problem. The listing is here:
QUEENS:
Z=A+B+C+D+E+F+G+H+
\GS(I:1:8:1:
\GS(J:1:8:1:
IF(I<>J AND SQ(I-J)<>1:
\GS(K:1:8:1:
IF(I<>K AND SQ(I-K)<>4
AND J<>K AND SQ(J-K)<>1:
\GS(L:1:8:1:
IF(I<>L AND SQ(I-L)<>9
AND J<>L AND SQ(J-L)<>4
AND K<>L AND SQ(K-L)<>1:
\GS(M:1:8:1:
IF(I<>M AND SQ(I-M)<>16
AND J<>M AND SQ(J-M)<>9
AND K<>M AND SQ(K-M)<>4
AND L<>M AND SQ(L-M)<>1:
\GS(N:1:8:1:
IF(I<>N AND SQ(I-N)<>25
AND J<>N AND SQ(J-N)<>16
AND K<>N AND SQ(K-N)<>9
AND L<>N AND SQ(L-N)<>4
AND M<>N AND SQ(M-N)<>1:
\GS(O:1:8:1:
IF(I<>O AND SQ(I-O)<>36
AND J<>O AND SQ(J-O)<>25
AND K<>O AND SQ(K-O)<>16
AND L<>O AND SQ(L-O)<>9
AND M<>O AND SQ(M-O)<>4
AND N<>O AND SQ(N-O)<>1:
\GS(P:1:8:1:
IF(I<>P AND SQ(I-P)<>49
AND J<>P AND SQ(J-P)<>36
AND K<>P AND SQ(K-P)<>25
AND L<>P AND SQ(L-P)<>16
AND M<>P AND SQ(M-P)<>9
AND N<>P AND SQ(N-P)<>4
AND O<>P AND SQ(O-P)<>1:
L(A:I)xL(B:J)xL(C:K)xL(D:L)xL(E:M)xL(F:N)xL(G:O)xL(H:P)/0
:0)):0)):0)):0)):0)):0)):0)))
Cheers
Thomas
Removed typo (empty if-statement) detected by Don Shepherd (cf. message # 32)
Edited: 4 Feb 2011, 5:33 a.m. after one or more responses were posted
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Wow, lots fewer IF's and, therefore, parentheses. Looks much nicer Thomas. You're not still keying that in on your iphone are you? : ) I see a case of carpal tunnel coming...
Don
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
You're not still keying that in on your iphone are you?
Nay, meanwhile I had access to a decent computer. Both listings for the 8-queens were generated to avoid typos. Well there still might be but now at least at similar places. Nevertheless a mobile version of this forum would be nice.
Quote:
I see a case of carpal tunnel coming...
A lot of new words I learn in this forum.
Thanks
Thomas
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
Quote:
Nevertheless a mobile version of this forum would be nice.
I'll second that. Dave, how about it? Something new for you to develop.
Thomas, Very nice work on this solver solution!
-Katie
▼
Posts: 735
Threads: 34
Joined: May 2007
Katie, guess who inspired us in doing this?
Cheers
Thomas
Posts: 735
Threads: 34
Joined: May 2007
Quote:
Wow, lots fewer IF's and, therefore, parentheses.
I was quiet surprised that this change reduced the time so much. It seems that jumps are expensive in the solver. Does anybody know the internal operating principles of this solver? What's happening during VERIFYING EQUATION... ? My speculation is that the equation is translated into some byte code. Or is it also RPL as in the HP-48? Christoph Gießelink might have an emulator and thus the ROM of this calculator. I remember a screen-shot of his desktop with pretty much every pioneer. So he could know. Or maybe someone at HP? Tim or Cyrill?
Just curious
Thomas
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Thomas, I suspect you are right about what happens during Verifying Equation. Something interesting I found was the difference between the original 17b and 17bii and the plusses regarding this behavior. The 17b (and bii) take much longer during the "verifying equation" phase, but are much quicker to actually solve the same equation than the plusses. Personally, I'd rather have the fast response during the execution phase rather than the "compile" phase, so I prefer the originals.
Don
▼
Posts: 1,248
Threads: 33
Joined: Aug 2007
Don,
I own only the original 17b. Besides the RPN option (and different color scheme), are there other significant difference in the 17bii? (Not +).
As an aside, too bad HP never made a 27sii (with RPN option). Might have made even 42s fans take a look.
Which is why I advocate a new scientific that incorporates the best features of both 42s and 27s.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Quote: Besides the RPN option (and different color scheme), are there other significant difference in the 17bii?
I think that's the only difference, Martin. I'm pretty sure they have the same amount of memory, and I know the solvers are the same.
▼
Posts: 1,248
Threads: 33
Joined: Aug 2007
Posts: 100
Threads: 1
Joined: Aug 2010
Thomas,
Awesome optimizing, there. It looks like Xerxes is going to have to update the benchmark table again. I want to reiterate how impressed I am with this and the fact that you took this task on. Good job!
Regards,
Mark
Posts: 136
Threads: 7
Joined: Jun 2007
What a nice optimization. Your work demonstrates the power of the solver in a very interesting way.
Posts: 1,392
Threads: 142
Joined: Jun 2007
Thomas, was it your intention to have an IF with no condition (line 4)? I've started to enter this on my 17bii+ and this seemed weird.
Don
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
OK, I entered this one on my brown/rubbery 17bii+ from 2007, and it gets the correct answer in 6 minutes 25 seconds, quite a bit slower than the original 17bii which does not surprize me. But the fact that it can be done at all is still amazing for an officially "non-programmable" calculator.
Thomas, very nice work and I am in awe of what you have done.
Don
Edited: 4 Feb 2011, 6:06 a.m.
▼
Posts: 735
Threads: 34
Joined: May 2007
Don, it was a typo. I removed the superfluous line. Thanks for pointing that out and for taking the time to enter that equation into your calculator. Based on your measurement it should rather be called HP-17bii-. Or what is considered to be the improvement?
Did you notice that the HP-17BII is right between the HP-42S with ROM versions A and C (using Turbo + Fast mode) in Xerxes' Calculator Benchmark list? Not bad, I'd say.
Best regards
Thomas
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Quote: Or what is considered to be the improvement?
I guess the only real improvement is increased storage space, which is good if you're going to use lots of equations. I do wish they would have left the solver alone, however.
Posts: 136
Threads: 7
Joined: Jun 2007
Thank you for testing the HP-17BII+. I've updated the list with your result and the corrected equation.
Posts: 100
Threads: 1
Joined: Aug 2010
Thomas,
I am extremely impressed by this accomplishment. Kudos to you.
Regards,
Mark
Posts: 1,248
Threads: 33
Joined: Aug 2007
Now I want to know: does this mean the 17bii is programmable?
▼
Posts: 1,841
Threads: 54
Joined: Jul 2005
Yes, of course. Not in a sense like the HP-41, but you can enter and evaluate expressions, which themselves can call and include other expressions;-)
▼
Posts: 1,248
Threads: 33
Joined: Aug 2007
Raymond,
My question was somewhat tongue-in-cheek because of an earlier discussion in another thread. Not sure if you saw that one. It included the following comment by Mark Harman:
Quote:
I remain unconvinced of the extent of programmability of the 17b series. They're great calculators and the menu-based Solve is awesome, but I think by its nature it is more limited than other programmable machines. Perhaps this is where creativity comes in and a good programmer can really shine in this regard.
Still, if you want to really impress me and, at the same time, make me a true believer of the 17's programming capability, write a version of the N-queens benchmark program for the 17bII+, execute it, and submit the time. ;^) As of yet, nobody has done this. Personally, I think this is a golden opportunity to prove all the naysayers wrong - if possible.
I have always maintained that the "Solver only" HP's are indeed programmable.
Posts: 114
Threads: 18
Joined: Jan 2011
Yes. Any calculator which is Turing-complete is 100% programmable one.
And solver of HP-17BII is definetely Turing complete.
I'm trying now to prove turing-completeness of HP-35S' solver.
However, not EVERY HP Solver is Turing complete. e.g. solvers of HP-32SII and HP-33S are NOT Turing complete. There is no known way to alter registers in Solver of these calcs. (Calcs themselves are complete, only Solver is not).
▼
Posts: 1,248
Threads: 33
Joined: Aug 2007
Well, I guess that settles it. So it was not necessary after all to develop a N-Queens routine to prove programmability.
▼
Posts: 114
Threads: 18
Joined: Jan 2011
I think the purpose of solving N-queen problem was different.
a. To measure the speed, so HP-17B could be added to famous Xerxes' list-o-fame.
b. The main one, i guess. To prove thyself thou CAN do it, and thou DID it. It's the most amazing thing with calcs to do - they are just means, not purpose - to make amazing things.
And. there is one more. If computer is not Turing-complete, it does not imply it could solve no problems. It just says it could solve not ALL problems, the other are capable of.
But, of course, if you have a problem and you know the computer is turing-complete, it gives you idea it could be solved.
Posts: 100
Threads: 1
Joined: Aug 2010
I was actually already convinced of programmability after given a good definition of what being programmable meant and being told that it could run a prime factor solver. At the point I asked about the N-queens benchmark, I just wanted to know to what it extent the machine was programmable. I thought that it would be limited since the n-queens problem, I feel, tests very well the robustness of a computer's level of programmability. With Thomas's feat, I am now convinced that creativity and patience can allow for a lot of complexity and variety in 17b series Solver programs.
It may not be a speed demon, but the fact that it can do N-queens is a heck of a lot more than what many calculators out there can do. I think it is awesome that it can be done. I will probably still not buy one of these machines, but I have a lot more respect for what its Solver can do now.
Also, I wasn't aware that the 17b series Solver was Turing Complete. Knowing this now helps me see better why Thomas was able to accomplish such an impressive display of programming.
Regards,
Mark
Edited: 1 Feb 2011, 12:52 p.m.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
This was all documented years ago on this forum, and I learned it through a painful experience, but there are differences between the solver in the 17b and 17bii and the solver in the 17bii+ (both brown and silver). Essentially, the solver in the 17b and bii operates like a programmer thinks it would; the solver in the plusses does not always do that.
This can be illustrated by a simple equation to get the sum of digits from input N:
a=sigma(i:0:log(n):1:mod(n:10)+0*l(n:idiv(n:10)))
Solve for A. Works like a trooper on the 17b and 17bii, but on the 17bii+ it results in "solution not found" because the solver on the plusses does a pre-evaluation pass of the equation to calculate items that can be precalculated (per Cyrille), but to do this it actually executes the equation twice, and the first pass (which the 17b does not do) reduces n to 0 so when you try to do log(n) when n is 0 in the second pass you get the error message. Now, there are workarounds, but anyone who intends to write "programs" for the plusses needs to be aware of this. When I got my 17bii+ years ago and tried that equation and it didn't work, I wrote HP and they told me the equation was "meaningless." That offended me greatly.
Don
▼
Posts: 2,448
Threads: 90
Joined: Jul 2005
Quote:
When I got my 17bii+ years ago and tried that equation and it didn't work, I wrote HP and they told me the equation was "meaningless."
That would offend me, too!
Posts: 1,248
Threads: 33
Joined: Aug 2007
Quote:
There is no known way to alter registers in Solver of these calcs.
Would you elaborate? What exactly do you mean by "alter registers"?
▼
Posts: 114
Threads: 18
Joined: Jan 2011
I mean 33S and 32sII lack "STO: (or L() in 17B terms) in solver, while solver of 35s has it.
Posts: 735
Threads: 34
Joined: May 2007
Quote:
And solver of HP-17BII is definetely Turing complete.
I'm trying now to prove turing-completeness of HP-35S' solver.
I'd be interested in both proofs.
Cheers
Thomas
▼
Posts: 114
Threads: 18
Joined: Jan 2011
Thomas, my proof attempt is vulgar, and so we should settle on rules first.
1. Ability to read/write memory register.
2. Ability to change value before writing. i.e. read A, store A+1
3. Ability to execute conditional statement (IF A THEN B), a-la
X<=Y?:STO+3 B
4. Ability to make conditional jump (X>Y?: GOTO A)- this is a hard nut on HP-35S.
Something not mentioned here? These are all from my memory.
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
4. Ability to make conditional jump (X>Y?: GOTO A)- this is a hard nut on HP-35S.
This is the point where I have my doubts concerning the HP-17BII. My equation uses an error to exit the nested loop but that terminates the program as well. Big problem when you need to continue the calculation because this is only an intermediate result. The same problem arisies with Katie's trick. We can start the solver only once. So I can imagine that there might be relatively easy problems that can't be solved with this calculator.
But I must confess that I dont understand yet what "Turing complete" exactly means.
Kind regards
Thomas
▼
Posts: 114
Threads: 18
Joined: Jan 2011
Wiki says http://en.wikipedia.org/wiki/Turing_complete
"This requires, at a minimum, conditional branching (an "if" and "goto" statement) and the ability to change arbitrary memory locations."
Basicaly, i remember the same.
more can be find here:
http://en.wikipedia.org/wiki/Turing_machine_equivalents#Register_machine_models
So, we need only JUMP IF EQUAL (e.g. simulate jump) to meet conditions.
Considering HP-17 - am i correct that you can:
a) Use multiple sigmas in one equation?
b) Change ending value of Sigma in it's expression?
c) Store values inside Sigma'e expression? (Is it possible to write
smth like (A+X^I>B) in expression? It is not clear in the manual.
Edited: 1 Feb 2011, 4:22 p.m.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
a) absolutely
b) not allowed, I'm pretty sure, because that would let you end a loop early which is not allowed
c) yes, via L()
▼
Posts: 114
Threads: 18
Joined: Jan 2011
Don, is it possible to use IF inside Sigma's algebraic expression?
b) So, only RCL of loop parameter allowed inside it.
And by A+X^I>B i mean A+X^I STO B to be precise
Edited: 1 Feb 2011, 6:22 p.m.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Quote: possible to use IF inside Sigma's algebraic expression?
Sure, look at Thomas' program above, IF's are all over the place inside the sigmas. That's fine.
Quote: only RCL of loop parameter allowed inside it.
Not sure what you mean by this. RCL is not something that can be in an equation, but you can use the loop index however you want, you just can't change it.
Quote: by A+X^I>B i mean A+X^I STO B to be precise
No, you can't use STO inside an equation either, which means you can't use the registers R0-R9 in an equation, but you can use variables, so this is not a huge limitation, IMO.
HTH
▼
Posts: 1,248
Threads: 33
Joined: Aug 2007
Quote:
No, you can't use STO inside an equation either, which means you can't use the registers R0-R9 in an equation, but you can use variables, so this is not a huge limitation, IMO.
Exactly! This is one of the great features in the 17b - 27s Solvers. Not only can you have an "unlimited" number of variables, but they can have descriptive names. You can even STO and RCL them (from the keyboard), at least while the equation in which they occur is active.
It was a huge blunder for HP to use the antiquated 32sii Solver in the 35s instead. Or at least a missed opportunity.
Posts: 1,392
Threads: 142
Joined: Jun 2007
The absolute best resource regarding the solver in the 17bii is the Technical Applications Manual for the HP-27S and HP-19B. It has whole sections on Get(), Let(), intermediate variables, multiplication by 0 method, using the sigma function, and simulating an indefinite loop (which essentially "does nothing" after a certain point in the loop is reached, but it doesn't really exit the loop so it will still do all of the iterations you originally told it to do), and the manual lists about 9 solver routines to accomplish various tasks, including finding prime factors and determining the GCD and LCM.
This manual is on the museum DVD set (2719tech.pdf).
Posts: 114
Threads: 18
Joined: Jan 2011
http://www.palmtoppaper.com/ptphtml/7/ptp7005c.htm
It describes HP-95LX Solver. May be it is equivalent to HP-17BII?
@The expression "0*L(initial:initial+10)" adds nothing to the value of "initial^2" because it is multiplied by zero. However, it does increase the value of initial by 10 each time you solve for "answer." @
So, it says *you can* change some of the FOR LOOP parameters. Is it true? If so, it makes pure BREAK possible.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
I'm not sure if the solvers in these two machines are the same, but the Applications Manual I referenced above (for the 27s and 19b and I believe the 17b) says:
Quote:
When the sigma function is first encountered in an equation, the solver stores the step size s and the counter variable's initial and final values c1 and c2 in a special location in memory not accessible to the user. Any attempt to alter the values of s, cv, c1, or c2 using the LET function causes the solver to create separate variables of the same name. Since the value of these variables (referring to the original s, cv, c1, and c2 I believe) cannot be changed, a loop cannot be prematurely exited. This is precisely what makes construction of a true indefinite loop impossible.
So once you start a loop, it will complete all its specified iterations. About the only thing you can do to terminate a loop early, and what Thomas did, is do an illegal instruction (divide by 0 always works nicely, as does log(0)) within the loop when a certain condition occurs and after storing a value of interest in a global variable. This stops the loop--and unfortunately stops evaluation of the equation--but you can RCL the variable where you stored something of interest to see it.
Edited: 2 Feb 2011, 9:32 a.m.
Posts: 114
Threads: 18
Joined: Jan 2011
Since my understanding of HP-17BII Solver is adequate now (with the big help of forum members), here is vulgar proof of it's Turing completeness. Our goal is SUFFICIENT completeness, with finite number of steps and memory locations.
a) Solver can read/write/modify variables. (Proved by forum)
b) Solver has conditional statement (IF). (Proved by manual and forum)
c) You can use multiple assignments and IFs inside Sigma loop
We need to prove we can use jumps (branches)
Sigma is essentialy equivalent to FOR LOOP.
BREAK could be emulated easily using IF inside FOR (with finite N):
FOR I IN [1..N] DO
IF (X>0) THEN BREAK; END IF;
EXPRESSION LIST;
END FOR;
is equivalent to
FOR I IN [1..N] DO
IF (X<=0) THEN
EXPRESSION LIST;
END IF;
END FOR;
Sure, there would be empty cycles, but it would do the same
Any BREAK position inside FOR could be rewritten using IF.
(We could emulate any loop iterator with FOR)
Having FOR with BREAK is equivalent to GOTO.
backward label:
LBL L:
EXPR1;
EXPR2;
IF A>B THEN GOTO L; END IF
is equivalent to
L:=TRUE;
FOR I IN [1..N] DO
IF L THEN
EXPR1;
EXPR2;
END IF;
L:=(A>B);
END FOR;
Forward label is trivial:
EXPR1;
IF A>B THEN GOTO L; END IF;
EXPR2;
LBL L: EXPR3;
EXPR1;
IF A<=B THEN
EXPR2;
END IF;
EXPR3;
Nested IFs (if they are not supported bu HP-17) could be
unrolled, e.g.
IF A>B THEN
IF C<D THEN
EXPR1;
END IF;
EXPR2;
END IF;
IF (A>B) AND (C<D) THEN EXPR1; END IF;
IF (A>B) THEN EXPR2; END IF;
So, we have all turing critera met.
Please, tell me where i am wrong.
Regards,
x34
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
FOR I IN [1..N] DO
IF (X>0) THEN BREAK; END IF;
EXPRESSION LIST;
END FOR;
is equivalent to
FOR I IN [1..N] DO
IF (X<=0) THEN
EXPRESSION LIST;
END IF;
END FOR;
What happens if the EXPRESSION LIST has side effects? Let's assume it just increments a counter. In the upper FOR-loop it counts the passes until the break-condition is met for the 1st time while in the lower it counts how many passes don't meet the break condition which is not the same.
However this can be fixed with an additional variable DONE. What we really want to have are expressions before and after the break:
FOR I IN [1..N] DO
EXPRESSION LIST A;
IF (X>0) THEN BREAK; END IF;
EXPRESSION LIST B;
END FOR;
This is equivalent to:
DONE=0
FOR I IN [1..N] DO
IF (DONE==0) THEN
EXPRESSION LIST A;
IF (X>0) THEN
DONE=1
ELSE
EXPRESSION LIST B;
END IF;
END IF;
END FOR;
I'm still not 100% convinced that an endless-loop and a for-loop are equivalent. But you might say that there isn't something as an endless-loop in a finite machine. Or how would you argue?
Best regards and thanks for your interesting contribution
Thomas
Edited: 2 Feb 2011, 11:36 a.m.
▼
Posts: 114
Threads: 18
Joined: Jan 2011
Quote:
Quote:
What happens if the EXPRESSION LIST has side effects? Let's assume it just increments a counter. In the upper FOR-loop it counts the passes until the break-condition is met for the 1st time while in the lower it counts how many passes don't meet the break condition which is not the same.
This could be rewritten to avoid side effects, as you illustrate:
Quote:
However this can be fixed with an additional variable DONE. What we really want to have are expressions before and after the break:
FOR I IN [1..N] DO
EXPRESSION LIST A;
IF (X>0) THEN BREAK; END IF;
EXPRESSION LIST B;
END FOR;
This is equivalent to:
DONE=0
FOR I IN [1..N] DO
IF (DONE==0) THEN
EXPRESSION LIST A;
IF (X>0) THEN
DONE=1
ELSE
EXPRESSION LIST B;
END IF;
END IF;
END FOR;
Absolutely!
[quote[
I'm still not 100% convinced that an endless-loop and a for-loop are equivalent. But you might say that there isn't something as an endless-loop in a finite machine. Or how would you argue?
No. i will not argue. You are right, they are not equivalent in general. But I think it simply does not matter here, because Endloss loop is not a request for Turing-Completeness,so i don't count it as an objection.
BTW, finite machine CAN have an endloss-loop if it is one of the states. Many of them actually have, like a telephone answering machine.
In our case (calculator) if you can make a 1E12 iterations cycle, it would be practically infinite. But actually TWO types of loops should be used - the one with simulated BREAKs would be impractical if near infinite. "Cray is so fast, it can do infinite loop in two seconds!" - it was popular saying in the 80's :)
And your solution of Queens is much faster than could be done with
"emulated" constructions.
Quote:
Best regards and thanks for your interesting contribition
Thomas
Thanks to you!
[pre]
Actually, i have a problem with HP-35S Solver.
What we have on HP-35S is:
a) One external loop, designed by Katie
b) Unlimited IFs
IFs are emulated with 0*((BOOLEAN RESULT) EXPRESSION).
X=0? is equivalent to 1-SGN(ABS(X)) or NOT(SGN(X))
X<Y?==NOT(SGN(Y-X)-1)
X>=Y?==NOT(SGN(X-Y)-1)+NOT(SGN(ABS(X-Y))
and so on.
I could not yet understand, if a lot of "IFs" within eternal loop
could be considered equivalent to GOTO and/or recursion.
I personaly think they are NOT equivalent, however could be used for
small tasks.
In any case, there would be EXTREMELY difficult to write 8 queens in the HP-35S Solver, however possible, even if it is not turing-complete. I will try to write simple compiler or macros to do it, but not soon.
May be someone will find a way to make any kind of iteration (loop) besides the outer one in HP-35S Solver? I hope so.
[pre/]
Posts: 735
Threads: 34
Joined: May 2007
A summary of this thread can be found in the HP Articles Forum: N-queens benchmark and the HP-17BII
Cheers
Thomas
|