Questions tagged [halting-problem]
For problems pertaining to the whether or not an automaton will halt.
13 questions
8
votes
5
answers
780
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 ...
- 5,980
21
votes
5
answers
3k
views
Will one-cell brainfuck halt?
Brainfuck is an esoteric programming language that is Turing Complete, meaning you can't tell whether a given program will halt without running it. It's cell-based and has an infinite tape of cells, ...
- 44.2k
16
votes
2
answers
406
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-...
- 78.4k
39
votes
31
answers
4k
views
Concatenated halting problem: no + no + ... = yes
Challenge
Write \$2 \le n \le 10\$ distinct, valid non-halting full programs in your language of choice. If all of them are concatenated in order, the resulting full program should be a valid halting ...
- 78.4k
13
votes
2
answers
311
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 <...
- 18.9k
44
votes
15
answers
4k
views
Does this Foo machine halt?
Determining whether a Turing machine halts is well known to be undecidable, but that's not necessarily true for simpler machines.
A Foo machine is a machine with a finite tape, where each cell on the ...
- 3,187
12
votes
3
answers
473
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.5k
34
votes
2
answers
2k
views
Halting Problem for Simplified Hexagony
Introduction
Decide whether a Hexagony program composed solely of the characters .)_|\/><@ will halt using least bytes.
Challenge
Hexagony is a language ...
- 3,657
6
votes
2
answers
725
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.5k
1
vote
0
answers
257
views
The Almost-Eternity Code [closed]
Write a program that outputs as many characters as possible, with two conditions:
The program must be 256 bytes or shorter
The program must almost surely eventually halt. In other words, the only ...
- 1,582
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.5k
40
votes
2
answers
2k
views
Confound my attempts to solve the halting problem
Please note: By its nature, the spec for this challenge is difficult to understand. It probably requires at least a freshman course in computability theory, or equivalent background reading. In ...
- 7,332
10
votes
4
answers
994
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,265