| In [1] a probabilistic solution to the Infinite Merchant's Problem, an undecidable problem equivalent to the Halting Problem, was proposed. The solution uses a real Hilbert space and is based on the estimation of the exponential growth of an unbounded semigroup. In [2] was offered an alternative solution in terms of scattering processes on quantum dots. The authors reduced the problem to a special scattering problem and testify the "halting phenomenon" based on the quantum measurement of results of scattering with random input data. The a-posteriori probability of halting, subject to the negative results of multiple independent tests, was estimated. The possibility of location the number of the bag with false coins in finite-dimensional case was noticed in [1] and proved in [2]. The aim of this paper is to offer a solution of the latter problem in the infinite case. [1] C.S. Calude, B.S. Pavlov. Coins, quantum measurements, and Turing's barrier, Quantum Information Processing, 1, 1--2 (2002), 107--127. [2] V.A. Adamyan, C.S. Calude, B.S. Pavlov, A quantum scattering approach to undecidable problem. In: Quantum information and complexity, Proceedings of the Meijo Winter School 2003, Meijo University, Nagoya, Japan, 6 - 10 January 2003, edited by T Hida, K Saitô (Meijo University, Japan) and Si Si (Aichi Prefectural University, Japan). |
Keywords
Merchant problem, average on Weiner measure, Hilbert space
Math Review Classification
Primary 81P68
; Secondary 68Q05
Last Updated
15/12/2004
Length
6
Availability
This article is available in: