patternMinor
Computability of Stack Cleanliness
Viewed 0 times
cleanlinesscomputabilitystack
Problem
Brain-Flak is a minimalistic, stack-based, Turing complete, esoteric programming language.
A big concern among Brain-Flak enthusiasts is a concept informally called "stack cleanliness".
The basic idea for stack cleanliness is that only certain values on the stack will be edited and all other values will remain unchanged
More formally:
Given an input arity (a tuple of positions on the active and inactive stack before the program runs), and an output arity (another tuple of the same sort after the program runs) and a function that maps between the two, a program is is considered stack clean iff it performs the function, ends on the stack it started, and the values on the stack that are not in the input remain the same regardless of the conditions of the stack.
The question is: Given a program that is known to halt for all input, a function and the two required arity tuples, is stack cleanliness computable?
A big concern among Brain-Flak enthusiasts is a concept informally called "stack cleanliness".
The basic idea for stack cleanliness is that only certain values on the stack will be edited and all other values will remain unchanged
More formally:
Given an input arity (a tuple of positions on the active and inactive stack before the program runs), and an output arity (another tuple of the same sort after the program runs) and a function that maps between the two, a program is is considered stack clean iff it performs the function, ends on the stack it started, and the values on the stack that are not in the input remain the same regardless of the conditions of the stack.
The question is: Given a program that is known to halt for all input, a function and the two required arity tuples, is stack cleanliness computable?
Solution
I don't know the language in detail, but my guess is: no, stack cleanliness is not computable.
For every natural $n$, consider a Brain-Flak program $P_n$ which does the following:
$P_n(k)$ is guaranteed to halt for any inputs $n,k$.
$P_n$ will be stack-clean (on all inputs $k$, by definition) if and only if the TM number $n$ never terminates on empty input.
The latter is known to be undecidable (it's not even semi-decidable).
Hence stack cleanliness over input arity 1, output arity 1, and constant zero function is already undecidable.
For every natural $n$, consider a Brain-Flak program $P_n$ which does the following:
- take a natural $k$ as input;
- without modifying the stack below, simulate Turing Machine number $n$ on empty input, for at most $k$ steps;
- if the machine does not halt within $k$ steps, revert the stack to the original state, and return $0$;
- otherwise, if it does halt, modify the stack below and return $0$.
$P_n(k)$ is guaranteed to halt for any inputs $n,k$.
$P_n$ will be stack-clean (on all inputs $k$, by definition) if and only if the TM number $n$ never terminates on empty input.
The latter is known to be undecidable (it's not even semi-decidable).
Hence stack cleanliness over input arity 1, output arity 1, and constant zero function is already undecidable.
Context
StackExchange Computer Science Q#65411, answer score: 7
Revisions (0)
No revisions yet.