Created
October 15, 2017 05:26
-
-
Save dotcypress/481dc13b4785e039fa15d951cb8441db to your computer and use it in GitHub Desktop.
Unlimited Register Machine
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//! Unlimited Register Machine | |
//! https://proofwiki.org/wiki/Definition:Unlimited_Register_Machine | |
use std::collections::HashMap; | |
type Address = usize; | |
type State = HashMap<Address, usize>; | |
#[derive(Debug)] | |
enum Op { | |
Zero(Address), | |
Suc(Address), | |
Transfer(Address, Address), | |
Jump(Address, Address, Address), | |
} | |
#[derive(Debug)] | |
struct URM { | |
cursor: Address, | |
program: Vec<Op>, | |
state: State, | |
} | |
impl URM { | |
fn execute(program: Vec<Op>, state: State) -> State { | |
let mut machine = URM { | |
program, | |
state, | |
cursor: 0, | |
}; | |
loop { | |
if machine.cursor >= machine.program.len() { | |
break; | |
} | |
match machine.program[machine.cursor] { | |
Op::Zero(address) => { | |
machine.state.insert(address, 0); | |
} | |
Op::Suc(address) => { | |
let register_value = machine.state.entry(address).or_insert(0); | |
*register_value += 1; | |
} | |
Op::Transfer(from, to) => { | |
let register_value = *machine.state.entry(from).or_insert(0); | |
machine.state.insert(to, register_value); | |
} | |
Op::Jump(lhr, rhs, address) => { | |
let left_value = *machine.state.entry(lhr).or_insert(0); | |
let right_value = *machine.state.entry(rhs).or_insert(0); | |
if left_value == right_value { | |
machine.cursor = address; | |
continue; | |
} | |
} | |
} | |
machine.cursor += 1; | |
} | |
machine.state | |
} | |
} | |
fn main() { | |
let state = vec![(0, 5), (1, 7)].into_iter().collect(); | |
let program = vec![ | |
Op::Jump(1, 2, 4), | |
Op::Suc(0), | |
Op::Suc(2), | |
Op::Jump(1, 1, 0), | |
Op::Transfer(0, 100), | |
Op::Zero(0), | |
Op::Zero(1), | |
Op::Zero(2), | |
]; | |
let final_state = URM::execute(program, state); | |
println!("{:?}", final_state); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment