Probabilistic Solutions to Merchant Problems: Locating of the False Stack

Vladimir L. Oleinik and Boris S. Pavlov

Abstract

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: