Computing desk
< June 16	<< May \| June \| Jul >>	Current desk >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 17

Z3 and Turing completeness

The Z3 didn't have a conditional branch instruction, but the article says that it Turing complete in a sense - it could execute all possible branches. If there were a large number of branches, would this result in a huge amount of output and the correct result would be in there somewhere? Bubba73 ^{You talkin' to me?} 01:56, 17 June 2019 (UTC)[reply]

Basically it uses a programming trick to simulate an n-way case statement with n blocks of straight-line code followed by using arithmetic to select which result to use. So it's a polynomial-time blowup of degree depending on the depth of nested case statements, I think. It's explained in the Rojas paper cited in the article but I only looked at it briefly. 67.164.113.165 (talk) 09:53, 17 June 2019 (UTC)[reply]

My point is that it executes all branches, so I assume there is output for each branch. How can you look at the output and tell which part of it is for the correct branch(es)? Bubba73 ^{You talkin' to me?} 01:58, 18 June 2019 (UTC)[reply]

Would a link to case statement help ? SinisterLefty (talk) 02:16, 18 June 2019 (UTC)[reply]

No. Bubba73 ^{You talkin' to me?} 03:36, 18 June 2019 (UTC)[reply]

Here's a thing I wrote in 2008, doing a branchless strlen in C. It does indeed evaluate all possible "branches", and then uses arithmetic to report only the "successful" one. It's been 11 years since I thought about this, so I'm rusty on the minutea of the discriminator, but here goes:

here be dragons

#include <stdio.h>
#include <string.h>

// implements the followng logic:
//  if CONDITION return VALUE else return 0
#define CONDFUNC1(CONDITION,VALUE) ((VALUE)&(0xFFFFFFFFU+(!(CONDITION))))

// a branchless strlen, which reports the length of strings, as long as it's <= 5
int branchless_strlen5(const char * str){
  return 
    CONDFUNC1(str[0]==0,0)+
    CONDFUNC1(str[0]!=0,
	      (CONDFUNC1(str[1]==0,1)+
	       CONDFUNC1(str[1]!=0, 
			 (CONDFUNC1(str[2]==0, 2)+
			  CONDFUNC1(str[2]!=0, 
				    CONDFUNC1(str[3]==0, 3)+
				    CONDFUNC1(str[3]!=0, 
					      CONDFUNC1(str[4]==0,4)+
					      CONDFUNC1(str[4]!=0,
							CONDFUNC1(str[5]==0,5)+
							CONDFUNC1(str[5]!=0, 99999) // OVERFLOW
							)
					      )
				    )
			  
			  )
			 )
	       )
	      )
    ;
}

int main() {
  const char basicstr[]="abcde";
  char teststr[]="----------------";

  for(int x=0;x<7;x++){
    strcpy(teststr,basicstr);
    teststr[x]=0;
    teststr[x+2]=0;
    printf("for x=%d, naive_strlen=%ld, branchless_strlen5=%d\n", 
	       x, 
           strlen(teststr),
           branchless_strlen5(teststr)
          );
  }

  return 0;
}

The meat of the thing is the CONDFUNC. I produced three variants, none of which are exactly fun to read:

#define CONDFUNC1(CONDITION,VALUE) ((VALUE)&(0xFFFFFFFFU+(!(CONDITION))))
#define CONDFUNC1(CONDITION,VALUE) ((VALUE)&((!(CONDITION))-1))
#define CONDFUNC1(CONDITION,VALUE) ((VALUE)&((~(CONDITION)&1)-1))

Does that amount to Turing completeness? I dunno. Bletchley Park's later computery things had "looping" because the "program" was actually on a physical paper loop, I don't know about the Z3.

A tiny aside: this horrid species of "deciding without branching" isn't quite a thing of the past. Check out OpenBSD's timingsafe_memcmp, which aims to take the same amount of time comparing two strings, regardless of the position in which they differ (which is used to help resist a timing attack). -- Finlay McWalter··–·Talk 10:38, 18 June 2019 (UTC)[reply]

Let me clarify. The Z3 had no conditional branch instruction. The paper said that it could simulate a Turing machine by executing all branches. Suppose that a program has one branch, depending on whether a variable, x, is odd or even when it gets to that point. Now, considering executing all branches. It executes the code if x is odd and the code if x is even. It produces output for each of those branches. But how do you know what part of the output is the correct output? And if there are many branches, there will be a huge amount of output and only a tiny part of it will be correct, and how do you know where that is? Bubba73 ^{You talkin' to me?} 19:32, 18 June 2019 (UTC)[reply]

I understand what you mean fine. But it doesn't "produce output for each of those branches"; it calculates the result of each branches, and then calculates which of those to report as a final result based on a tricksy piece of bitwise arithmetic. Here's the simplest C example I can think of (which uses effectively the second CONDFUNC1 definition above) - here branching_f is ordinary branching code (with an if statement, that only works on a conventional computer, and branchless_f is the equivalent code, which produces the same result, but has no if or other branching instruction (the main() is a simple test harness to show the two are equivalent). branchless_f would (notionally) work on a machine like the Z3 with no branch instruction, because it only uses arithmetic and bitwise operations, and the control flow is entirely linear.

another dragon

#include <stdio.h>

#define IS_EVEN(Z)((Z)%2==0)

int branching_f(int x){
  int y;
  if(IS_EVEN(x)) {
    y = x*x;
  }
  else {
    y = x*x*x;
  }
  
  return y;
}

// effectively, EXPAND(0) returns 0 and EXPAND(1) returns 0xFFFFFFFF
#define EXPAND(V) ((!(V))-1)

int nonbranching_f(int x){
  // calculate both paths
  int a = x*x;
  int b = x*x*x;

  // calculate which result we want
  int disc = IS_EVEN(x);

  // and discriminate between them, producing the result we care about
  int result = (EXPAND(disc)&a) | (EXPAND(!disc)&b);

  return result;
}

int main(){
  for(int x=0; x<10; x++){
    int y,z;

    y = branching_f(x);
    z = nonbranching_f(x);
    
    printf ("%d,%d,%d\n", x, y, z);
  }
  
  return 0;
}

If there were many paths, that is inefficient, and the discriminator logic at the end is concomitantly complex. But eventually there is still a single output, z. -- Finlay McWalter··–·Talk 21:03, 18 June 2019 (UTC)[reply]

OK, I didn't know that it then goes back and figures out which results to output. That answers my concern. Bubba73 ^{You talkin' to me?} 21:25, 18 June 2019 (UTC) [reply]

Resolved

How does a machine with no branch instruction manage loops such as for(int x=0;x<7;x++){...} and for(int x=0; x<10; x++){...}  ?

DroneB (talk) 21:34, 18 June 2019 (UTC)[reply]

It doesn't, really. Those loops in my examples are for the test harnesses; only the code in nonbranching_f is what you'd actually run on the branchless computer. The rest is just to help me illustrate that it does actually do a de facto if without actually branching.

On the branchless computer, you'd have to unroll the loop:

     printf("%d\n",  nonbranching_f(0));
     printf("%d\n",  nonbranching_f(1));
     printf("%d\n",  nonbranching_f(2));
     printf("%d\n",  nonbranching_f(3));
     // etc.

... which is effectively what branchless_strlen5 above does.

That said, there's one wrinkle left. If you can persuade the hardware to perform what's effectively a computed_goto (i.e. JMP X, where X is the contents of a register), you can use a similar mechanism to the above to jump to one path or the other, and effectively implement a real(ish) if without an explicit branch instruction. Scarier still, on a primitive machine where the linear program is stored on a looping medium like the Colossus computer's paper tape loops, or a drum memory, then a computed goto is effectively a wait (N) operation. So if the hardware were to support that (or could be tortured in some way to effectively do so), then you'd tell the CPU to hang for (precisely!) long enough for the desired instruction to loop around and then start running again. It's terrible, but if your PC is just the current position of a physical object that the computer itself doesn't control, you're stuck doing terrible things. -- Finlay McWalter··–·Talk 21:59, 18 June 2019 (UTC)[reply]

I forgot to say - with that computed goto, you could actually implement a real loop. -- Finlay McWalter··–·Talk 22:11, 18 June 2019 (UTC)[reply]

Thank you for all of your help in understanding it. Bubba73 ^{You talkin' to me?} 01:43, 19 June 2019 (UTC)[reply]

Programming in assembler you would modify directly the address in some unconditional branching instruction in order to jump to the right line in a table. Here for example if x is even its last bit must be 0 and if it is odd its last bit must be 1, so:

add +1, (x and 1) * 2

jmp +1

mov y, x*x

jmp +2

mov y, x*x*x

...

That means: (x and 1) returns the last bit of x which is added to the next instruction, resulting in "jmp +1" or "jump +3" dependig on (x and 1) being zero or one. So you execute the instruction "mov y, x*x" or the instruction "mov y, x*x*x" as intended, without implementing explicitly a test on the value of x and importantly without executing all possible branches. The point is, you need to think of a form of your test such that you can use the result of an operation as an index in a table. By the way, a conditional branch in this case would look like "jmpnz +3", i.e. "jump to the third instruction from here if the accumulator is not zero (and to the next one if it is)". I wonder why Zuse didn't implement this. It would be interesting to see some original source code. 2003:F5:6F04:3400:C50F:E088:B2D:224E (talk) 17:08, 22 June 2019 (UTC) Marco Pagliero Berlin.[reply]

Modern assembly on a modern architecture isn't very relevant - the Z3 didn't have jump instructions at all, conditional or not. When the Z3 (computer) article says "program code was stored on punched film" it really does mean "stored" and not "loaded into RAM from tape". The Z3 read an instruction from tape, decoded and executed it, and then advanced the tape one position. You can't "jmp +2" because that tape isn't in the computer's own control - it advances automatically. So the Z3 just works on the linear sequence of instructions the tape contains. All it has is a tiny amount of storage, which is just adequate to store the variables in a very simple calculation. This article details the Z3's miniscule instruction set (all 7), and says "The instruction most conspicuously absent from the instruction set of the Z3 is conditional branching. Loops can be implemented by the simple expedient of bringing together the two ends of the punched tape." - that wording is perhaps slightly unfortunate, as it might be taken to mean that the Z3 has an unconditional branch, which it doesn't. And that "loop" (which really is a loop of tape) is unbreakable (until the operator actualy stops the machine from advancing, by intervening externally). Perhaps, given more time and expericence with such machines, successors to Z3 or Colossus would have added a "skip N" instruction, allowing it ignore the next N instructions (with special wiring in the instruction decode logic, and a special N register to count down to the point where it started following orders again) - but in practice, successor machines (even before the advent of stored program computers) used more sophisticated means of encoding programs - e.g. ENIAC#Programming. -- Finlay McWalter··–·Talk 15:41, 26 June 2019 (UTC)[reply]

What is a guccounter?

I've seen this in URLs, especially when signing in to email, but I saw it several times today. I did a Wikipedia search and it only seemed to be in URLs in references. So it probably needs to be added to Wikipedia, but where?— Vchimpanzee • talk • contributions • 20:27, 17 June 2019 (UTC)[reply]

The only reference I've seen is this. Martin of Sheffield (talk) 21:35, 17 June 2019 (UTC)[reply]

That's not going to be helpful. Anyway, I have more than one AOL account because I didn't know AIM mail and AOL mail were the same thing. That's where I first saw it.— Vchimpanzee • talk • contributions • 21:42, 17 June 2019 (UTC)[reply]

<redacted>?folderType=INBOX&guccounter=2&showImages=true&offset=0 is a URL (minus personal information) for an email I just sent myself.— Vchimpanzee • talk • contributions • 21:53, 17 June 2019 (UTC)[reply]

Everything after ? is a query string. It is a set of variable names and values. A programmer can use any variable name he or she wants to use. So, the developer for that website decided to use a variable name called "guccounter". For you, the value was set to 2. If you want to know exactly what it means, you absolutely must contact the developer. It is absolutely impossible for anyone else to know exactly what it means. We can only guess at what the developer meant. 68.115.219.130 (talk) 12:40, 18 June 2019 (UTC)[reply]

Well, if every time you do a certain thing on the web site, that counter goes up by 1, then you would have a good indication what it's counting. You could also try the "View Page Source" option (CTRL U in Chrome), although there's no guarantee that you could decipher the meaning from that. SinisterLefty (talk) 14:27, 18 June 2019 (UTC)[reply]

Today, with the email address I use most, I saw some URLs with the guccounter at 1, and some at 2.— Vchimpanzee • talk • contributions • 13:54, 19 June 2019 (UTC)[reply]

Today, I have a variable named ahti. Sometimes it is 0. Sometimes it is 1. Sometimes it is 2. I've seen it get up to 3 before. But, what does that mean? I know what ahti means because I named that variable. If you ask 100 people, you will get 100 guesses. If you ask me, I can tell you exactly what it means. That is the point here. You can ask 100 people what guccounter means. You will get 100 guesses - and those are nothing more than guesses. If you ask the developer, you can get an answer. Absolutely nobody here is a developer for AOL. So, absolutely nobody here can give you the answer that you want. 209.149.113.5 (talk) 11:21, 19 June 2019 (UTC)[reply]

Forgot to sign yesterday. I was just pointing out that I got different values for the same email address at different times.— Vchimpanzee • talk • contributions • 13:54, 19 June 2019 (UTC)[reply]

I was trying to point out that the values are meaningless if you don't know what the values represent. If this is a concern for you, you need to contact AOL's support staff. It is readily available at help.aol.com. I am not claiming that they will actually help you. I am claiming that if anyone could help, it would be a developer at AOL. In the end, this is a reference desk. There are no public references that explain the meaning of every variable in every program used by AOL. So, your request for a reference can only be answered by telling you to ask AOL. If the value is 99 tomorrow. The answer is still the same. Ask AOL. If the variable vanishes the next day, the answer is still the same. Ask AOL. 12.207.168.3 (talk) 16:14, 19 June 2019 (UTC)[reply]

I'm not asking anyone. I'm just saying what people think is true isn't true. And AOL is not the email service I was using at the time. That was the first email service where I saw it.— Vchimpanzee • talk • contributions • 18:37, 20 June 2019 (UTC)[reply]

Wikipedia:Reference desk/Archives/Computing/2019 June 17

Contents

June 17

Z3 and Turing completeness

What is a guccounter?