<p>Consider the following building blocks, which can be used to construct a logic circuit:</p>

<ul>
<li>basic logic gates {OR, AND, NOT} which have $n$ input and $m$ output pins, with $n,m\ge 1$.  </li>
<li>generators of stable values {0,1}.</li>
<li>links, which can be used to join each other logic gates or generators.</li>
</ul>

<p>Signal traversing a link have a propagation delay between a minimum $d_{min}$ and a maximum finite value $d_{max}$, with $0&lt;d_{min}&lt; d_{max}$. Different links may have different minimum and maximum values. When an input pin of a gate changes its value, the output value of the gate is instantaneously computed and, if the output value is changed, it is sent through all the output links. </p>

<p>In order to "execute" a logic circuit, it must be initialized.
At the initial state, each input and output pin of every gate in the circuit must be initialized to a certain value in such a way that for each link, its endpoints have the same value. As soon as the circuit is started:</p>

<ul>
<li>each gate instantaneously computes its output value. If the output value is changed, it is sent through all the output links of the gate.</li>
</ul>

<p>A logic circuit <em>halts</em> if, for each possible execution, (i) for each link its endpoints have the same value and (ii) for each gate, its output value is the correct output w.r.t. the current gate inputs. A logic circuit <em>oscillates</em> if, for each possible execution, it does not halt.
E.g., a NOT gate, whose pins are each other connected, oscillates since it never halts for each possible execution.</p>

<p>Problem. Given a Linear Bounded Automata $L$ (as defined <a href="http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/lba.pdf" rel="nofollow">here</a>, page 6), is it possible to construct in polynomial time (w.r.t. the size of $L$) a logic circuit $C$ that simulates $L$ in the following way: if $L$ halts, then $C$  halts and if $L$ does not halt, then $C$ oscillates.</p>

<p>I think that I solved this problem with a long construction with a positive answer.
It seems that this is a problem that must have been studied in the past, but I cannot find any reference in the literature. I really would like to have a reference that answers this question. Can anyone help me?</p>

<p>Observe that, the problem is not trivial. In fact, as <a href="http://alexandria.tue.nl/extra1/wskrap/publichtml/8930516.pdf" rel="nofollow">proved</a> by Brzozowski and Ebergen, if $d_{max}$ is allowed to be infinite, it is not possible to build any interesting memory logic structures (e.g., flip-flops, muller c-element, linear bounded automata,$\dots$).</p>

CC BY-SA 3.0
2013-05-08T18:22:00.610Z
To be pedantic, you should say: given a deterministic linear bounded automata is it possible to construct a logic circuit that simulates it ....? (or alternatively you can allow an infinite logic circuit with some initial configuration)
Marzio De Biasi
CC BY-SA 3.0
2013-05-08T23:18:50.430Z
another question: what is the role of the delay range? Isn't enough to assign to every link a fixed delay $d \geq 0$? Furthermore are "signal splits" allowed (a gate with one input and two outputs)? What happens if two outputs are linked together (if not forbidden) and two opposite 0/1 signals are "sent" on the link from the two endpoints?
Marzio De Biasi
CC BY-SA 3.0
2013-05-09T05:31:51.810Z
I feel that delay ranges are a more realistic assumption than fixed delays. Every time a signal is sent, it never takes exactly the same time to travel from its two endpoints. It also models the fact that each gate never takes exactly the same time to process a signal. Anyway, I would be also very interested in finding a reference in the literature that solves the fixed delay case. As for "signal split", it is possible that a gate have more than one output, but it is not possible to connect two output pins each other.
Marco
CC BY-SA 3.0
2013-05-09T10:58:38.540Z
One consequence of the delay range is that you have nondeterminism. Then what exactly do you mean by "the circuit halts"? Should this hold for all possible executions, or is just one enough?
Klaus Draeger
CC BY-SA 3.0
2013-05-09T14:12:28.777Z
@Marco: ok, thanks. I think that with your model (with fixed link delays) you can easily build a standard "computer": simulate a clock connecting the output of a NOT to its input and placing an AND in the middle to stop the clock when the computation ends), simulate flip-flops and memory, simulate CPU, ALU ... Let me know if you need further details.
Marzio De Biasi
CC BY-SA 3.0
2013-05-09T16:22:17.260Z
@Klaus: I mean all possible executions. If the LBA halts, the circuit also halts for every possible execution. If the LBA does not halts, the circuit also does not halts for every possible execution. Thank you for pointing this out.
Marco
CC BY-SA 3.0
2013-05-09T16:23:01.450Z
@Marzio: I would be very interested in finding a reference to a scientific paper where this problem is studied in these two delay models, especially in the min-max model. I feel that someone must have built a Turing Machine with logic gates assuming some delay constraints. I cannot find any scientific work that do this. Thanks.
Marco
CC BY-SA 3.0
2013-05-09T16:40:00.070Z
@Marco: as commented by Klaus in the min-max model you can have nondeterminism, but since PSPACE = NPSPACE, perhaps the difference is not too interesting/studied. About references, did you see: 1) "[Quasi-delay-insensitive circuits are Turing-complete](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.3632&rep=rep1&type=pdf)", 2) "Computing with BGP: from Routing Configurations to Turing Machines" and 3) [E.Fredkin and T.Toffoli model with delayed unit wires and Fredkin gates](http://www.cs.princeton.edu/courses/archive/fall06/cos576/papers/fredkin_toffoli82.pdf)
Marzio De Biasi
CC BY-SA 3.0
2013-05-09T16:42:31.953Z
... the models are different but they share the idea of combining some logic gates + delay to simulate a TM.
Marzio De Biasi
CC BY-SA 3.0
2013-05-10T08:15:53.977Z
@MarzioDeBiasi: Thanks for these references. In the first one, I am not sure if the idea of isochronic forks map to min-max delays. Isochronic fork means that some wires have exactly the same delay. This assumption cannot be made in the min-max model. In the third reference, the model is the exact-delays and it does not hold in the min-max model. 
As for PSPACE=NPSPACE, observe that, as proved [here](http://alexandria.tue.nl/extra1/wskrap/publichtml/8930516.pdf), if $d_{max}$ is allowed to be infinite, hence there is non-determinism, you can build no logic circuit with memory, hence LBA.
Marco
<cc.complexity-theory><circuit-complexity><turing-machines>
Is it possible to simulate a Linear Bounded Automata with logic circuits where links have min-max bounded delays? I need a reference in the literature
Marco
# Is it possible to simulate a Linear Bounded Automata with logic circuits where links have min-max bounded delays? I need a reference in the literature

(Asked by: username_0 on 2013-05-08)

Consider the following building blocks, which can be used to construct a logic circuit:

* basic logic gates {OR, AND, NOT} which have $n$ input and $m$ output pins, with $n,m\ge 1$.
* generators of stable values {0,1}.
* links, which can be used to join each other logic gates or generators.

Signal traversing a link have a propagation delay between a minimum $d\_{min}$ and a maximum finite value $d\_{max}$, with $0

In order to "execute" a logic circuit, it must be initialized.
At the initial state, each input and output pin of every gate in the circuit must be initialized to a certain value in such a way that for each link, its endpoints have the same value. As soon as the circuit is started:

* each gate instantaneously computes its output value. If the output value is changed, it is sent through all the output links of the gate.

A logic circuit *halts* if, for each possible execution, (i) for each link its endpoints have the same value and (ii) for each gate, its output value is the correct output w.r.t. the current gate inputs. A logic circuit *oscillates* if, for each possible execution, it does not halt.
E.g., a NOT gate, whose pins are each other connected, oscillates since it never halts for each possible execution.

Problem. Given a Linear Bounded Automata $L$ (as defined [here](http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/lba.pdf), page 6), is it possible to construct in polynomial time (w.r.t. the size of $L$) a logic circuit $C$ that simulates $L$ in the following way: if $L$ halts, then $C$ halts and if $L$ does not halt, then $C$ oscillates.

I think that I solved this problem with a long construction with a positive answer.
It seems that this is a problem that must have been studied in the past, but I cannot find any reference in the literature. I really would like to have a reference that answers this question. Can anyone help me?

Observe that, the problem is not trivial. In fact, as [proved](http://alexandria.tue.nl/extra1/wskrap/publichtml/8930516.pdf) by Brzozowski and Ebergen, if $d\_{max}$ is allowed to be infinite, it is not possible to build any interesting memory logic structures (e.g., flip-flops, muller c-element, linear bounded automata,$\dots$).

**Tags:** cc.complexity-theory, circuit-complexity, turing-machines

> **Comments:**
> **username_1**: To be pedantic, you should say: given a deterministic linear bounded automata is it possible to construct a logic circuit that simulates it ....? (or alternatively you can allow an infinite logic circuit with some initial configuration)  
> **username_1**: another question: what is the role of the delay range? Isn't enough to assign to every link a fixed delay $d \geq 0$? Furthermore are "signal splits" allowed (a gate with one input and two outputs)? What happens if two outputs are linked together (if not forbidden) and two opposite 0/1 signals are "sent" on the link from the two endpoints?  
> **username_0**: I feel that delay ranges are a more realistic assumption than fixed delays. Every time a signal is sent, it never takes exactly the same time to travel from its two endpoints. It also models the fact that each gate never takes exactly the same time to process a signal. Anyway, I would be also very interested in finding a reference in the literature that solves the fixed delay case. As for "signal split", it is possible that a gate have more than one output, but it is not possible to connect two output pins each other.  
> **username_2**: One consequence of the delay range is that you have nondeterminism. Then what exactly do you mean by "the circuit halts"? Should this hold for all possible executions, or is just one enough?  
> **username_1**: @username_0: ok, thanks. I think that with your model (with fixed link delays) you can easily build a standard "computer": simulate a clock connecting the output of a NOT to its input and placing an AND in the middle to stop the clock when the computation ends), simulate flip-flops and memory, simulate CPU, ALU ... Let me know if you need further details.  
> **username_0**: @Klaus: I mean all possible executions. If the LBA halts, the circuit also halts for every possible execution. If the LBA does not halts, the circuit also does not halts for every possible execution. Thank you for pointing this out.  
> **username_0**: @Marzio: I would be very interested in finding a reference to a scientific paper where this problem is studied in these two delay models, especially in the min-max model. I feel that someone must have built a Turing Machine with logic gates assuming some delay constraints. I cannot find any scientific work that do this. Thanks.  
> **username_1**: @username_0: as commented by Klaus in the min-max model you can have nondeterminism, but since PSPACE = NPSPACE, perhaps the difference is not too interesting/studied. About references, did you see: 1) "[Quasi-delay-insensitive circuits are Turing-complete](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.3632&rep=rep1&type=pdf)", 2) "Computing with BGP: from Routing Configurations to Turing Machines" and 3) [E.Fredkin and T.Toffoli model with delayed unit wires and Fredkin gates](http://www.cs.princeton.edu/courses/archive/fall06/cos576/papers/fredkin_toffoli82.pdf)  
> **username_1**: ... the models are different but they share the idea of combining some logic gates + delay to simulate a TM.  
> **username_0**: @MarzioDeBiasi: Thanks for these references. In the first one, I am not sure if the idea of isochronic forks map to min-max delays. Isochronic fork means that some wires have exactly the same delay. This assumption cannot be made in the min-max model. In the third reference, the model is the exact-delays and it does not hold in the min-max model.  As for PSPACE=NPSPACE, observe that, as proved [here](http://alexandria.tue.nl/extra1/wskrap/publichtml/8930516.pdf), if $d_{max}$ is allowed to be infinite, hence there is non-determinism, you can build no logic circuit with memory, hence LBA.  

---

## 0 answers

