The stochastic geometric machine model

Abstract

This paper introduces the stochastic version of the Geometric Machine Model for the modelling of sequential, alternative, parallel (synchronous) and nondeterministic computations with stochastic numbers stored in a (possibly infinite) shared memory. The programming language L(D! 1), induced by the Coherence Space of Processes D! 1, can be applied to sequential and parallel products in order to provide recursive definitions for such processes, together with a domain-theoretic semantics of the Stochastic Arithmetic. We analyze both the spacial (ordinal) recursion, related to spacial modelling of the stochastic memory, and the temporal (structural) recursion, given by the inclusion relation modelling partial objects in the ordered structure of process

Apresenta-se a versão estocástica da Máquina Geométrica, capaz de interpretar computações sequenciais, paralelas (síncronas) e não determinísticas,considerando uma memória compartilhada (posssivelmente infinita). A linguagem de programação L(D →∞), induzida pelo espaço coerente de processos D →∞, pode ser aplicada sobre produtos sequenciais e paralelos, para prover definições recursivas de processos estocásticos e uma semântica denotacional para a Aritmética Estocástica. São analisadas a recursão espacial (ou ordinal) relacionada com a modelagem espacial da memória, e a recursão temporal (ou estrutural) obtida pela relação de inclusão modelando objetos parciais na estrutura do modelo. O estudo da complexidade de algumas operações e algoritmos aritméticos estocásticos mostrou a adequação da representação escolhida para os números estocásticos, assim como as vantagens da estruturação paralela de programas de aritmética estocástica.