To give a clear definition:

1) No wire delay

2) Any number of bits(including infinity) doing NAND(and therefore all the lead-out logics) operation cost O(1) time

3) There are only finite layers(so you can't find a logic chain longer than a fixed value)

4) There may be an input of countable infinity size

To define calculate: You are allowed to say, for i in N(0 to infinity), or maybe a few for's, (a,f(i))->(c,g(i)), where a<c, and f and g are functions with plus, minus and merge(packing two integers into one). The expression should be finite.

E.g. Increase a binary number a[inf]..a[0] by 1:

f[i] = a[i] xor (a[i-1] and a[i-2] and ... and a[0])

E.g.2 Add two binary numbers a[inf..0] and b[inf..0]:

u[i] = a[i] or b[i]

t[i] = a[i] and b[i]

s[i][j] = u[i-1] and u[i-2] and ... and u[i-j]

c[i] = t[i-1] or (t[i-2] and s[i][1]) or (t[i-3] and s[i][2]) or ... or (t[0] and s[i][i-1])

f[i] = c[i] xor a[i] xor b[i]

E.g.3 Adding two real numbers: Get (0.a[0]a[1]a[2]...+0.b[0]b[1]b[2]...)mod 1

f[i] = a[i] xor b[i] xor ((a[i+1] and b[i+1]) or ((a[i+1] or b[i+1]) and (a[i+2] and b[i+2])) or ((a[i+1] or b[i+1]) and (a[i+2] or b[i+2]) and (a[i+3] and b[i+3]))...)

  • $\begingroup$ What have you tried? Where did you get stuck? By infinity as the input, do you mean INF - a number that tells it is not a number or do you really mean that infinite input costs one unit to read? $\endgroup$ – Evil Sep 23 '17 at 13:44
  • $\begingroup$ We have an infinity circult, which means that there can be infinity parallel calculating, so there should be nothing strange if it can handle an infinity size input. 2) makes it possible to get a result bit affected by an infinity number of inputs. $\endgroup$ – l4m2 Sep 23 '17 at 15:35
  • $\begingroup$ It's a curiousty problem. I'm not stuck at xx. $\endgroup$ – l4m2 Sep 23 '17 at 15:36
  • 2
    $\begingroup$ Everything can be computed using depth 2 circuits, so it seems your circuit will be able to compute any function. $\endgroup$ – Yuval Filmus Sep 23 '17 at 16:47
  • $\begingroup$ I'm not sure what you're asking. A single circuit has a fixed number of inputs and, since there are only finitely many different functions $\{0,1\}^n\to \{0,1\}$ for any $n$, you only need finitely many gates to express anything that can be expressed. $\endgroup$ – David Richerby Sep 23 '17 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.