-
-
Save Iijil1/d325da33be74a86ac2399c161a57166a to your computer and use it in GitHub Desktop.
Compile tms to 2 symbol tms encoding the symbols of the original tm with length 2
This file contains hidden or 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
| <?php | |
| #erdos: | |
| # php compiler.php 2RB2RB1RA3RA_0LC1RB3RB2RA_0LE1LC2LC3LD_0RB1LD2LD3LD_1RD2RD3RD1RZ | |
| #ack14: | |
| # php compiler.php 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC | |
| #ack11: | |
| # php compiler.php 1RB1RZ1LA2RB_1RC3RC1LA2LB_2LB2RC1LC3RB | |
| #bigfoot: | |
| # php compiler.php 1RB2RA1LC_2LC1RB2RB_1RZ2LA1LA | |
| # --- transitions in the input are treated as "undefined", meaning the compiled TM is allowed to do anything when it encounters this transition. | |
| # For many champions or cryptids that are given with a --- transition it is important that it halts when the tm tries to use this transition. | |
| # To specify that use 1RZ instead of ---. | |
| const MAXSTEPS = 10000; //for TNF conversion | |
| function done($text) | |
| { | |
| echo("$text\n"); die; | |
| } | |
| function output($tm) | |
| { | |
| echo(tmToString(convert($tm))."\n"); | |
| } | |
| function outputMeta($stateMap, $leftEncoding, $rightEncoding) | |
| { | |
| echo("left side symbol encoding: ".encodingToString($leftEncoding)."\n"); | |
| echo("right side symbol encoding: ".encodingToString($rightEncoding)."\n"); | |
| echo("state encoding: ".stateMapToString($stateMap)."\n"); | |
| } | |
| function encodingToString($encoding) | |
| { | |
| $symbols = []; | |
| foreach ($encoding as $symbol => $macroSymbol) { | |
| $symbols[] = implode("->",[$symbol,implode("",$macroSymbol)]); | |
| } | |
| return implode(", ", $symbols); | |
| } | |
| function stateMapToString($stateMap) | |
| { | |
| $states = []; | |
| foreach ($stateMap as $state => $macroState) { | |
| $states[] = implode("->",[$state,intToState($macroState)]); | |
| } | |
| return implode(", ", $states); | |
| } | |
| function convert($tm) | |
| { | |
| $startState = $tm["start"]; | |
| unset($tm["states"], $tm["symbols"], $tm["start"]); | |
| $stateMap = [0 => $startState]; | |
| $symbolMap = [0 => 0]; | |
| $config = [$startState, 0, [0 => 0]]; | |
| for ($i = 0; $i < MAXSTEPS; $i++) { | |
| $config = stepTm($tm, $config); | |
| if ($config === "HALT") { | |
| break; | |
| } | |
| [$state, $pos, $tape] = $config; | |
| if (!isset($tape[$pos])) { | |
| $tape[$pos] = 0; | |
| $config[2][$pos] = 0; | |
| } | |
| if (!in_array($state, $stateMap)) { | |
| $stateMap[] = $state; | |
| } | |
| if (isset($tape[$pos-1]) && !in_array($tape[$pos-1], $symbolMap)) { | |
| $symbolMap[] = $tape[$pos-1]; | |
| } | |
| if (isset($tape[$pos+1]) && !in_array($tape[$pos+1], $symbolMap)) { | |
| $symbolMap[] = $tape[$pos+1]; | |
| } | |
| } | |
| $unseenStates = array_diff(array_keys($tm),$stateMap); | |
| if (count($unseenStates) > 0) { | |
| echo("unseen states: ". implode(", ", $unseenStates) ."\n"); | |
| } | |
| $dirMap = ["R" => "R", "L" => "L"]; | |
| if ($tm[0][0][1] === "L") { | |
| $dirMap = ["R" => "L", "L" => "R"]; | |
| } | |
| $rtm = array_map(function ($state) use ($tm, $symbolMap, $dirMap, $stateMap) { | |
| return array_map(function ($symbol) use ($tm, $symbolMap, $dirMap, $stateMap, $state) { | |
| if (!isset($tm[$state][$symbol])) { | |
| return "undef"; | |
| } | |
| $transition = $tm[$state][$symbol]; | |
| if ($transition === "halt") { | |
| return "halt"; | |
| } | |
| [$nSymbol, $ndir, $nState] = $transition; | |
| $rSymbol = array_search($nSymbol, $symbolMap); | |
| $rState = array_search($nState, $stateMap); | |
| $rDir = $dirMap[$ndir]; | |
| if ($rSymbol === false) { | |
| echo("required symbol $nSymbol was unseen\n"); | |
| } | |
| if ($rState === false) { | |
| return "halt"; | |
| } | |
| return [$rSymbol, $rDir, $rState]; | |
| }, $symbolMap); | |
| }, $stateMap); | |
| return $rtm; | |
| } | |
| function stepTm($tm, $config) | |
| { | |
| [$state, $pos, $tape] = $config; | |
| $symbol = $tape[$pos]; | |
| if (!isset($tm[$state][$symbol])) { | |
| return "HALT"; | |
| } | |
| [$nextSymbol, $dir, $nextState] = $tm[$state][$symbol]; | |
| if (!isset($tm[$nextState])) { | |
| return [$nextState, $pos, $tape]; | |
| } | |
| $tape[$pos] = $nextSymbol; | |
| $state = $nextState; | |
| $pos = $pos + ["L" => -1, "R" => 1][$dir]; | |
| return [$state, $pos, $tape]; | |
| } | |
| function tmToString($tm) | |
| { | |
| unset($tm["states"],$tm["symbols"]); | |
| $maxState = 0; | |
| foreach ($tm as $state => $data) { | |
| if ($state > $maxState) { | |
| $maxState = $state; | |
| } | |
| } | |
| $states = []; | |
| for ($i = 0; $i <= $maxState; $i++) { | |
| $transitions = []; | |
| for ($j = 0; $j < 2; $j++) { | |
| if (!isset($tm[$i], $tm[$i][$j])) { | |
| $transitions[] = "---"; | |
| continue; | |
| } | |
| $trans = $tm[$i][$j]; | |
| if ($trans === "halt") { | |
| $transitions[] = "1RZ"; | |
| continue; | |
| } | |
| if ($trans === "undef") { | |
| $transitions[] = "---"; | |
| continue; | |
| } | |
| [$symbol, $dir, $state] = $tm[$i][$j]; | |
| $transitions[] = implode("", [$symbol, $dir, intToState($state)]); | |
| } | |
| $states[] = implode("", $transitions); | |
| } | |
| return implode("_", $states); | |
| } | |
| function intToState($o) | |
| { | |
| if (!preg_match("/^\d+$/", $o)) { | |
| return "[$o]"; | |
| } | |
| return chr(ord("A")+$o); | |
| } | |
| function readTm($tmString) | |
| { | |
| $stateStrings = explode("_", $tmString); | |
| if (count($stateStrings) == 0) { | |
| done("tm must have a state"); | |
| } | |
| $tm = [ | |
| "states" => count($stateStrings), | |
| "symbols" => strlen($stateStrings[0])/3, | |
| ]; | |
| foreach ($stateStrings as $offset => $stateString) { | |
| if (strlen($stateString) != $tm["symbols"]*3) { | |
| done("invalid std format stateString length"); | |
| } | |
| $curState = intToState($offset); | |
| foreach (str_split($stateString, 3) as $curSymbol => $tranString) { | |
| if ($tranString === "---") { | |
| continue; | |
| } | |
| $tm[$curState][$curSymbol] = str_split($tranString, 1); | |
| } | |
| } | |
| return $tm; | |
| } | |
| function compile($tm) | |
| { | |
| $done = false; | |
| $maxStates = 1; | |
| while (!$done) { | |
| echo("trying $maxStates states\n"); | |
| foreach (getRequiredStatesAndSymbols($tm) as [$requiredStates, $requiredLeftSymbols, $requiredRightSymbols]) { | |
| foreach (getEncodings($requiredLeftSymbols) as $leftEncoding) { | |
| foreach (getEncodings($requiredRightSymbols, $leftEncoding) as $rightEncoding) { | |
| $roleConditions = extractConditions($tm, $requiredStates, $leftEncoding, $rightEncoding); | |
| global $mode; | |
| if ($mode%2 == 1) { | |
| if (bruteforceCompile($maxStates, $roleConditions, $requiredStates, $leftEncoding, $rightEncoding)) { | |
| $done = true; | |
| }; | |
| } else { | |
| if (subTMCompile($tm, $maxStates, $roleConditions, $requiredStates, $leftEncoding, $rightEncoding)) { | |
| $done = true; | |
| }; | |
| } | |
| } | |
| } | |
| } | |
| $maxStates++; | |
| } | |
| } | |
| function getEncodings($requiredSymbols, $existingEncoding = [0 => [0,0]]) | |
| { | |
| if (count($requiredSymbols) > 4) { | |
| done("more than 4 symbols required"); | |
| } | |
| global $mode; | |
| if ((($mode / 2) % 2) === 1) { | |
| $existingEncoding = [0 => [0,0]]; | |
| } | |
| foreach ($existingEncoding as $symbol => $enc) { | |
| if (!in_array($symbol, $requiredSymbols)) { | |
| unset($existingEncoding[$symbol]); | |
| } | |
| } | |
| $possibleEncodings = removeEncodings([[0,0],[0,1],[1,0],[1,1]], $existingEncoding); | |
| $requiredSymbols = array_diff($requiredSymbols, array_keys($existingEncoding)); | |
| return completeEncoding($requiredSymbols, $possibleEncodings, [$existingEncoding]); | |
| } | |
| function completeEncoding($requiredSymbols, $possibleEncodings, $existingEncodings) | |
| { | |
| if (count($requiredSymbols) === 0) { | |
| return $existingEncodings; | |
| } | |
| $symbol = array_shift($requiredSymbols); | |
| $extendedEncodings = []; | |
| foreach ($possibleEncodings as $encoding) { | |
| foreach (completeEncoding($requiredSymbols, removeEncodings($possibleEncodings, [$encoding]), $existingEncodings) as $extendedEncoding) { | |
| $extendedEncoding[$symbol] = $encoding; | |
| $extendedEncodings[] = $extendedEncoding; | |
| } | |
| } | |
| return $extendedEncodings; | |
| } | |
| function removeEncodings($encs, $rems) | |
| { | |
| $encs = array_map(function ($arr) { return implode(",", $arr); }, $encs); | |
| $rems = array_map(function ($arr) { return implode(",", $arr); }, $rems); | |
| $encs = array_diff($encs, $rems); | |
| $encs = array_map(function ($str) { return explode(",", $str); }, $encs); | |
| return $encs; | |
| } | |
| function subTMCompile($targetTm, $maxStates, $roleConditions, $requiredStates, $leftEncoding, $rightEncoding) | |
| { | |
| $stateTms = []; | |
| $todoStates = []; | |
| for ($state = 0; $state < $targetTm["states"]; $state++) { | |
| $todoStates[] = $state; | |
| } | |
| $success = false; | |
| $stateMaxStates = 0; | |
| while ($stateMaxStates * count($todoStates) <= $maxStates) { | |
| foreach($todoStates as $state) { | |
| [$tm, $conditions, $targetRoles, $stateMap] = initialMap($requiredStates, $roleConditions, $state); | |
| $stateTms[$state] = [[], $stateMap]; | |
| if ($tm["states"] > $stateMaxStates) { | |
| continue; | |
| } | |
| $tms = grow($tm, $stateMaxStates, $stateMap, $conditions, $targetRoles, $leftEncoding, $rightEncoding); | |
| if (count($tms) > 0) { | |
| $stateTms[$state] = [$tms, $stateMap]; | |
| $maxStates = $maxStates - $stateMaxStates - 1; | |
| unset($todoStates[$state]); | |
| } | |
| } | |
| if (count($todoStates) === 0) { | |
| $success = true; | |
| break; | |
| } | |
| $stateMaxStates++; | |
| } | |
| if ($success) { | |
| [$prodTms, $stateMap] = combine($stateTms); | |
| outputMeta($stateMap, $leftEncoding, $rightEncoding); | |
| $minStates = $prodTms[0]["states"]; | |
| foreach ($prodTms as &$compiledTm) { | |
| $compiledTm["states"] = count($compiledTm) - 2; | |
| if ($compiledTm["states"] < $minStates) { | |
| $minStates = $compiledTm["states"]; | |
| } | |
| } | |
| foreach ($prodTms as $compiledTm) { | |
| if ($compiledTm["states"] === $minStates) { | |
| $compiledTm["start"] = 0; | |
| output($compiledTm); | |
| } | |
| } | |
| } | |
| return $success; | |
| } | |
| function bruteforceCompile($maxStates, $roleConditions, $requiredStates, $leftEncoding, $rightEncoding) | |
| { | |
| $success = false; | |
| foreach (initialMapBruteforce($requiredStates, $roleConditions) as [$tm, $conditions, $stateMap]) { | |
| if ($tm["states"] > $maxStates) { | |
| continue; | |
| } | |
| $tms = grow($tm, $maxStates, $stateMap, $conditions, [], $leftEncoding, $rightEncoding); | |
| if (count($tms) > 0) { | |
| $success = true; | |
| outputMeta($stateMap, $leftEncoding, $rightEncoding); | |
| foreach ($tms as $compiledTm) { | |
| if (isset($stateMap["LA"])) { | |
| $compiledTm["start"] = $stateMap["LA"]; | |
| } else { | |
| $compiledTm["start"] = $stateMap["RA"]; | |
| } | |
| output($compiledTm); | |
| } | |
| // var_dump($roleConditions, $conditions, $stateMap); die; | |
| } | |
| } | |
| return $success; | |
| } | |
| // commented are some methods, that give only one of the shortest combinations of subTMs | |
| // this might be required to save memory, if there are many. | |
| // function combine($stateTms) | |
| // { | |
| // $stateMap = []; | |
| // $tm = ["states" => 0, "symbols" => 2]; | |
| // [$tm, $stateMap] = expand($tm, $stateMap, $stateTms); | |
| // return [[$tm], $stateMap]; | |
| // } | |
| // function expand($tm, $stateMap, $stateTms) | |
| // { | |
| // if (count($stateTms) === 0) { | |
| // foreach ($tm as $key => $value) { | |
| // if (in_array($key,["states", "symbols"])) { | |
| // continue; | |
| // } | |
| // $tm[$key] = array_map(function($transition) use ($stateMap) { | |
| // if ($transition === "halt") { | |
| // return "halt"; | |
| // } | |
| // $state = $transition[2]; | |
| // if (isset($stateMap[$state])) { | |
| // $transition[2] = $stateMap[$state]; | |
| // } | |
| // return $transition; | |
| // }, $value); | |
| // } | |
| // $shrunk = shrink($tm); | |
| // return [$shrunk, $stateMap]; | |
| // } | |
| // [$nextTms, $nextStateMap] = array_shift($stateTms); | |
| // $usedStates = $tm["states"]; | |
| // foreach ($nextStateMap as $role => $state) { | |
| // $stateMap[$role] = $state + $usedStates; | |
| // } | |
| // foreach ($nextTms as $newTm) { | |
| // $newStates = $newTm["states"]; | |
| // unset($newTm["states"],$newTm["symbols"]); | |
| // $incCopy = []; | |
| // foreach ($newTm as $i=>$symbolTransitions) { | |
| // $incCopy[$i + $usedStates] = array_map(function($transition) use ($usedStates) { | |
| // if ($transition === "halt") { | |
| // return "halt"; | |
| // } | |
| // if (preg_match("/^\d+$/", $transition[2])) { | |
| // $transition[2] = $transition[2] + $usedStates; | |
| // } | |
| // return $transition; | |
| // }, $symbolTransitions); | |
| // } | |
| // $tm["states"] = $tm["states"] + $newStates; | |
| // foreach ($incCopy as $key => $value) { | |
| // $tm[$key] = $value; | |
| // } | |
| // [$grownTm, $grownStateMap] = expand($tm, $stateMap, $stateTms); | |
| // if (!isset($bestTm) || $bestTm["states"] > $grownTm["states"]) { | |
| // $bestTm = $grownTm; | |
| // $bestMap = $grownStateMap; | |
| // } | |
| // } | |
| // return [$bestTm, $bestMap]; | |
| // } | |
| function combine($stateTms) | |
| { | |
| [$tms, $stateMap] = array_shift($stateTms); | |
| return expand($tms, $stateMap, $stateTms); | |
| } | |
| function expand($tms, $stateMap, $stateTms) | |
| { | |
| if (count($stateTms) === 0) { | |
| $shrunk = []; | |
| foreach ($tms as $tm) { | |
| foreach ($tm as $key => $value) { | |
| if (in_array($key,["states", "symbols"])) { | |
| continue; | |
| } | |
| $tm[$key] = array_map(function($transition) use ($stateMap) { | |
| if ($transition === "halt") { | |
| return "halt"; | |
| } | |
| $state = $transition[2]; | |
| if (isset($stateMap[$state])) { | |
| $transition[2] = $stateMap[$state]; | |
| } | |
| return $transition; | |
| }, $value); | |
| } | |
| $shrunk[] = shrink($tm); | |
| } | |
| return [$shrunk, $stateMap]; | |
| } | |
| [$nextTms, $nextStateMap] = array_shift($stateTms); | |
| $usedStates = $tms[0]["states"]; | |
| foreach ($nextStateMap as $role => $state) { | |
| $stateMap[$role] = $state + $usedStates; | |
| } | |
| $prodTms = []; | |
| foreach ($nextTms as $newTm) { | |
| $newStates = $newTm["states"]; | |
| unset($newTm["states"],$newTm["symbols"]); | |
| $incCopy = []; | |
| foreach ($newTm as $i=>$symbolTransitions) { | |
| $incCopy[$i + $usedStates] = array_map(function($transition) use ($usedStates) { | |
| if ($transition === "halt") { | |
| return "halt"; | |
| } | |
| if (preg_match("/^\d+$/", $transition[2])) { | |
| $transition[2] = $transition[2] + $usedStates; | |
| } | |
| return $transition; | |
| }, $symbolTransitions); | |
| } | |
| foreach ($tms as $oldTm) { | |
| $oldTm["states"] = $oldTm["states"] + $newStates; | |
| foreach ($incCopy as $key => $value) { | |
| $oldTm[$key] = $value; | |
| } | |
| $prodTms[] = $oldTm; | |
| } | |
| } | |
| return expand($prodTms, $stateMap, $stateTms); | |
| } | |
| function shrink($tm) | |
| { | |
| unset($tm["states"], $tm["symbols"]); | |
| $tm = recursiveShrink($tm); | |
| $tm["states"] = count($tm); | |
| $tm["symbols"] = 2; | |
| return $tm; | |
| } | |
| function recursiveShrink($tm) { | |
| $compatibleStates = array_map(function($stateData) use ($tm) { | |
| return array_combine(array_keys($tm),array_keys($tm)); | |
| },$tm); | |
| $change = true; | |
| while ($change === true) { | |
| $change = false; | |
| foreach ($compatibleStates as $state1 => $options) { | |
| foreach ($options as $state2) { | |
| if (compatibleState($tm, $state1, $state2, $compatibleStates)) { | |
| continue; | |
| } | |
| unset($compatibleStates[$state1][$state2], $compatibleStates[$state2][$state1]); | |
| $change = true; | |
| } | |
| } | |
| } | |
| foreach ($compatibleStates as $state => $options) { | |
| if (count($options) <= 1) { | |
| unset($compatibleStates[$state]); | |
| continue; | |
| } | |
| $compatibleStates[$state] = array_diff($options, [$state]); | |
| } | |
| $bestTm = $tm; | |
| foreach ($compatibleStates as $state1 => $options) { | |
| foreach ($options as $state2) { | |
| $try = tryCollapse($tm, [[$state1, $state2]]); | |
| if ($try !== false) { | |
| $try = recursiveShrink($try); | |
| if (count($try) < count($bestTm)) { | |
| $bestTm = $try; | |
| } | |
| } | |
| } | |
| } | |
| return $bestTm; | |
| } | |
| function tryCollapse($tm, $todo) { | |
| if (count($todo)=== 0) { | |
| return $tm; | |
| } | |
| [$state1, $state2] = array_shift($todo); | |
| //after this loop is done all transitions from state 1 | |
| //are mirrored in state 2. Additional state equalities | |
| //that have to hold are appended to $todo. | |
| foreach ($tm[$state1] as $symbol => $trans1) { | |
| //continue if this transition is fine | |
| //return false if it is incompatible | |
| if (!isset($tm[$state2][$symbol])) { | |
| $tm[$state2][$symbol] = $trans1; | |
| continue; | |
| } | |
| $trans2 = $tm[$state2][$symbol]; | |
| if ($trans1 === "halt") { | |
| if ($trans2 !== "halt") { | |
| return false; | |
| } | |
| continue; | |
| } | |
| if ($trans2 === "halt") { | |
| if ($trans1 !== "halt") { | |
| return false; | |
| } | |
| continue; | |
| } | |
| [$sym1, $dir1, $next1] = $trans1; | |
| [$sym2, $dir2, $next2] = $trans2; | |
| if ($sym1 !== $sym2) { | |
| return false; | |
| } | |
| if ($dir1 !== $dir2) { | |
| return false; | |
| } | |
| if ($next1 === $next2) { | |
| continue; | |
| } | |
| $todo[] = [$next1, $next2]; | |
| } | |
| unset($tm[$state1]); | |
| //redirect all transitions into state1 to state2 | |
| foreach ($tm as &$transitions) { | |
| foreach ($transitions as &$trans) { | |
| if ($trans === "halt") { | |
| continue; | |
| } | |
| if ($trans[2] === $state1) { | |
| $trans[2] = $state2; | |
| } | |
| } | |
| } | |
| //clean up $todo | |
| foreach ($todo as $i => [$todo1, $todo2]) { | |
| if ($todo1 === $state1) { | |
| $todo1 = $state2; | |
| } | |
| if ($todo2 === $state1) { | |
| $todo2 = $state2; | |
| } | |
| if ($todo1 === $todo2) { | |
| unset($todo[$i]); | |
| continue; | |
| } | |
| $todo[$i] = [$todo1, $todo2]; | |
| } | |
| return tryCollapse($tm, $todo); | |
| } | |
| function compatibleState($tm, $state1, $state2, $compatibleStates) | |
| { | |
| foreach ($tm[$state1] as $symbol => $transition1) { | |
| if (!isset($tm[$state2][$symbol])) { | |
| continue; | |
| } | |
| $transition2 = $tm[$state2][$symbol]; | |
| if (!compatibleTransition($transition1, $transition2, $compatibleStates)) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| function compatibleTransition($trans1, $trans2, $compatibleStates) | |
| { | |
| if ($trans1 === "halt") { | |
| return ($trans2 === "halt"); | |
| } | |
| if ($trans2 === "halt") { | |
| return ($trans1 === "halt"); | |
| } | |
| [$sym1, $dir1, $state1] = $trans1; | |
| [$sym2, $dir2, $state2] = $trans2; | |
| if ($sym1 !== $sym2) { | |
| return false; | |
| } | |
| if ($dir1 !== $dir2) { | |
| return false; | |
| } | |
| return in_array($state2, $compatibleStates[$state1]); | |
| } | |
| function initialMap($requiredStates, $roleConditions, $focusedState) | |
| { | |
| $state = 0; | |
| $stateMap = []; | |
| foreach (array_keys($requiredStates) as $role) { | |
| if (strpos($role, intToState($focusedState)) === false) { | |
| continue; | |
| } | |
| $stateMap[$role] = $state; | |
| $state ++; | |
| } | |
| $tm = ["states" => $state, "symbols" => 2]; | |
| $conditions = []; | |
| $targetRoles = []; | |
| foreach($roleConditions as $config => $goal) { | |
| if (strpos($config, intToState($focusedState)) === false) { | |
| continue; | |
| } | |
| [$config, $goal] = str_replace(array_keys($stateMap), array_values($stateMap), [$config, $goal]); | |
| $conditions[$config] = $goal; | |
| if ($goal === "HALT") { | |
| continue; | |
| } | |
| $goalState = decodeConfig($goal)[0]; | |
| if (preg_match("/^\d+$/",$goalState) || in_array($goalState, $targetRoles)) { | |
| continue; | |
| } | |
| $targetRoles[] = $goalState; | |
| } | |
| return [$tm, $conditions, $targetRoles, $stateMap]; | |
| } | |
| function initialMapBruteforce($requiredStates, $roleConditions) | |
| { | |
| $leftStates = []; | |
| $rightStates = []; | |
| foreach ($requiredStates as $role => [$fromDir, ]) { | |
| switch ($fromDir) { | |
| case "L": | |
| $leftStates[] = $role; | |
| break; | |
| case "R": | |
| $rightStates[] = $role; | |
| break; | |
| } | |
| } | |
| $possibileMaps = []; | |
| foreach (partialBijections($leftStates, $rightStates) as $roleCollapse) { | |
| $state = 0; | |
| $stateMap = []; | |
| foreach (array_keys($requiredStates) as $role) { | |
| if (isset($stateMap[$role])) { | |
| continue; | |
| } | |
| $stateMap[$role] = $state; | |
| if (isset($roleCollapse[$role])) { | |
| $stateMap[$roleCollapse[$role]] = $state; | |
| } | |
| $state ++; | |
| } | |
| $tm = ["states" => $state, "symbols" => 2]; | |
| $conditions = []; | |
| foreach($roleConditions as $config => $goal) { | |
| [$config, $goal] = str_replace(array_keys($stateMap), array_values($stateMap), [$config, $goal]); | |
| if (isset($conditions[$config])) { | |
| if ($conditions[$config] !== $goal) { | |
| continue 2; | |
| } | |
| } | |
| $conditions[$config] = $goal; | |
| } | |
| $possibileMaps[] = [$tm, $conditions, $stateMap]; | |
| } | |
| return $possibileMaps; | |
| } | |
| function partialBijections($set1, $set2, $tail=[[]]) | |
| { | |
| if (count($set1) === 0) { | |
| return $tail; | |
| } | |
| $elem1 = array_shift($set1); | |
| $pbs = []; | |
| foreach ($tail as $partial) { | |
| $pbs[] = $partial; | |
| foreach ($set2 as $elem2) { | |
| if (in_array($elem2, $partial)) { | |
| continue; | |
| } | |
| $partial[$elem1] = $elem2; | |
| $pbs[] = $partial; | |
| } | |
| } | |
| return partialBijections($set1, $set2, $pbs); | |
| } | |
| function grow($tm, $maxStates, $stateMap, $conditions, $targetRoles, $leftEncoding, $rightEncoding) | |
| { | |
| $todo = check($tm, $conditions); | |
| switch ($todo) { | |
| case "works": | |
| return [$tm]; | |
| case "contra": | |
| return []; | |
| } | |
| //grow | |
| while (true) { | |
| foreach ($conditions as $config => $goal) { | |
| [$nextConfig, $status] = step($tm, $config); | |
| switch ($status) { | |
| case "step": | |
| unset($conditions[$config]); | |
| $conditions[$nextConfig] = $goal; | |
| continue 2; | |
| case "halt": | |
| case "done": | |
| unset($conditions[$config]); | |
| continue 2; | |
| } | |
| //undef | |
| [$state, $pos, $tape] = decodeConfig($nextConfig); | |
| return growAt($state, $tape[$pos], $tm, $maxStates, $stateMap, $conditions, $targetRoles, $leftEncoding, $rightEncoding); | |
| } | |
| } | |
| done("nowhere to grow"); | |
| } | |
| function growAt($state, $symbol, $tm, $maxStates, $stateMap, $conditions, $targetRoles, $leftEncoding, $rightEncoding) | |
| { | |
| $possibleTms = []; | |
| $tm[$state][$symbol] = "halt"; | |
| $possibleTms = array_merge($possibleTms, grow($tm, $maxStates, $stateMap, $conditions, $targetRoles, $leftEncoding, $rightEncoding)); | |
| foreach ($targetRoles as $newState) { | |
| foreach ([["L",0],["L",1],["R",0],["R",1]] as [$dir, $newSymbol]) { | |
| $tm[$state][$symbol] = [$newSymbol, $dir, $newState]; | |
| $possibleTms = array_merge($possibleTms, grow($tm, $maxStates, $stateMap, $conditions, $targetRoles, $leftEncoding, $rightEncoding)); | |
| } | |
| } | |
| $curStates = $tm["states"]; | |
| for ($newState = 0; $newState <= $curStates; $newState++) { | |
| if ($newState == $curStates) { | |
| $tm["states"] = $newState + 1; | |
| if ($tm["states"] > $maxStates) { | |
| continue; | |
| } | |
| } | |
| foreach ([["L",0],["L",1],["R",0],["R",1]] as [$dir, $newSymbol]) { | |
| $tm[$state][$symbol] = [$newSymbol, $dir, $newState]; | |
| $possibleTms = array_merge($possibleTms, grow($tm, $maxStates, $stateMap, $conditions, $targetRoles, $leftEncoding, $rightEncoding)); | |
| } | |
| } | |
| return $possibleTms; | |
| } | |
| function check($tm, $conditions) | |
| { | |
| foreach ($conditions as $config => $goal) { | |
| [$finConfig, $status] = ffwd($tm, $config); | |
| if ($status === "done") { | |
| if ($finConfig === $goal) { | |
| unset($conditions[$config]); | |
| continue; | |
| } | |
| return "contra"; | |
| } | |
| if (isset($conditions[$finConfig])) { | |
| if ($conditions[$finConfig] !== $goal) { | |
| return "contra"; | |
| } | |
| } | |
| if (!preg_match("/^\d+$/", decodeConfig($finConfig)[0])) { | |
| return "contra"; | |
| } | |
| unset($conditions[$config]); | |
| $conditions[$finConfig] = $goal; | |
| } | |
| if (count($conditions) === 0) { | |
| return "works"; | |
| } | |
| return "grow"; | |
| } | |
| function step($tm, $configString) | |
| { | |
| [$state, $pos, $tape] = decodeConfig($configString); | |
| if (!isset($tape[$pos])) { | |
| return [$configString, "done"]; | |
| } | |
| if (!isset($tm[$state][$tape[$pos]])) { | |
| return [$configString, "undef"]; | |
| } | |
| $transition = $tm[$state][$tape[$pos]]; | |
| if ($transition === "halt") { | |
| return [$configString, "halt"]; | |
| } | |
| [$tape[$pos], $dir, $state] = $transition; | |
| $pos = ["L" => ["L",0] , "R" => [1,"R"]][$dir][$pos]; | |
| $configString = encodeConfig([$state, $pos, $tape]); | |
| return [$configString, "step"]; | |
| } | |
| function ffwd($tm, $configString) | |
| { | |
| $history = []; | |
| $status = "step"; | |
| while ($status === "step") { | |
| if (in_array($configString, $history)) { | |
| return ["CYCLE", "done"]; | |
| } | |
| $history[]=$configString; | |
| [$configString, $status] = step($tm, $configString); | |
| } | |
| if ($status === "halt") { | |
| return ["HALT", "done"]; | |
| } | |
| return [$configString, $status]; | |
| } | |
| function encodeConfig($config) | |
| { | |
| $config[2] = implode(",", $config[2]); | |
| return implode(";",$config); | |
| } | |
| function decodeConfig($configString) | |
| { | |
| $config = explode(";", $configString); | |
| $config[2] = explode(",", $config[2]); | |
| return $config; | |
| } | |
| function extractConditions($tm, $requiredStates, $leftEncoding, $rightEncoding) | |
| { | |
| $encoding = ["L" => $rightEncoding, "R" => $leftEncoding]; | |
| unset($tm["states"]); | |
| unset($tm["symbols"]); | |
| $conds = []; | |
| foreach ($requiredStates as [$fromDir, $fromState]) { | |
| foreach ($tm[$fromState] as $fromSymbol => [$toSymbol, $toDir, $toState]) { | |
| if (!isset($encoding[$fromDir][$fromSymbol])) { | |
| continue; | |
| } | |
| $config = encodeCondition($fromState, $fromDir, $encoding[$fromDir][$fromSymbol]); | |
| $goal = "HALT"; | |
| if (isset($tm[$toState])) { | |
| $goal = encodeGoal($toState, $toDir, $encoding[$toDir][$toSymbol]); | |
| } | |
| $conds[$config] = $goal; | |
| } | |
| } | |
| return $conds; | |
| } | |
| function encodeCondition($fromState, $fromDir, $tape) | |
| { | |
| return implode(";", [encodeState($fromDir, $fromState), ["R"=>1,"L"=>0][$fromDir], implode(",",$tape)]); | |
| } | |
| function encodeGoal($toState, $toDir, $tape) | |
| { | |
| return implode(";", [encodeState(m($toDir), $toState), $toDir, implode(",",$tape)]); | |
| } | |
| function encodeState($dir, $state) | |
| { | |
| return $dir . $state; | |
| } | |
| function getRequiredStatesAndSymbols($tm) | |
| { | |
| unset($tm["states"], $tm["symbols"]); | |
| $reqs = []; | |
| $reqL = ["0"]; | |
| $reqR = ["0"]; | |
| foreach ($tm as $symbolTransitions) { | |
| if (!is_array($symbolTransitions)) { | |
| continue; | |
| } | |
| foreach ($symbolTransitions as $transition) { | |
| if (!is_array($transition)) { | |
| continue; | |
| } | |
| [$symbol, $dir, $state] = $transition; | |
| if (!isset($tm[$state])) { | |
| continue; | |
| } | |
| $dir = m($dir); | |
| $reqs[encodeState($dir, $state)] = [$dir, $state]; | |
| if ($dir === "L" && !in_array($symbol, $reqL)) { | |
| $reqL[] = $symbol; | |
| } | |
| if ($dir === "R" && !in_array($symbol, $reqR)) { | |
| $reqR[] = $symbol; | |
| } | |
| } | |
| } | |
| if (isset($reqs[encodeState("L", "A")]) || isset($reqs[encodeState("R", "A")]) ) { | |
| return [[$reqs, $reqL, $reqR]]; | |
| } | |
| $reqsL = $reqs; | |
| $reqsL[encodeState("L", "A")] = ["L", "A"]; | |
| $reqsR = $reqs; | |
| $reqsR[encodeState("R", "A")] = ["R", "A"]; | |
| return [[$reqsL, $reqL, $reqR], [$reqsR, $reqL, $reqR]]; | |
| } | |
| function m($dir) | |
| { | |
| return ["L"=>"R","R"=>"L"][$dir]; | |
| } | |
| //--------------------main------------------------------- | |
| if (!isset($argv[1])) { | |
| done("Usage: php compiler.php <StdTmString> mode\nmode % 2 = 1 -> bruteforce\nmode/2 % 2 = 1 -> different side encodings\n"); | |
| } | |
| global $mode; | |
| $mode = 0; | |
| if (isset($argv[2])) { | |
| $mode = $argv[2]; | |
| } | |
| $tmString = $argv[1]; | |
| $tm = readTm($tmString); | |
| compile($tm); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment