The Experts below are selected from a list of 240 Experts worldwide ranked by ideXlab platform
Robert S Lubarsky - One of the best experts on this subject based on the ideXlab platform.
-
An introduction to feedback Turing Computability
Journal of Logic and Computation, 2020Co-Authors: Nathanael L Ackerman, Cameron E Freer, Robert S LubarskyAbstract:Abstract Feedback Computability is computation with an oracle that contains the correct convergence/divergence information for all computations calling that same oracle. Here we study feedback Turing Computability, as well as feedback for some smaller classes of computation. We also examine some versions of parallelization of these notions.
-
parallel feedback Turing Computability
Foundations of Computer Science, 2016Co-Authors: Robert S LubarskyAbstract:In contrast to most kinds of Computability studied in mathematical logic, feedback Computability has a non-degenerate notion of parallelism. Here we study parallelism for the most basic kind of feedback, namely that of Turing Computability. We investigate several different possible definitions of parallelism in this context, with an eye toward specifying what is so computable. For the deterministic notions of parallelism identified we are successful in this analysis; for the non-deterministic notion, not completely.
-
LFCS - Parallel Feedback Turing Computability
Logical Foundations of Computer Science, 2015Co-Authors: Robert S LubarskyAbstract:In contrast to most kinds of Computability studied in mathematical logic, feedback Computability has a non-degenerate notion of parallelism. Here we study parallelism for the most basic kind of feedback, namely that of Turing Computability. We investigate several different possible definitions of parallelism in this context, with an eye toward specifying what is so computable. For the deterministic notions of parallelism identified we are successful in this analysis; for the non-deterministic notion, not completely.
-
feedback Turing Computability and Turing Computability as feedback
Logic in Computer Science, 2015Co-Authors: Nathanael L Ackerman, Cameron E Freer, Robert S LubarskyAbstract:The notion of a feedback query is a natural generalization of choosing for an oracle the set of indices of halting computations. Notice that, in that setting, the computations being run are different from the computations in the oracle: the former can query an oracle, whereas the latter cannot. A feedback computation is one that can query an oracle, which itself contains the halting information about all feedback computations. Although this is self-referential, sense can be made of at least some such computations. This threatens, though, to obliterate the distinction between con- and divergence: before running a computation, a machine can ask the oracle whether that computation converges, and then run it if and only if the oracle says "yes." This would quickly lead to a diagonalization paradox, except that a new distinction is introduced, this time between freezing and non-freezing computations. The freezing computations are even more extreme than the divergent ones, in that they prevent the dovetailing on all computations into a single run. In this paper, we study feedback around Turing Computability. In one direction, we examine feedback Turing machines, and show that they provide exactly hyper arithmetic Computability. In the other direction, Turing Computability is itself feedback primitive recursion (at least, one version thereof). We also examine parallel feedback. Several different notions of parallelism in this context are identified. We show that parallel feedback Turing machines are strictly stronger than sequential feedback TMs, while in contrast parallel feedback p.r. Is the same as sequential feedback p.r.
-
LICS - Feedback Turing Computability, and Turing Computability as Feedback
2015 30th Annual ACM IEEE Symposium on Logic in Computer Science, 2015Co-Authors: Nathanael L Ackerman, Cameron E Freer, Robert S LubarskyAbstract:The notion of a feedback query is a natural generalization of choosing for an oracle the set of indices of halting computations. Notice that, in that setting, the computations being run are different from the computations in the oracle: the former can query an oracle, whereas the latter cannot. A feedback computation is one that can query an oracle, which itself contains the halting information about all feedback computations. Although this is self-referential, sense can be made of at least some such computations. This threatens, though, to obliterate the distinction between con- and divergence: before running a computation, a machine can ask the oracle whether that computation converges, and then run it if and only if the oracle says "yes." This would quickly lead to a diagonalization paradox, except that a new distinction is introduced, this time between freezing and non-freezing computations. The freezing computations are even more extreme than the divergent ones, in that they prevent the dovetailing on all computations into a single run. In this paper, we study feedback around Turing Computability. In one direction, we examine feedback Turing machines, and show that they provide exactly hyper arithmetic Computability. In the other direction, Turing Computability is itself feedback primitive recursion (at least, one version thereof). We also examine parallel feedback. Several different notions of parallelism in this context are identified. We show that parallel feedback Turing machines are strictly stronger than sequential feedback TMs, while in contrast parallel feedback p.r. Is the same as sequential feedback p.r.
Holger Boche - One of the best experts on this subject based on the ideXlab platform.
-
identification capacity of channels with feedback discontinuity behavior super activation and Turing Computability
IEEE Transactions on Information Theory, 2020Co-Authors: Holger Boche, Rafael F Schaefer, Vincent H PoorAbstract:The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not, and the identification-feedback (IDF) capacity of channels with feedback is studied. The IDF capacity is shown to be discontinuous and super-additive for both deterministic and randomized encoding. For the deterministic IDF capacity the phenomenon of super-activation occurs, which is the strongest form of super-additivity. This is the first time that super-activation is observed for discrete memoryless channels. On the other hand, for the randomized IDF capacity, super-activation is not possible. Finally, the developed theory is studied from an algorithmic point of view by using the framework of Turing Computability. The problem of computing the IDF capacity on a Turing machine is connected to problems in pure mathematics and it is shown that if the IDF capacity would be Turing computable, it would provide solutions to other problems in mathematics including Goldbach’s conjecture and the Riemann Hypothesis. However, it is shown that the deterministic and randomized IDF capacities are not Banach-Mazur computable. This is the weakest form of Computability implying that the IDF capacity is not computable even for universal Turing machines. On the other hand, the identification capacity without feedback is Turing computable revealing the impact of the feedback: It transforms the identification capacity from being computable to non-computable.
-
Turing Computability of fourier transforms of bandlimited and discrete signals
IEEE Transactions on Signal Processing, 2020Co-Authors: Holger Boche, Ullrich J MonichAbstract:The Fourier transform is an important operation in signal processing. However, its exact computation on digital computers can be problematic. In this paper we consider the Computability of the Fourier transform and the discrete-time Fourier transform (DTFT). We construct a computable bandlimited absolutely integrable signal that has a continuous Fourier transform, which is, however, not Turing computable. Further, we also construct a computable sequence such that the DTFT is not Turing computable. Turing Computability models what is theoretically implementable on a digital computer. Hence, our result shows that the Fourier transform of certain signals cannot be computed on digital hardware of any kind, including CPUs, FPGAs, and DSPs. This also implies that there is no symmetry between the time and frequency domain with respect to Computability. Therefore, numerical approaches which employ the frequency domain representation of a signal (like calculating the convolution by performing a multiplication in the frequency domain) can be problematic. Interestingly, an idealized analog machine can compute the Fourier transform. However, it is unclear whether and how this theoretical superiority of the analog machine can be translated into practice. Further, we show that it is not possible to find an algorithm that can always decide for a given signal whether the Fourier transform is computable or not.
-
Investigations on the approximability and Computability of the Hilbert transform with applications
Applied and Computational Harmonic Analysis, 2020Co-Authors: Holger Boche, Volker PohlAbstract:Abstract It was recently shown that on a large class of important Banach spaces there exist no linear methods which are able to approximate the Hilbert transform from samples of the given function. This implies that there is no linear algorithm for calculating the Hilbert transform which can be implemented on a digital computer and which converges for all functions from the corresponding Banach spaces. The present paper develops a much more general framework which also includes non-linear approximation methods. All algorithms within this framework have only to satisfy an axiom which guarantees the Computability of the algorithm based on given samples of the function. The paper investigates whether there exists an algorithm within this general framework which converges to the Hilbert transform for all functions in these Banach spaces. It is shown that non-linear methods give actually no improvement over linear methods. Moreover, the paper discusses some consequences regarding the Turing Computability of the Hilbert transform and the existence of computational bases in Banach spaces.
-
Secure Communication and Identification Systems — Effective Performance Evaluation on Turing Machines
IEEE Transactions on Information Forensics and Security, 2020Co-Authors: Holger Boche, Rafael F Schaefer, H. Vincent PoorAbstract:Modern communication systems need to satisfy pre-specified requirements on spectral efficiency and security. Physical layer security is a concept that unifies both and connects them with entropic quantities. In this paper, a framework based on Turing machines is developed to address the question of deciding whether or not a communication system meets these requirements. It is known that the class of Turing solvable problems coincides with the class of algorithmically solvable problems so that this framework provides the theoretical basis for effective verification of such performance requirements. A key issue here is to decide whether or not the performance functions, i.e., capacities, of relevant communication scenarios, particularly those with secrecy requirements and active adversaries, are Turing computable. This is a necessary condition for the corresponding communication protocols to be effectively verifiable. Within this framework, it is then shown that for certain scenarios including the wiretap channel the corresponding capacities are Turing computable. Next, a general necessary condition on the performance function for Turing Computability is established. With this, it is shown that for certain scenarios, including the wiretap channel with an active jammer, the performance functions are not computable when deterministic codes are used. As a consequence, such performance functions are also not computable on all other computer architectures such as the von Neumann-architecture or the register machines.
-
Downsampling of Bounded Bandlimited Signals and the Bandlimited Interpolation: Analytic Properties and Computability
IEEE Transactions on Signal Processing, 2019Co-Authors: Holger Boche, Ullrich J MonichAbstract:Downsampling and the computation of the bandlimited interpolation of discrete-time signals are two important concepts in signal processing. In this paper we analyze the downsampling operation regarding its impact on the existence and Computability of the bounded bandlimited interpolation. We assume that the discrete-time signal is obtained by downsampling the samples of a bounded bandlimited signal that vanishes at infinity, and we study two problems. First, we investigate the existence of the bounded bandlimited interpolation for such discrete-time signals from a signal theoretic perspective and show that there exist signals for which the bounded bandlimited interpolation does not exist. Second, we analyze the algorithmic generation of the bounded bandlimited interpolation, using the concept of Turing Computability. Turing Computability models what is theoretically implementable on a digital computer. Interestingly, it turns out that even if the bounded bandlimited interpolation exists analytically, it is not always computable, which implies that there exists no algorithm on a digital computer that can always compute it. Computability is important in order that the approximation error be controlled. If a signal is not computable, we cannot ascertain whether the computed signal is sufficiently close to the true signal, i.e., we cannot verify every approximation accuracy.
Ullrich J Monich - One of the best experts on this subject based on the ideXlab platform.
-
Turing Computability of fourier transforms of bandlimited and discrete signals
IEEE Transactions on Signal Processing, 2020Co-Authors: Holger Boche, Ullrich J MonichAbstract:The Fourier transform is an important operation in signal processing. However, its exact computation on digital computers can be problematic. In this paper we consider the Computability of the Fourier transform and the discrete-time Fourier transform (DTFT). We construct a computable bandlimited absolutely integrable signal that has a continuous Fourier transform, which is, however, not Turing computable. Further, we also construct a computable sequence such that the DTFT is not Turing computable. Turing Computability models what is theoretically implementable on a digital computer. Hence, our result shows that the Fourier transform of certain signals cannot be computed on digital hardware of any kind, including CPUs, FPGAs, and DSPs. This also implies that there is no symmetry between the time and frequency domain with respect to Computability. Therefore, numerical approaches which employ the frequency domain representation of a signal (like calculating the convolution by performing a multiplication in the frequency domain) can be problematic. Interestingly, an idealized analog machine can compute the Fourier transform. However, it is unclear whether and how this theoretical superiority of the analog machine can be translated into practice. Further, we show that it is not possible to find an algorithm that can always decide for a given signal whether the Fourier transform is computable or not.
-
Downsampling of Bounded Bandlimited Signals and the Bandlimited Interpolation: Analytic Properties and Computability
IEEE Transactions on Signal Processing, 2019Co-Authors: Holger Boche, Ullrich J MonichAbstract:Downsampling and the computation of the bandlimited interpolation of discrete-time signals are two important concepts in signal processing. In this paper we analyze the downsampling operation regarding its impact on the existence and Computability of the bounded bandlimited interpolation. We assume that the discrete-time signal is obtained by downsampling the samples of a bounded bandlimited signal that vanishes at infinity, and we study two problems. First, we investigate the existence of the bounded bandlimited interpolation for such discrete-time signals from a signal theoretic perspective and show that there exist signals for which the bounded bandlimited interpolation does not exist. Second, we analyze the algorithmic generation of the bounded bandlimited interpolation, using the concept of Turing Computability. Turing Computability models what is theoretically implementable on a digital computer. Interestingly, it turns out that even if the bounded bandlimited interpolation exists analytically, it is not always computable, which implies that there exists no algorithm on a digital computer that can always compute it. Computability is important in order that the approximation error be controlled. If a signal is not computable, we cannot ascertain whether the computed signal is sufficiently close to the true signal, i.e., we cannot verify every approximation accuracy.
-
Turing Computability of the fourier transform of bandlimited functions
International Symposium on Information Theory, 2019Co-Authors: Holger Boche, Ullrich J MonichAbstract:The Fourier transform is an essential operation in information sciences. However, it can rarely be calculated in closed form. Nowadays, digital computers are used to compute the Fourier transform. In this paper we study the Computability of the Fourier transform. We construct an absolutely integrable bandlimited function that is computable as an element of L2, such that its Fourier transform is not Turing computable. This means the Fourier transform is not computable on a digital computer, because we have no way of effectively controlling the approximation error. This result has consequences for algorithms that use the Fourier transform of bandlimited function, e.g., the computation of the convolution via a multiplication in the Fourier domain.
Ning Zhong - One of the best experts on this subject based on the ideXlab platform.
-
Computing Schrödinger propagators on Type-2 Turing machines
Journal of Complexity, 2006Co-Authors: Klaus Weihrauch, Ning ZhongAbstract:AbstractWe study Turing Computability of the solution operators of the initial-value problems for the linear Schrödinger equation ut=iΔu+φ and the nonlinear Schrödinger equation of the form iut=-Δu+mu+|u|2u. We prove that the solution operators are computable if the initial data are Sobolev functions but noncomputable in the linear case if the initial data are Lp-functions and p≠2. The computations are performed on Type-2 Turing machines
-
Turing Computability of a nonlinear schrodinger propagator
Computing and Combinatorics Conference, 2001Co-Authors: Klaus Weihrauch, Ning ZhongAbstract:We study Turing Computability of the nonlinear solution operator S of the Cauchy problem for the Schrodinger equation of the form idu/dt = -d2u/dx2+mu+ |u|2u in R. We prove that S is a computable operator from H1(R) to C(R;H1(R)) with respect to the canonical representations.
-
COCOON - Turing Computability of a Nonlinear Schrödinger Propagator
Lecture Notes in Computer Science, 2001Co-Authors: Klaus Weihrauch, Ning ZhongAbstract:We study Turing Computability of the nonlinear solution operator S of the Cauchy problem for the Schrodinger equation of the form idu/dt = -d2u/dx2+mu+ |u|2u in R. We prove that S is a computable operator from H1(R) to C(R;H1(R)) with respect to the canonical representations.
Klaus Weihrauch - One of the best experts on this subject based on the ideXlab platform.
-
Computing Schrödinger propagators on Type-2 Turing machines
Journal of Complexity, 2006Co-Authors: Klaus Weihrauch, Ning ZhongAbstract:AbstractWe study Turing Computability of the solution operators of the initial-value problems for the linear Schrödinger equation ut=iΔu+φ and the nonlinear Schrödinger equation of the form iut=-Δu+mu+|u|2u. We prove that the solution operators are computable if the initial data are Sobolev functions but noncomputable in the linear case if the initial data are Lp-functions and p≠2. The computations are performed on Type-2 Turing machines
-
Turing Computability of a nonlinear schrodinger propagator
Computing and Combinatorics Conference, 2001Co-Authors: Klaus Weihrauch, Ning ZhongAbstract:We study Turing Computability of the nonlinear solution operator S of the Cauchy problem for the Schrodinger equation of the form idu/dt = -d2u/dx2+mu+ |u|2u in R. We prove that S is a computable operator from H1(R) to C(R;H1(R)) with respect to the canonical representations.
-
COCOON - Turing Computability of a Nonlinear Schrödinger Propagator
Lecture Notes in Computer Science, 2001Co-Authors: Klaus Weihrauch, Ning ZhongAbstract:We study Turing Computability of the nonlinear solution operator S of the Cauchy problem for the Schrodinger equation of the form idu/dt = -d2u/dx2+mu+ |u|2u in R. We prove that S is a computable operator from H1(R) to C(R;H1(R)) with respect to the canonical representations.
