Humo is a programming language with a tiny interpreter implementation and the smallest set of operations for an imperative programming language.
This is an experimental language that uses very few concepts to perform Turing complete computations.
Live demo: Humo IDE
Humo is a computational model proven to be Turing Complete, built entirely upon string rewriting and recursive substitution. It differs fundamentally from traditional interpreters by operating only on a single, continuous string of text and possessing no internal keywords or reserved memory structures.
Formally, Humo functions as a Dynamic Semi-Thue System where the set of substitution rules evolves during execution.
The engine recognizes only one primitive operation: the Rule Definition.
- Definition Phase: When the engine encounters
pattern{replacement}, it registers that the stringpatternmaps toreplacement. - Expansion Phase: When the engine encounters
patternlater, it replaces it withreplacement.
The core principle is recursive expansion: the output of a substitution is immediately re-scanned. This capability is what allows the program to dynamically modify its own rule set (meta-programming) and create complex control flow. Crucially, all standard syntax (e.g., [run], $) is user-defined convention, not part of the engine itself.
Humo has been empirically proven to be Turing Complete.
By utilizing the mechanisms described above—specifically the infinite tape simulation via dynamic variables (tape_n), conditional state transitions (RULE_q_sym), and recursive control flow—we have successfully implemented a full Universal Turing Machine within Humo.
Proof of Concept: A functional implementation of a Decimal-to-Binary Converter was built using Humo. This implementation replicates the state table of a standard Turing Machine, handling:
Infinite tape traversal (Left/Right movements).
Symbol reading and writing via string concatenation (tape_ + position).
State changes via dynamic rule dispatch (RULE_ + state + symbol).
This demonstrates that despite having only a single "instruction" (text substitution), Humo is capable of computing any algorithm that a Turing Machine can run.
Complete interpreter implementation code (the following code executes any Humo program) :
/*
* Humo Language
* Copyright (C) 2002-2010, Fernando Damian Petrola
*
* Distributable under GPL license.
* See terms of license at gnu.org.
*/
package ar.net.fpetrola.humo;
import java.util.HashMap;
import java.util.Map;
public class HumoInterpreter
{
protected Map<CharSequence, CharSequence> productions = new HashMap<CharSequence, CharSequence>();
public int parse(StringBuilder sourcecode, int first)
{
int last = first, current = first;
for (char currentChar; last < sourcecode.length() && (currentChar = sourcecode.charAt(last++)) != '}';)
{
if (currentChar == '{')
{
current = parse(sourcecode, last);
productions.put(sourcecode.subSequence(first, last - 1), sourcecode.subSequence(last, current - 1));
last = first = current;
}
CharSequence production = productions.get(sourcecode.subSequence(current, last));
if (production != null)
{
StringBuilder value = new StringBuilder(production);
parse(value, 0);
sourcecode.replace(current, last, value.toString());
last = current += value.length();
}
}
return last;
}
}Coding example:
[comm{[com}ent]{ment]}
[comment] {----------------------------------------------------- Humo Runtime -----------------------------------------------------}
[comment] {-------------------------------------------------------------------------------------------------------------------------}
[te{[t}mp]{emp]}
[sent{[sen}ence]{tence]}
[exec]{[run]}
[run]{[sentence]}
[vari{[var}able]{iable]}
[exec{[exe}ute]{cute]}
[cre{[cr}ate]{eate]}
[field]{[variable]$instance:name.}
#class{new}
#method:{[me][thod]<*>instance:name.}
#property:{[prop][erty]<*>instance:name.}
#this.{[do][llar]<*>instance:name.}
<--{<-}
<->{@}
<**{<*}
<*>{$}
[dollar]{$}
[do]{[do}
[llar]{llar]}
[method]{$}
[me]{[me}
[thod]{thod]}
[property]{$}
[prop]{[prop}
[erty]{erty]}
[_x{[_}
_]{x_]}
@[{[}
@a{a}
@b{b}
@e{e}
@t{t}
@v{v}
@u{u}
@r{r}
@${$}
#begin-construction {
[run]{<-->[@vari{<*}<-->a@ble]{>}}
[run]{<-->[@exec{}<-->u@te]{$}}
[run]{<-->@[cre{}<-->@ate]{new}}
}
#end-construction {
[run]{<***>instance:name{<****>instance:name}}
[run]{<-->[@vari{[var}<-->a@ble]{iable]}}
[run]{<-->[@exec{[exe}<-->u@te]{cute]}}
[run]{<-->@[cre{@[cr}<-->@ate]{<-->e@ate]}}
}
[comment] {------------------- ARITMETICA BASICA (Para el Cabezal) -------------------}
[comment] { Tablas para mover el indice de la cinta (Head Position) }
[comment] { -- Valores Hexadecimales Positivos (0-F) -- }
INC_0{1} INC_1{2} INC_2{3} INC_3{4} INC_4{5} INC_5{6} INC_6{7} INC_7{8} INC_8{9}
INC_9{A} INC_A{B} INC_B{C} INC_C{D} INC_D{E} INC_E{F}
[comment] { -- Valores Negativos Hexadecimales (0 a -F) -- }
INC_-1{0} INC_-2{-1} INC_-3{-2} INC_-4{-3} INC_-5{-4} INC_-6{-5} INC_-7{-6} INC_-8{-7} INC_-9{-8}
INC_-A{-9} INC_-B{-A} INC_-C{-B} INC_-D{-C} INC_-E{-D} INC_-F{-E}
[comment] { -- Valores Hexadecimales Positivos (1-F) -- }
DEC_1{0} DEC_2{1} DEC_3{2} DEC_4{3} DEC_5{4} DEC_6{5} DEC_7{6} DEC_8{7} DEC_9{8}
DEC_A{9} DEC_B{A} DEC_C{B} DEC_D{C} DEC_E{D} DEC_F{E}
[comment] { -- Transicion Cero y Valores Negativos (0 a -F) -- }
DEC_0{-1}
DEC_-1{-2} DEC_-2{-3} DEC_-3{-4} DEC_-4{-5} DEC_-5{-6} DEC_-6{-7} DEC_-7{-8} DEC_-8{-9}
DEC_-9{-A} DEC_-A{-B} DEC_-B{-C} DEC_-C{-D} DEC_-D{-E} DEC_-E{-F}
[comment] {------------------- REGLAS DE LA MAQUINA DE TURING (DEC -> BIN) -------------------}
[comment] { Formato de la Regla: RULE_EstadoActual_SimboloLeido }
[comment] { Accion: Establece nuevas variables globales para la siguiente iteracion }
[comment] { ESTADO qinit: Mover el cabezal al final del número para iniciar la división }
$RULE_qinit_0{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{R} } }
$RULE_qinit_1{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{R} } }
$RULE_qinit_2{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{2} } [run]{ <**> moveDir{R} } }
$RULE_qinit_3{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{3} } [run]{ <**> moveDir{R} } }
$RULE_qinit_4{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{4} } [run]{ <**> moveDir{R} } }
$RULE_qinit_5{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{5} } [run]{ <**> moveDir{R} } }
$RULE_qinit_6{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{6} } [run]{ <**> moveDir{R} } }
$RULE_qinit_7{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{7} } [run]{ <**> moveDir{R} } }
$RULE_qinit_8{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{8} } [run]{ <**> moveDir{R} } }
$RULE_qinit_9{ [run]{ <**> nextState{qinit} } [run]{ <**> writeVal{9} } [run]{ <**> moveDir{R} } }
$RULE_qinit__{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{L} } }
[comment] { ESTADO halve: Dividir el dígito actual por 2. Cociente se escribe, residuo se lleva. }
$RULE_halve_0{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{L} } }
$RULE_halve_1{ [run]{ <**> nextState{addHalf} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{R} } }
$RULE_halve_2{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{L} } }
$RULE_halve_3{ [run]{ <**> nextState{addHalf} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{R} } }
$RULE_halve_4{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{2} } [run]{ <**> moveDir{L} } }
$RULE_halve_5{ [run]{ <**> nextState{addHalf} } [run]{ <**> writeVal{2} } [run]{ <**> moveDir{R} } }
$RULE_halve_6{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{3} } [run]{ <**> moveDir{L} } }
$RULE_halve_7{ [run]{ <**> nextState{addHalf} } [run]{ <**> writeVal{3} } [run]{ <**> moveDir{R} } }
$RULE_halve_8{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{4} } [run]{ <**> moveDir{L} } }
$RULE_halve_9{ [run]{ <**> nextState{addHalf} } [run]{ <**> writeVal{4} } [run]{ <**> moveDir{R} } }
$RULE_halve__{ [run]{ <**> nextState{removezero} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{R} } }
[comment] { ESTADO addHalf: El dígito anterior era impar, debo sumar 5 (0.5 * 10) al dígito actual. }
$RULE_addHalf_0{ [run]{ <**> nextState{jump} } [run]{ <**> writeVal{5} } [run]{ <**> moveDir{L} } }
$RULE_addHalf_1{ [run]{ <**> nextState{jump} } [run]{ <**> writeVal{6} } [run]{ <**> moveDir{L} } }
$RULE_addHalf_2{ [run]{ <**> nextState{jump} } [run]{ <**> writeVal{7} } [run]{ <**> moveDir{L} } }
$RULE_addHalf_3{ [run]{ <**> nextState{jump} } [run]{ <**> writeVal{8} } [run]{ <**> moveDir{L} } }
$RULE_addHalf_4{ [run]{ <**> nextState{jump} } [run]{ <**> writeVal{9} } [run]{ <**> moveDir{L} } }
[comment] { ESTADO jump: Simplemente moverse hacia atrás para seguir con la division (halve) }
$RULE_jump_0{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{L} } }
$RULE_jump_1{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{L} } }
$RULE_jump_2{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{2} } [run]{ <**> moveDir{L} } }
$RULE_jump_3{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{3} } [run]{ <**> moveDir{L} } }
$RULE_jump_4{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{4} } [run]{ <**> moveDir{L} } }
[comment] { ESTADO removezero: Limpiar ceros a la izquierda y el digito final. }
$RULE_removezero_0{ [run]{ <**> nextState{removezero} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{R} } }
$RULE_removezero_1{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{R} } }
$RULE_removezero_2{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{2} } [run]{ <**> moveDir{R} } }
$RULE_removezero_3{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{3} } [run]{ <**> moveDir{R} } }
$RULE_removezero_4{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{4} } [run]{ <**> moveDir{R} } }
$RULE_removezero_5{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{5} } [run]{ <**> moveDir{R} } }
$RULE_removezero_6{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{6} } [run]{ <**> moveDir{R} } }
$RULE_removezero_7{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{7} } [run]{ <**> moveDir{R} } }
$RULE_removezero_8{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{8} } [run]{ <**> moveDir{R} } }
$RULE_removezero_9{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{9} } [run]{ <**> moveDir{R} } }
$RULE_removezero__{ [run]{ <**> nextState{qfin} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{R} } }
[comment] { ESTADO goBack: Mover a la derecha hasta el final del numero. }
$RULE_goBack_0{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{R} } }
$RULE_goBack_1{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{R} } }
$RULE_goBack_2{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{2} } [run]{ <**> moveDir{R} } }
$RULE_goBack_3{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{3} } [run]{ <**> moveDir{R} } }
$RULE_goBack_4{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{4} } [run]{ <**> moveDir{R} } }
$RULE_goBack_5{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{5} } [run]{ <**> moveDir{R} } }
$RULE_goBack_6{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{6} } [run]{ <**> moveDir{R} } }
$RULE_goBack_7{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{7} } [run]{ <**> moveDir{R} } }
$RULE_goBack_8{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{8} } [run]{ <**> moveDir{R} } }
$RULE_goBack_9{ [run]{ <**> nextState{goBack} } [run]{ <**> writeVal{9} } [run]{ <**> moveDir{R} } }
$RULE_goBack__{ [run]{ <**> nextState{rest} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{L} } }
[comment] { ESTADO rest: Determinar el bit menos significativo del número original (0 o 1). }
$RULE_rest_0{ [run]{ <**> nextState{rest0} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{R} } }
$RULE_rest_5{ [run]{ <**> nextState{rest1} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{R} } }
[comment] { ESTADOS rest0/rest1: Avanzar, limpiando el dígito final, para escribir el bit de residuo. }
$RULE_rest0__{ [run]{ <**> nextState{setrest0} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{R} } }
$RULE_rest1__{ [run]{ <**> nextState{setrest1} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{R} } }
[comment] { ESTADOS setrest0/setrest1: Moverse al final del resultado (binario) }
$RULE_setrest0_0{ [run]{ <**> nextState{setrest0} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{R} } }
$RULE_setrest0_1{ [run]{ <**> nextState{setrest0} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{R} } }
$RULE_setrest0__{ [run]{ <**> nextState{continue} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{L} } }
$RULE_setrest1_0{ [run]{ <**> nextState{setrest1} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{R} } }
$RULE_setrest1_1{ [run]{ <**> nextState{setrest1} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{R} } }
$RULE_setrest1__{ [run]{ <**> nextState{continue} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{L} } }
[comment] { ESTADO continue: Mover al inicio del número decimal para seguir dividiendo }
$RULE_continue_0{ [run]{ <**> nextState{continue} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{L} } }
$RULE_continue_1{ [run]{ <**> nextState{continue} } [run]{ <**> writeVal{1} } [run]{ <**> moveDir{L} } }
$RULE_continue__{ [run]{ <**> nextState{continue2} } [run]{ <**> writeVal{_} } [run]{ <**> moveDir{L} } }
[comment] { ESTADO continue2: Delimitador, ir a la división de nuevo }
$RULE_continue2__{ [run]{ <**> nextState{halve} } [run]{ <**> writeVal{0} } [run]{ <**> moveDir{L} } }
[comment] { ESTADO qfin: Estado de aceptación. El resultado está escrito después del número original. }
[comment] {------------------- LOGICA DE LA MAQUINA -------------------}
#class TuringMachine {
#begin-construction
[comment] { --- Inicializacion --- }
#method:init {
[run]{ [variable] tm:headPos{0} }
[run]{ [variable] tm:currentState{qinit} }
[run]{ [variable] tm:running{true} }
}
[comment] { --- Ciclo Principal (Recursivo) --- }
#method:ran {
[run]{ [variable] isRunning{#this.running} }
[comment] { Despacho dinamico: si isRunning es true, llama a step, si no, para }
[run]{ [variable] b1{[execute]action_} }
[run]{ [variable] nextAction{[execute]b1 $isRunning} }
[run]{ [execute] nextAction }
}
[comment] { --- Un paso de la maquina --- }
#method:step {
[comment] { 1. LEER CINTA }
[run]{ [variable] pos{#this.headPos} }
[run]{ [variable] _tape_{[execute]tape_} }
[run]{ [variable] currentSym{[execute]_tape_ $pos} }
[comment] { 2. BUSCAR REGLA (Transition Function) }
[run]{ [variable] state{#this.currentState_} }
[run]{ [variable] _rule_{[execute]RULE_} }
[run]{ [variable] ruleName{[execute]_rule_ $state $currentSym} }
[comment] { 3. EJECUTAR REGLA (Esto carga nextState, writeVal y moveDir) }
[run]{ [execute] ruleName }
[comment] { 4. ESCRIBIR EN CINTA }
[run]{ [variable] valToWrite{$writeVal} }
[run]{ [execute] _tape_ $pos{$valToWrite} }
[comment] { 5. MOVER CABEZAL }
[run]{ [variable] dir{$moveDir} }
[run]{ [variable] _move_{[execute]MOVE_} }
[run]{ [variable] moveCmd{[execute]_move_ $dir} }
[run]{ [execute] moveCmd }
[comment] { 6. ACTUALIZAR ESTADO }
[run]{ [field] currentState{$nextState} }
[comment] { 7. VERIFICAR HALT }
[run]{ [variable] _check_halt_{[execute]CHECK_HALT_} }
[run]{ [variable] checker{[execute]_check_halt_ $nextState} }
[run]{ [execute] checker }
[comment] { 8. RECURSION (Bucle Infinito) }
[run]{ [execute] tm1.ran }
}
#property:headPos { [execute] tm:headPos }
#property:currentState { [execute] tm:currentState }
#property:running { [execute] tm:running }
#end-construction
}
[comment] {------------------- HELPERS DE CONTROL -------------------}
[comment] { Helpers para el bucle while }
$action_true{ $tm1.step }
$action_false{ [comment] { Termino el programa } }
[comment] { Helpers para mover el cabezal }
$MOVE_R{
[run]{ <**> _position_{$tm:headPos} }
[run]{ <**> _inc_{INC_} }
[run]{ <**> temp1{<*>_inc_ $_position_} }
[run]{ <**> tm:headPos{<*> temp1} }
}
$MOVE_L{
[run]{ <**> _position_{$tm:headPos} }
[run]{ <**> _dec_{DEC_} }
[run]{ <**> temp1{<*>_dec_ $_position_} }
[run]{ <**> tm:headPos{<*> temp1} }
}
$MOVE_N{ }
[comment] { Helper para detectar estado de parada }
$CHECK_HALT_qfin{ [run]{ <**> tm:running{false} } }
[comment] {------------------- MAIN -------------------}
#class Main {
#begin-construction
#method:execute {
[comment] { 1. Configurar Cinta Inicial: Ampliada para índices negativos y positivos }
[comment] { Cinta Negativa (Indexación Lógica) }
[run]{ [variable] tape_-9{_} }
[run]{ [variable] tape_-8{_} }
[run]{ [variable] tape_-7{_} }
[run]{ [variable] tape_-6{_} }
[run]{ [variable] tape_-5{_} }
[run]{ [variable] tape_-4{_} }
[run]{ [variable] tape_-3{_} }
[run]{ [variable] tape_-2{_} }
[run]{ [variable] tape_-1{_} }
[run]{ [variable] tape_0{1} }
[run]{ [variable] tape_1{0} }
[run]{ [variable] tape_2{_} }
[run]{ [variable] tape_3{_} }
[run]{ [variable] tape_4{_} }
[run]{ [variable] tape_5{_} }
[run]{ [variable] tape_6{_} }
[run]{ [variable] tape_7{_} }
[run]{ [variable] tape_8{_} }
[run]{ [variable] tape_9{_} }
[comment] { 2. Crear Maquina }
[run]{ [variable] instance:name{tm1} }
[run]{ [create] TuringMachine }
[run]{ [execute] tm1.init }
[comment] { 3. Ejecutar }
[run]{ [execute] tm1.ran }
[comment] { 4. Ver Resultado (Deberia ser 1101, a partir de tape_3) }
[run]{ [variable] res0{$tape_0} }
[run]{ [variable] res1{$tape_1} }
[run]{ [variable] res2{$tape_2} }
[run]{ [variable] res3{$tape_3} }
[run]{ [variable] res4{$tape_4} }
[run]{ [variable] res5{$tape_5} }
[run]{ [variable] res6{$tape_6} }
[run]{ [variable] res7{$tape_7} }
[run]{ [variable] res8{$tape_8} }
[run]{ [variable] res9{$tape_9} }
}
#end-construction
}
[temp] {
[run]{ $instance:name{mainApp} }
[run]{ new Main }
[run]{ $mainApp.execute }
}