Questions tagged [halting-problem]

For problems pertaining to the whether or not an automaton will halt.

Filter by
Sorted by
Tagged with
8 votes
5 answers
771 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 ...
Ginger's user avatar
  • 5,430
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, ...
emanresu A's user avatar
  • 37.2k
16 votes
2 answers
368 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-...
Bubbler's user avatar
  • 75.5k
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 ...
Bubbler's user avatar
  • 75.5k
13 votes
2 answers
306 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 <...
Rydwolf Programs's user avatar
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 ...
pommicket's user avatar
  • 3,137
12 votes
3 answers
465 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: \ ...
Esolanging Fruit's user avatar
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 ...
Weijun Zhou's user avatar
  • 3,637
6 votes
2 answers
713 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, ...
Esolanging Fruit's user avatar
1 vote
0 answers
251 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 ...
Alecto Irene Perez's user avatar
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 ...
Esolanging Fruit's user avatar
39 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 ...
N. Virgo's user avatar
  • 7,254
10 votes
4 answers
976 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***...
Christopher King's user avatar