2
$\begingroup$

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<d_{min}< 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.

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, 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 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$).

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Marzio De Biasi May 8 '13 at 18:22
  • $\begingroup$ 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? $\endgroup$ – Marzio De Biasi May 8 '13 at 23:18
  • $\begingroup$ 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. $\endgroup$ – Marco May 9 '13 at 5:31
  • 1
    $\begingroup$ @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", 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 $\endgroup$ – Marzio De Biasi May 9 '13 at 16:40
  • 1
    $\begingroup$ ... the models are different but they share the idea of combining some logic gates + delay to simulate a TM. $\endgroup$ – Marzio De Biasi May 9 '13 at 16:42

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.