Questions tagged [halting-problem]

Question 1

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 ...

Question 2

The objective Find a program among all programs of length 13, that takes a great number of steps to terminate. The more steps, the better. The ideal solution is a 13-th busy beaver. Why 'a'? Because ...

Question 3

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 ...

Question 4

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, ...

Question 5

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-...

Question 6

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 ...

Question 7

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 <...

Question 8

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 ...

Question 9

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: \ ...

Question 10

Introduction Decide whether a Hexagony program composed solely of the characters .)_|\/><@ will halt using least bytes. Challenge Hexagony is a language ...

Question 11

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, ...

Question 12

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 ...

Question 13

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 ...

Question 14

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 ...

Question 15

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***...

Stack Exchange Network

Questions tagged [halting-problem]

How does the NSDT program end?

Maximize the number of steps a brainfuck program of length 13 takes to terminate

Will this makina program halt?

Will one-cell brainfuck halt?

Solve the halting problem for S combinatory logic

Concatenated halting problem: no + no + ... = yes

Determine if a dot(comma) program halts

Does this Foo machine halt?

Solve the Halting Problem for Modilar SNISP

Halting Problem for Simplified Hexagony

Generate all halting Smallfuck programs of length n

The Almost-Eternity Code [closed]

Solve the Halting Problem for Befinge

Confound my attempts to solve the halting problem

Partially Solve the halting problem for brainf***

Hot Network Questions