Questions tagged [halting-problem]
For problems pertaining to the whether or not an automaton will halt.
15 questions
8 votes
6 answers
839 views
How does the NSDT program end?
Challenge: NSDT is like a calculus model invented by me that contains only 4 commands and grouping. Your task is to check in which way the program ends. The program is read from left to right. There ...
- 5,085
8 votes
5 answers
851 views
Will this makina program halt?
makina is a cell-based esolang composed of automata which move around a grid. These automata follow paths of instructions that direct their movement. Your task is to, given a makina program using only ...
- 6,098
18 votes
2 answers
493 views
Solve the halting problem for S combinatory logic
Background Combinatory logic is a system where a term is written using a finite set of combinators and function application between terms, and reduction rules are defined for each combinator. The well-...
- 79.3k
13 votes
2 answers
345 views
Determine if a dot(comma) program halts
Dotcomma is a simple esolang I made a while ago that only uses four operators: [.,]. In this challenge, you'll determine if a dotcomma program consisting only of <...
- 19.3k
12 votes
3 answers
510 views
Solve the Halting Problem for Modilar SNISP
In the spirit of Solve the Halting Problem for Befinge, let's define another 2D language called Modilar SNISP. Modilar SNISP has the following six instructions: \ ...
- 15.6k
6 votes
2 answers
809 views
Generate all halting Smallfuck programs of length n
Your task is to write a program that, given a number n, returns a list of all valid, halting Smallfuck programs of length n, in any order. Actually, we're using a variation of Smallfuck called F2, ...
- 15.6k
29 votes
11 answers
2k views
Solve the Halting Problem for Befinge
Let's define a simple 2D language, which we'll give the incredibly original name befinge. Befinge has 5 instructions: <>^v, as in most 2D esolangs, redirect ...
- 15.6k
10 votes
4 answers
1k views
Partially Solve the halting problem for brainf***
To solve the Halting Problem you are given a description of a program, and must determine whether or not it will ever finish. You can never do this for all programs. Yet for programs like (in brainf***...
- 7,353