Probabilistic Shoenfield Machines
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908343348494336 |
|---|---|
| author | Bujok, Maksymilian Mata, Adam |
| author_facet | Bujok, Maksymilian Mata, Adam |
| contents | The article provides the theoretical framework of Probabilistic Shoenfield Machines (PSMs), an extension of the classical Shoenfield Machine that models randomness in the computation process. PSMs are introduced in contexts where deterministic computation is insufficient, such as randomized algorithms. By allowing transitions to multiple possible states with certain probabilities, PSMs can solve problems and make decisions based on probabilistic outcomes, thus expanding the variety of possible computations. We provide an overview of PSMs, detailing their formal definitions, the computation mechanism, and their equivalence with Non-deterministic Shoenfield Machines (NSMs) |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05777 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Probabilistic Shoenfield Machines Bujok, Maksymilian Mata, Adam Symbolic Computation Logic in Computer Science F.1.1, F.1.2, F.2.0 F.4.1 The article provides the theoretical framework of Probabilistic Shoenfield Machines (PSMs), an extension of the classical Shoenfield Machine that models randomness in the computation process. PSMs are introduced in contexts where deterministic computation is insufficient, such as randomized algorithms. By allowing transitions to multiple possible states with certain probabilities, PSMs can solve problems and make decisions based on probabilistic outcomes, thus expanding the variety of possible computations. We provide an overview of PSMs, detailing their formal definitions, the computation mechanism, and their equivalence with Non-deterministic Shoenfield Machines (NSMs) |
| title | Probabilistic Shoenfield Machines |
| topic | Symbolic Computation Logic in Computer Science F.1.1, F.1.2, F.2.0 F.4.1 |
| url | https://arxiv.org/abs/2407.05777 |