Three More Models

Post's Correspondence Problem (PCP)

Origin: Emil Post, 1946 ("A Variant of a Recursively Unsolvable Problem").
Instance: A finite set of pairs $$ I = {(g_1, g_1'), \dots, (g_k, g_k')} $$ where $k \ge 1$ and $g_i, g_i' \in \Sigma^+$ (non-empty strings over some alphabet $\Sigma$).
Question: Does there exist a non-empty sequence of indices $i_1, \dots, i_n$ (with $n \ge 1$) such that $$ g_{i_1} g_{i_2} \cdots g_{i_n} = g'{i_1} g'{i_2} \cdots g'_{i_n} \;? $$
Theorem (Post): The set of solvable PCP instances is recursively enumerable but not recursive (i.e., PCP is undecidable).
Significance: PCP is a classic undecidable problem, often used to prove undecidability of other problems via reductions.

Interaction Nets

Proposed by: Yves Lafont (1990).
Concept: A graph-rewriting model of computation based on agents and edges.
Components:
- Agents: nodes with a principal port and auxiliary ports (analogous to gates).
- Edges: connect ports of agents (analogous to wires).
- Interaction rules: specify how two agents connected via their principal ports rewrite (merge, split, etc.).
Analogy: Electric circuits – agents as gates, edges as wires.
Computation: Starts from an initial net; repeatedly apply interaction rules until no rule applies (normal form).
Properties:
- Strong confluence (if confluent) and good parallelism properties.
- Can simulate $\lambda$-calculus efficiently; used as a foundation for optimal reduction (e.g., Lamping's algorithm).
Tools: Lambdascope (van Oostrom, Rochel) – an interactive animation tool for interaction nets and optimal reduction.

Proposed by: John Horton Conway (1987).
Concept: A programming language based on a list of fractions and a single integer state.
Program: A finite list of positive rational numbers $f_1, f_2, \dots, f_n$.
Execution: Starting with a positive integer $N$, repeatedly find the first fraction $f_i$ such that $N \cdot f_i$ is an integer; set $N := N \cdot f_i$ and repeat. If no such fraction exists, halt.
Computational power: Fractran is Turing-complete (Conway showed it can simulate register machines).
Remark: Extremely simple syntax but very powerful; can encode arithmetic operations and control flow.

A model $\mathcal{M}_1$ can be simulated by $\mathcal{M}_2$ via an encoding $\rho$ if for every function $f_1$ computable in $\mathcal{M}_1$, there exists $f_2$ computable in $\mathcal{M}_2$ such that: $$ f_1 = \rho^{-1} \circ f_2 \circ \rho $$ (with suitable domains and codomains).
This defines a simulation pre-order: $\mathcal{M}_1 \lessdot_{\rho} \mathcal{M}_2$.

Traditionally, encodings are assumed to be computable/effective.
Boker and Dershowitz (2006) proposed using injective or bijective encodings to avoid circularity (since computability is what we are trying to compare).
Injective: $\rho$ is one-to-one.
Bijective: $\rho$ is a bijection.

A decision model has outputs in $\{0,1\}$.
Theorem (Endrullis/Grabmayer/Hendriks): For any countable decision model $\mathcal{M}$ over alphabet $\Sigma$, we have $$ \mathcal{M} \lessdot_{\text{injective}} \text{DFA}(\Gamma) \quad \text{and} \quad \mathcal{M} \lessdot_{\text{bijective}} \text{DFA}(\Gamma) $$ for any alphabet $\Gamma$ containing $\{0,1\}$.
Consequence: Even Turing machine deciders can be bijectively encoded into finite automata (which are strictly weaker). This shows that injective/bijective encodings are too weak to capture intuitive notions of simulation power, because they allow uncomputable encodings.

Given two machines $M_1 \in \mathcal{M}_1$ and $M_2 \in \mathcal{M}_2$, they simulate each other with respect to computable encoding $enc: I_{M_1} \to I_{M_2}$ and decoding $dec: O_{M_2} \to O_{M_1}$ if the following diagram commutes (in the sense of reachability and output): $$ \alpha_{M_2}(enc(i)) \vdash_{M_2}^ c \in EC_{M_2} \iff \alpha_{M_1}(i) \vdash_{M_1}^ c' \in EC_{M_1} $$ and $\omega_{M_2}(c) = dec(\omega_{M_1}(c'))$ (with appropriate adjustments). This defines a Galois connection between computation relations.

$\mathcal{M}_1 \le \mathcal{M}_2$ (computational power of $\mathcal{M}_1$ is subsumed by $\mathcal{M}_2$) if there exist computable encoding $enc: I_{\mathcal{M}_1} \to I_{\mathcal{M}_2}$ and decoding $dec: O_{\mathcal{M}_2} \to O_{\mathcal{M}_1}$ such that for every $M_1 \in \mathcal{M}_1$ there exists $M_2 \in \mathcal{M}_2$ such that $M_1$ and $M_2$ simulate each other w.r.t. $(enc, dec)$.
Equivalence: $\mathcal{M}_1 \sim \mathcal{M}_2$ if both $\mathcal{M}_1 \le \mathcal{M}_2$ and $\mathcal{M}_2 \le \mathcal{M}_1$.

Let $\mathcal{TM}(\Sigma)$ be the class of Turing machines with input alphabet $\Sigma$.
A model $\mathcal{M}$ is Turing-complete if $\mathcal{TM}(\Sigma) \le \mathcal{M}$ for some non-empty $\Sigma$.
It is Turing-equivalent if $\mathcal{M} \sim \mathcal{TM}(\Sigma)$ for some non-empty $\Sigma$.

All classical models (TMs, $\lambda$-calculus, recursive functions, Post machines, etc.) are Turing-equivalent.
The definition allows precise comparisons and avoids anomalies caused by arbitrary encodings.

PCP: Undecidable string matching problem; r.e. but not recursive.
Interaction Nets: Graph-rewriting model, confluent, supports optimal reduction.
Fractran: Minimal arithmetic language based on fractions; Turing-complete.
Comparing MoCs: Requires well-defined encodings and simulations; injective/bijective encodings can lead to counterintuitive results for decision models.
Formal framework: Abstract MoC definition and simulation relations provide a rigorous basis for comparing computational power across different formalisms.