Complex Boolean networks obtained by diagonalization (Q1060185)

The author shows that by using a mildly sophisticated version of a conventional diagonal argument, complex Boolean networks can be constructed by suitable polytape machines. More precisely: ''For every \(s>1\) there is a constant \(c_ s\) and a polytape machine \(T_ s\) which, when given the string \(1^ n\) as input, constructs a propositional formula \(F^ s_ n(X_ 1,...,X_ s)\) having the property: if B is a Boolean network with n input nodes whose total number N of nodes satisfies \(N\leq c_ s\cdot n^ s\cdot (\log n)^{-1}\), then the set \(\{\) \(\xi\) \(|\) \(\xi =(\xi_ 1,...,\xi_ n)\in \{0,1\}^ n\) and \(B(\xi)=1\}\) is different from the set \(\{\) \(\xi\) \(|\) \(\xi =(\xi_ 1,...,\xi_ n)\in \{0,1\}^ n\) and \(F^ s_ n(\xi_ 1,...,\xi_ n)\) is true\(\}\) (with B(\(\xi)\) the value computed by B on input \(\xi)\).''