text:
Counting characters
Write a function or program that accepts one character (or a string of length 1) as input, and outputs the number of times that character occurs inside the code.

This program must be a Proper Quine, only in the sense that it cannot, for example, read itself as a file, etc.

Input can be any character, printable or not. Output may be to standard out, or as a return value from a function. This is code golf, so the shortest submission in bytes wins. Good luck!

How can the program be a quine and at the same time output the number of times that the input character appears in the code? Those are contradictory output requirements, aren't they?

@LuisMendo When I made the suggestion above, I meant that solutions should not be allowed to read their own source code. I suppose I worded the suggestion poorly though

Related, but not a duplicate

FYI @mathjunkie's suggestion wasn't necessary because improper quines are a standard loophole

Arguably an empty program meets this criterion in some languages, if output is an exit code or interpreted as unary. Might want to ban those.

Are comments in the code allowed?

ASCII only, or the full range of Unicode characters as input?

@xnor Empty programs to questions tagged [tag:quine] are also a standard loophole

@Adam Abahot Is this your homework, or what?
Unless the only point is that it should be Quine, how has this not been Answered thousands of times before?

Case sensitive?

Python 2, 30 22 bytes
-8 bytes thanks to @Mukundan314
`'``*2.count'*2`.count

Try it online!

-8 bytes

@Mukandan314 Thanks, way to shave off 8 bytes!

COW, 711 519 504 390 387 bytes
moOMooMOOmOoMoOMoOMoOMoOMoOMoOMoOMOOmoOMOoMOoMOoMOoMOoMOoMOoMOoMOoMOoMOomOoMOomoomoOMMMMOOMOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOmOomooMMMMOOMOoMOoMMMmoOMoOMoOmoOMOomOomOoOOOmooMMMMOOmOoMoOMoOMoOMoOMOOmoOMOoMOoMOoMOoMOoMOoMOoMOomOoMOomoomoOMMMmoOMOomoOMoOmOomOoOOOmooMMMMOOMoOMoOMMMmoOOOOMoOMoOMoOmoOMOoMOomOomOoOOOmooMMMMOOmoOmoomoOMOOmoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOmOoMOomoomoOOOM

Try it online!
I appreciated a lot the previous solution (504 bytes) because it's deducted step by step, if you are interested please take a look at that in the timeline...
Now I furnish the program with a more "sensible" structure that promises to be less expensive (in terms of total byte count) but finding just a working set of values isn't simple...
To find the best, brute force comes in.
The next sections refers to the 390 bytes answer since it's simpler to explain that and then tell what it's done to save 3 bytes.
What it does
\$L = \{M,O,o,m\}\$ is the set of used chars and \$n_1,\dots ,n_4\$ their count.
The program has a structure that allows to form the output number \$n_i\$ as
$$
\begin{align}
n_i = x_i\times cf+y_i
\end{align}
$$
Furthermore we don't need to form \$x_i\$ and \$y_i\$ every time from zero, we reach them using the partial sums of 2 sequences occurring in cells [2] and [3] respectively.
[0]: multiplier for [1]     [1]: input-current_char     [2]: x_i     [3]: y_i

[1] = getchar()
if[1] { [1]-=77(M), [2]+=8, [3]+=0, cut[1] } paste[1]  //checks for 'M' and prepares its count
if[1] { [1]-= 2(O), [2]+=2, [3]+=0, cut[1] } paste[1]  //checks for 'O' and prepares its count
if[1] { [1]-=32(o), [2]-=1, [3]-=1, cut[1] } paste[1]  //checks for 'o' and prepares its count
if[1] { [1]+= 2(m), [2]-=6, [3]-=2, cut[1] } paste[1]  //checks for 'm' and prepares its count
if ![1]                                                //input was one of the letters above
    print [2]*13+[3]
else                                                   //input was something else
    print [4] (0)

As long as the input doesn't match any letter in \$L\$, [1] stays ≠ 0 and [2] and [3] hold \$x_i\$ and \$y_i\$ of the last tested letter.
Otherwise, if [1] has become 0, those value are no longer updated and at the end they will form the related \$n_i\$.
(When the input isn't a letter in \$L\$, after the 4 tests [1] is still ≠ 0 so the flow enters a loop ([>]) that sabotages the placement of the head, thus prevents from printing \$n_4\$ (the number of o).)
How
I've first constructed the exoskeleton: the complete program without the info about its char count.
That is without \$cf\$(common factor) and the 2 sequences that form \$x_i\$ and \$y_i\$.

The exoskeleton

    moo ]    mOo <    MOo -    OOO *    Moo .
    MOO [    moO >    MoO +    MMM =    oom o

    >.
    [  <+++++++[>-----------<-]>  > ? > ? <<  =*]=
    [             --              > ? > ? <<  =*]=
    [     <++++[>--------<-]>     > ? > ? <<  =*]=
    [             ++              > ? > ? <<  =*]=
    [>]
    >[> ? <-]>o

Some of them can be negative but I know that in order to write them I'll spend \$len\$: the sum of their absolute value in MoOs and MOos (+ and -).
Thanks to this condition the comptutation is rather straightforward.
Brute force

\$cf>0\qquad\qquad A=\{a_1,\ a_2,\ a_3,\ a_4,\ a_5,\ a_6,\ a_7,\ a_8\}\$

\$x_i=\sum_{j=1}^{i} a_j \qquad y_i=\sum_{j=5}^{4+i} a_j\$

\$n_i = x_i\times cf+y_i\$

\$len = cf + \sum_{j=1}^{8} |a_j|\$

$$
(*)\begin{cases}
n_1=|M|+len\\
n_2=|O|+len\\
n_3=|o|+len\\
n_4=|m|
\end{cases}
$$
Given the letter count in the exoskeleton \$|M|=71,\ |O|=97,\ |o|=85,\ |m|=38\$
we can now search for \$cf\$ and \$A\$ that satisfies \$(*)\$ minimizing \$len\$.
cf = 13, A = [8, 2, -1, -6, 0, 0, 1, -2] is the best for that exoskeleton (\$len=33\$)
Finished program
>.
[  <+++++++[>-----------<-]>  >  ++++++++  >      <<  =*]=
[             --              >     ++     >      <<  =*]=
[     <++++[>--------<-]>     >     -      >   +  <<  =*]=
[             ++              >   ------   >  --  <<  =*]=
[>]
>[>+++++++++++++<-]>o

As you can se when some \$a_i\$ is \$0\$ its relative pair of > < became non-functional. But obviously we can't take them off in retrospect.
-3 bytes, 387 bytes
Juggling with the exoskeleton I've found that there is one configuration slightly different that overall saves 3 bytes (1 instruction). What's different?

One * is replaced with [-] that has the same effect (+2 instr.)
Using one * \$x_4\$ is detached from the partial sum: \$x_4=a_4\$ (+1 instr.)
A pair of > < are saved because \$a_5=0\$ (-2 instr.)

The letter count of this exoskeleton is \$|M|=73,\ |O|=98,\ |o|=86,\ |m|=37\$
cf = 13, A = [8, 2, -1, 3, 0, -1, 1, -2] is the best. (\$len=31\$) (-2 instr.)

JavaScript (ES6),  40  38 bytes
A function made of 19 distinct characters used twice each.
_=>_.match`[\\]chmt[-a.02:=>?^^-]`?2:0

Try it online!
How?
The range going from [ to a allows us to match the backtick and the underscore, which are both already doubled in the code, without explicitly including them in the pattern.
This method comes with two minor drawbacks:

Because this range also includes ^, we need to insert it twice in the code as well although it's not part of the payload.
We also have to insert a second -.

Character set:
-.02:=>?[\]^_`achmt

JavaScript (Node.js), 54 bytes
y=>"3.>=includes(*)\\\"y3.>=includes(*)".includes(y)*3

Try it online!
A bit convoluted but I tried to avoid using f= that would violate the proper quine requirement. The code is written in the way that all characters occur exactly 3 times.

Pyth, 10 bytes
y/+N"y/+N"

Try it online!
Test cases
y/+N"y/+N"
    "y/+N"    String literal
  +N          Append the string `"`
 /            Count occurrences of the input in that string
y             Multiply by 2

Pyth has a quote built-in!?

@Λ̸̸ Yep! See this golfing tip

Stax, 12 bytes
".+#H".""+#H

Run and debug it
Takes as input a code point. Those provided in the test are for each character in the program, as well as their immediate predecessors and successors.
Explanation:
".+#H".""+#H
".+#H"          String literal ".+#H"
      .""       String literal "\"\""
         +      Concatenate
          #     Count occurrences of the input
           H    Double

Constructs a string of half the program, permuted somehow. Counts occurrences there, then doubles.

J, 34 bytes
(2*1#.=&'(2*1#.=&)+6*=&')+6*=&''''

Try it online!
how
                             single quote
         quoted program      adjustment
                |              /
        vvvvvvvvvvvvvvvv _____/___
(2*1#.=&'(2*1#.=&)+6*=&')+6*=&''''
^^^^^^^^                ^^^^^^^^^^
        \               /
         regular program

Everything above a ^ is part of the "regular program".
The rest is "the program quoted", but with one exception:

The quoted program doesn't include the program's single quote characters '

2*1#.=&'...' - Two times 2* the sum of 1#. the total number of times the input char matches a char in "the quoted program".  One for the actual program char, one for its quoted twin.
+6*=&'''' - Plus six times +6* the 1/0-indicator of whether the input char is equal to a single quote =&''''.  This is the hardcoded knowledge that there are 6 single quotes in the program.

Jelly,  12 10  8 bytes
-2 thanks to caird coinheringaahing (input is a character, not a string!)
“ḤṾċⱮ”Ḥċ

A monadic Link accepting a character that yields the count.
Try it online!
How?
“ḤṾċ”ḤṾċ - Main Link: character, c
           (A full program with a single character as input gives the main
            Link a list of characters - i.e. S = ['c'])
“ḤṾċ”    - list of characters = ['Ḥ', 'Ṿ', 'ċ']
     Ḥ   - double = ["ḤḤ", "ṾṾ", "ċċ"]  (Python strings)
      Ṿ  - un-eval = ['“', 'Ḥ', 'Ḥ', 'Ṿ', 'Ṿ', 'ċ', 'ċ', '”']
       ċ - count occurrences of c (in the un-eval-ed list)
         - implicit print (a list with a single entry just prints that entry)

-2 bytes by taking the input as a character literal (define the link as a function which takes a single character)

@cairdcoinheringaahing >.< left it as accepting a string from my initial checking and then forgot we should just take a character; thanks!

Charcoal, 20 bytes
Ｉ⊗№⁺´”´””yＩ⊗№⁺´´yＳ”Ｓ

Try it online! Explanation:
    ´”´”                Literal string `””`
   ⁺                    Concatenated with
        ”yＩ⊗№⁺´´yＳ”     Literal string `Ｉ⊗№⁺´´yＳ`
  №                Ｓ    Count matches of input character
 ⊗                      Doubled
Ｉ                       Cast to string
                        Implicitly print

Charcoal has two ways of quoting non-ASCII characters, ´ (which quotes a single character) and ”y...” (which quotes anything except ”). Trying to do everything with ´ is awkward because it uses too many of them; the best I could do was 26 bytes.

05AB1E, 14 bytes
Port of the Stax answer. ¢ is order-sensitive, which is fairly annoying here.
"„Js¢·"„""Js¢·

Try it online!
05AB1E, 18 bytes
As for this... I wrote this myself.
„…J…¢s·'„'D''DJs¢·

Try it online!
Explanation
„…J                 2-char string. …, J
   …¢s·             3-char string. ¢, s, ·
       '„           1-char string. „
         'D         1-char string. D
           ''       1-char string. '
             D      Copy this character.
              J     Join the stack.
               s¢   Count occurances of the input in the string.
                 ·  Multiply the count by 2. (Perfectly makes the 0-count still 0.)

Brachylog, 18 bytes
∈"∈∈\\\"∧33||"∧3|∧

Try it online!
Brachylog doesn't really have any good way to get quotes without escaping them in a string literal (or using the Ṭ constant, which came out longer when I tried it), so the approach I came to is to simply triple down on everything else.
(I don't know why the testing header runs out of stack after it's done every test case; I'd think it's something to do with the unbound variable output for 0 but it works fine on individual inputs... so long as an unbound variable is indeed an acceptable way to give 0. If it's not, +3 bytes)

Python 3, 48 bytes
x="(x+2*chr(34)+'x=;f=eval(x)').count";f=eval(x)

Try it online!
Idea: Store code in string. The stored code returns function that counts characters in the string within which it is contained. Evaluate the string to get the function. Special care for characters wrapping the string.
Python 3 without eval I, 48 bytes
 lambda c:3*(c in" \\\"(())**33::abbcddiillmmnn")

Try it online!
Python 3 without eval II, 124 bytes
And a more creative, but much longer solution:
lambda c:[0o3623>(ord(c)-76)**2>195,' !!""##$$%%&&++,-..//4457889:;;==ZZ\\^^__``beeffgghhiijjkklmnnppqqrssttuuvvwwxx'][0]<<1

Try it online!
Idea: Ensure all characters that satisfy a certain equation (195 < (c-76)² < 1939) appear exactly twice in the code, and return 2 for those characters (0 for all others). Maybe someone can think of a better compression for the long string, but remember expressing it may only use the same character twice.

Hello and welcome to PPCG; nice first post. For testing, I would add an assertion such that one does not have to manually compare all character counts: TIO.

perl, 128 bytes, assuming ASCII input only
print 1;#!"$%&'()*+,-./023456789:<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghjklmoqsuvwxyz{|}~...

Replace the trailing ... with the 33 unprintable characters (ASCII 0 .. ASCII 31 + ASCII 127), with the newline at the end. (If anyone knows how to put unprintable characters in a textfield and have them show up here, I'm all ears).

R, 96 82 126 94 90 bytes
3*sum(unlist(strsplit(c('"',"#'''((()))*,,3=acilmnprsssttu"),''))==scan(,''))##()*,3amprst

Try it online!
Edit1: thanks to math junkie for pointing-out a horrible bug in the original version (the \ character): hence the temporary increase and subsequent decrease in byte-length, as successive patches were added in panic..
Edit2: -4 bytes: Copying the entire program into the 'look-up' string seemed wasteful (94 bytes), so instead added extra characters so that every character was present an even-number of times, and now just include half the program (character-wise) in the look-up string

Ouch!  Good call!  I'm working on it...  hoping that this won't cost another 41 bytes to resolve...

...cost 12 bytes, so better than worst-case scenario, at least...

No idea if this would help, but you can use "\x5c" for a backslash \\. Would require a significant rework, no doubt.

J, 24 bytes
2*1#.0 :0=[
2*1#.0 :0=[

Try it online!
The second newline counts too, so it's not 23.

Retina 0.8.2, 26 bytes
T`Tan[-a\]\n^0__-`2
[^2]
0

Try it online!
I got the idea to use [-a from @Arnauld's JavaScript answer.
Explanation
T`Tan[-a\]\n^0__-`2

Transliterate each of the following characters into a 2:

The letters T, a, and n
The range [-a which also includes \, ], ^, _, and `
Literal ] and literal newline
The characters ^, 0, _, and -

[^2]
0

Replace any character that is not a 2 with a 0

Perl 5 + -plF, 49 bytes
$_=q($_=grep/\Q@F/,qq(\$_=q($_);eval)=~/./g);eval

Try it online!
Explanation
Pretty much the standard quine with some minor changes.
The program itself is stored in $_ which is evaled (eval - along with most other functions - works on $_ by default if no argument is specified. When the program is evaluated, $_ is set to the number of matches (~~grep) against the input char /\Q@F/, which is interpolated at runtime and necessitates \Q to escape any special chars, against the list of chars resulting from the template string $_=q(...);eval with the actual program interpolated in the innermost %_, which is obtained with =~/./g (this returns a list of all the chars that matches the regex, . being match-all).

Husk, 10 bytes
D#hs"D#hs"

Try it online!
D             Twice
 #            the number of occurrences of the input in
    "D#hs"    "D#hs",
   s          quoted,
  h           without the second quote.

For the same number of bytes:
Husk, 10 bytes
#S+s"#S+s"

Try it online!
Somewhat boring adaptation of the standard S+s"S+s+ quine.

Retina, 1 byte
1

Try it online!
Counts the number of 1s in the input, so the output is always 1 or 0.
Inspired by this answer on a related question.

Ruby -nl, 40...32 28 bytes
p~/[,-2\[-\]p~,..011?:]/?2:0

Try it online!
Derived from my answer to a related challenge. Each of the 14 distinct characters in the code appears twice. The input is tested against a regexp. The outer [] is a character class containing literal characters plus two character ranges: ,-2 is equivalent to the literal characters ,-./012 and \[-\] is equivalent to the literal characters [\]. The code prints 2 if the regexp matches the input character; 0 is printed otherwise.

C (gcc), 303 bytes
n[4467]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,1,0,0,3,3,0,0,126,0,0,0,92,15,17,2,2,2,2,2,0,1,0,2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,2,0,0,0,2,0,1,1,1,1,1,1,2,0,0,0,1,5,0,1,0,2,0,2,0,0,0,0,0,0,2,0,2};main(){printf("%d\n",n[getchar()]);}

Try it online!

174 bytes

Japt, 16 bytes
"UèiQÑ )"iQ èU)Ñ

Try it
Takes inspiration from the normal Japt quine. Essentially, counts the number of occurences in the string at the beginning (with a quote), then doubles it.

Whitespace, 144 bytes
[S S S N
_Push_0][S N
S _Duplicate_0][S N
S _Duplicate_0][T   N
T   S _Read_STDIN_as_character][T   T   T   _Retrieve_input][S N
S _Duplicate][S S S T   S S S S S N
_Push_32][T S S T   _Subtract][N
T   S S N
_If_0_Jump_to_Label_SPACE][S N
S _Duplicate][S S S T   S S T   N
_Push_9][T  S S T   _Subtract][N
T   S T N
_If_0_Jump_to_Label_TAB][S S S T    S T S N
_Push_10][T S S T   _Subtract][N
T   S S T   N
_If_0_Jump_to_Label_NEWLINE][N
S N
N
_Jump_to_Label_PRINT][N
S S S N
_Create_Label_SPACE][S S S T    S S T   S T T   N
_Push_75][N
S N
N
_Jump_to_Label_PRINT][N
S S T   N
_Create_Label_TAB][S S S T  S S S S T   N
_Push_33][N
S N
N
_Jump_to_Label_PRINT][N
S S S T N
_Create_Label_NEWLINE][S S S T  S S T   S S N
_Push_36][N
S S N
_Create_Label_PRINT][T  N
S T _Print_as_integer_to_STDOUT]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.
Try it online (with raw spaces, tabs and new-lines only).
Explanation in pseudo-code:
Character c = STDIN as character
If(c == ' '):
  Print 75 to STDOUT
Else-if(c == '\t'):
  Print 33 to STDOUT
Else-if(c == '\n'):
  Print 36 to STDOUT
Else:
  Print 0 to STDOUT

This sounds pretty straight-forward, but it was reasonably tricky to get the correct numbers. Pushing a number in Whitespace is done as follows:

S: Enable Stack Manipulation
S: Push number
S/T: Positive/negative respectively
Some T/S followed by a single N: Decimal as binary, where T is 1 and S is 0

So, after I created the template of my program, the amount of newlines were fixed and I could simply print 36 in that case.
But the amount of spaces and tabs are variable. If I correct the count-output of the amount of spaces, the tabs would be incorrect, and vice-versa. This required some tweaking, which I eventually did without wasting any bytes by using a Label ST for the Label_NEWLINE. Usually I create Labels in the following order, based on the amount of times it's used: (empty label); S; T; SS; ST; TS; TT; SSS; etc. In this case, I've skipped the SS and used ST instead, allowing me to print 75 and 33 with the binary pushes of TSSTSTT and TSSSST for the counts of spaces and tabs respectively.

Turing Machine Code, 95 bytes
I'm not sure this counts, and if so deemed, I'll make it non-competing (or delete it if you guys think it's too egregious). The reasons why have to do with the Turing Machine Code interpreter I'm using. This affects the space character ( ), asterisk (*), and semi-colon(;).
Space character
Basically it internally converts space characters into underscores '_'. Also, it interprets the lack of any character as a space character, and therefore interprets that as an underscore. Not only this, but it also interprets an actual underscore '_' as an underscore (or space, or lack of a character). Since the input is strictly limited to the text box on the web page, this means there is significant ambiguity as to how to count a space character. So that character will not work with this code. Any attempts at trying to fudge something here could easily and reasonably be discounted as wrong by atleast 3 different valid interpretations that I can come up with off the top of my head.
Asterisk
This character is set aside for a few special uses, depending on where in the code it's used. Most relevantly for this challenge, the asterisk - when used as an input check - acts as a special catch-all character. So any attempt at trying to catch this as input, catches anything and everything, including the aforementioned space character. It does so without any ability to discern an actual asterisk from the infinite possibilities. So that character will not work with this code.
Semicolon
Lastly, the semicolon is a very strict line comment. You put that anywhere in that line of code, and that's it. Everything after it (inclusive) on that line is interpreted as a comment, and is ignored. As a result of this, this Turing Machine interpretor will never be able to 'read' the semicolon character ';'. So that character will not work with this code.
0 0 1 r 0
0 _ 2 * 2
0 r 7 * r
0 7 3 * r
0 2 7 * 2
0 3 5 * r
0 1 2 * r
0 5 3 * r
0 * 0 * 2;3325_

Try it online!
I'm deeply suspicious that there is a two or three line solution to this. I'll probably play around with this for a bit some more. Having to use a comment to pad the numbers really sets off a flag in my head that this code could accomplish this task far more efficiently.

FYI, you cannot "make an answer non-competing" to save it from being deleted. Either this answer is valid, or it needs to be deleted, there's no middle ground (I don't understand this programming language well enough to judge)

@pppery. Agreed. Hence my explanation.

Vyxal, 12 8 bytes
`I$O`I$O

Try it Online!
Back then, there was no quine cheese. Now there is.
Explained
`I$O`I$O
`I$O`    # The string "I$O"
     I   # surrounded in backticks and appended to itself
      $O # Get the count of the input in that.


text:
Reverse busy beaver problem
In this challenge, Turing machines operate on a zero-initialized binary tape that is infinite in both directions.
You are given an integer \$N\$, where \$1 \le N \le 20000\$. Your program has to output a Turing machine that takes exactly \$N\$ steps to halt, including the final step. Alternatively, you can write a program that outputs all 20000 machines.
Your program should complete within 2 hours for all 20000 inputs, when tested on my computer (AMD Ryzen 2600 12-thread CPU). If your program solves all test cases on the same thread, sequentially and independently, your program's running time is divided by 4.
Your score is the total number of states in all 20000 outputs of your program. The lowest-scoring program wins.
Output
Below is described the (recommended) output format for a single test case.
In the first line, output a number \$M\$, the number of states of the machine. In the next \$M\$ lines, output the transitions from the states, in order from the first to the last, if the cell under the pointer is zero. In the next \$M\$ lines, output the corresponding transitions, if the cell under the pointer is one.
The output format for transitions is movement newval newstate, where movement stands for either L - move left, R - move right, S - do not move, or H - halt, newval is the new value of the cell under the pointer (it can be equal to the original one), and newstate is an integer from \$1\$ to \$M\$, the state the machine will be in in the next step.
Python 3 checker that inputs in the format described above and outputs the number of steps the Turing machine takes to halt. If you use a different output format, please include a link to a program that can  be used to simulate your Turing machines (it's likely a good idea to simply modify my checker).

Deleted sandbox post

Related OEIS sequence.

@Arnauld re: the oeis seq, is the machine in this question 3-tuple? Is it similarly difficult to compute min required states for larger numbers?

@Jonah Aren't 3-tuple and 5-tuple two different notations describing the same machines? What really matters here is the number of states, not the number of rules. (Incidentally, all solutions given in this link from the OEIS sequence contain 2 transition rules per state anyway, even if one of them is never used.)

@Arnauld Thanks for clarifying

@Jonah I should add that I'm not familiar with Turing Machine notations and that this 5-tuple Turing machine in the OEIS definition puzzled me as well. I don't quite understand why they put it in there. The fact that it's a 2-symbol machine is all that should matter here.

@mypronounismonicareinstate To clarify, the idea is that we’d create an algorithm to cleverly search a subset of the possible programs to find a small one meeting “halts in N” requirement?  The “sequentially and independently” rules out searching all of them at once and saving for N whenever we stumble on a small state program that happens to stop in N?

@Jonah it doesn't rule all other approaches out: it just means that programs that could be trivially made multithreaded do not suffer a severe penalty (or am I misunderstanding you?)

I feel like any competitive program for this would just be a long precomputed list of optimal Turing machines. Iterate through a bunch of small machines, running them for 1000 steps each, recording for each N the smallest machine that runs for exactly N steps. Doesn't matter if it takes more than an hour to compile the list of machines, once the list is hardcoded into a program it's trivial and fast to output list[N] given N.

@Magma So the optimal output is computable. That is a huge problem with the challenge that I somehow didn't notice and was not pointed out in the sandbox, and I have no idea what to do now.

You could increase the upper limit for N until precomputation becomes unfeasible. To discourage people from precomputing machines for small N anyway, you can increase the lower limit too.

@myp I remember mentioning the problem of hardcoding in the sandbox post. ..?

@user202729 It seems you actually did, but I didn't notice that the outputs are actually computable. With the current upper bound, that approach is impractical, though.

Python 3, 275,467 255,540 states
Thanks @mypronounismonicareinstate for suggesting to add \$I\$ into the \$B \rightarrow C\$ loop, which ultimately saves about \$20k\$ states.
def print_machine(states):
 print(len(states[0]))
 for i in 0,1:
  for s in states[i]:
   # if s is None (state unused), puts dummy value in there
   move, new_val, new_state = s or ["H", 0, 0]
   print(move, new_val, new_state+1)

# simple machine that uses ceil(step/2) states
# used for small cases
def generate_simple_machine(steps):
 n_states = (steps+1)//2
 # states[cur_char][state_id]
 states = [[], []]
 for i in range(n_states):
  states[0].append(["S", 1, i])
  states[1].append(["S", 0, i+1])
 states[1][-1][0] = "H"
 if steps%2==1: states[0][-1][0] = "H"
 return states

BASE_STEPS = [(1<<i+2)-i-3 for i in range(20)]
BASE_STEPS[0] = -999

def generate_counter_machine(steps, do_print=True):
 # how many bits/states needed?
 for n_bits, max_steps in enumerate(BASE_STEPS):
  if max_steps > steps:
   break
 n_bits -= 1
 n_states = n_bits + 2
 extra = steps - BASE_STEPS[n_bits]
 if extra >= (1 << (n_bits+1)):
  n_states += 1

 # if small number of steps, use simple machine
 n_states_simple = (steps+1)//2
 if not do_print:
  return min(n_states_simple, n_states)
 if n_states >= n_states_simple :
  states = generate_simple_machine(steps)
  print_machine(states)
  return n_states_simple

 # states[cur_char][state_id]
 # use 0 indexed state
 states = [[None]*n_states, [None]*n_states]

 # state indices
 I_STATE  = 0
 B_STATE  = 1
 E_STATE  = n_states - 1
 C_STATES = [i+2 for i in range(n_bits)]

 # initial state
 states[0][I_STATE] = ["R", 1, C_STATES[0]]
 states[1][I_STATE] = ["H", 0, 0]  # not used initially

 # go back state
 states[0][B_STATE] = ["L", 0, B_STATE]
 states[1][B_STATE] = ["R", 1, C_STATES[0]]

 # ith-digit check states
 for i in C_STATES:
  states[0][i] = ["L", 1, B_STATE]
  states[1][i] = ["R", 0, i+1]
 states[1][C_STATES[-1]][0] = "H"

 # dealing with extras
 # first, figure out how many half-state
 # goes between B_1 -> C1_x
 t = 1<<n_bits
 q1 = t - 1
 q2 = q1 + t
 q3 = q2 + t
 if  extra < q1:
  extra_state = I_STATE
 elif extra < q2:
  # connect B_1 -> I_0 -> C1_?
  states[1][B_STATE] = ["S", 0, I_STATE]
  extra -= q1
  extra_state = I_STATE
 elif extra < q3:
  # connect B_1 -> I_0 -> I_1 -> C1_x
  states[1][B_STATE] = ["S", 0, I_STATE]
  states[0][I_STATE] = ["S", 1, I_STATE]
  states[1][I_STATE] = ["R", 1, C_STATES[0]]
  extra -= q2
  extra_state = E_STATE
 else:
  # connect B_1 -> I_0 -> I_1 -> E_0 -> C1_x
  states[1][B_STATE] = ["S", 0, I_STATE]
  states[0][I_STATE] = ["S", 1, I_STATE]
  states[1][I_STATE] = ["S", 0, E_STATE]
  states[0][E_STATE] = ["R", 1, C_STATES[0]]
  extra -= q3
  extra_state = E_STATE

 # then put a half-state between Cx_0 -> B
 # if needed
 if extra > 0:
  states[1][extra_state] = ["L", 1, B_STATE]
  for i in reversed(C_STATES):
   if extra%2==1:
    states[0][i] = ["S", 1, extra_state]
   extra //= 2
 print_machine(states)
 return n_states

Try it online! or Verify all machines from 1 to 20k
Big idea
We want to construct a Turing machine that has a large time complexity compared to the number of states. In this answer, I used a binary counter to count all integers with \$n\$ bits, which has a time complexity of \$O(2^n)\$. The binary counter was chosen because it is very simple to construct, easy to scale, and flexible enough to add any small number of steps.
Binary counter
Let's say we want to count all integers with 4 bits. The tape layout will be as follows:
1 x x x x
e.g.
1 0 0 0 0
1 1 0 0 0
....
1 0 1 1 1
1 1 1 1 1

where the left most 1 is used to mark the start of the number, and xxxx is the current number in binary, in reverse order (the least significant bit first). We start with 10000, and end with 11111.
At each cycle, we increase the number by 1 as follows:

Find the left most 0. E.g.

1 1 1 0 1
      ^

Set that digit to 1, and all previous digits to 0. The previous example becomes 1 0 0 1 1.

We then repeat these steps until the tape is 1 1 1 1 1.
Binary counter Turing machine
The counter machine for \$b\$-bit integers will have \$b+2\$ states: the initial state \$I\$, \$b\$ digit check states \$C_1\$ to \$C_b\$, and the "go back" state \$B\$:

The initial state \$I\$ simply sets the left most cell to 1: R 1 C1 / x x x.

The \$i^{th}\$ digit check state \$C_i\$ is only called if all previous digits are 1, and the pointer is currently on the \$i^{th}\$ left most digit.

If the current digit is 0, then we've found the left most 0. Set the current digit to 1, and enter "go back" state: L 1 B.
If the current digit is 1, set that digit to 0 and enter the next digit check state: R 0 C(i+1). If this is the last digit check state (\$C_b\$), then halts, since this means the current number is 111..1.

"Go back" state \$B\$ is called after the number is incremented, to reset the pointer to the unit digit and start a new cycle. This state simply moves left until it sees the 1 that marks the start of the number. It then moves one step right to the unit digit, and calls the first digit check state \$C_1\$: L 0 B / R 1 C1.

Time complexity
With \$n\$ states (counting \$n-2\$ bit integers), a counter machine runs for \$2^n-n-1\$ steps.
states  steps
     3      4
     4     11
     5     26
     6     57
     7    120
     8    247
     9    502
    10   1013
    11   2036
    12   4083
    13   8178
    14  16369
    15  32752

Bridging the gap
The above scheme only allows us to generate machines with the exact number of steps in the table above. This means that we are stuck if the number of steps falls in the "gaps" between the above numbers. Thankfully, there is a simple scheme that allow us to add some extra steps to a machine, at the cost of at most 1 state.
For example, from the above table, we know that a counter with 6 states runs for 57 steps, and a machine with 7 states runs for 120 steps. There are 62 numbers in the gap between them (58 to 119). This means that we need to be able to extend a 6-state machine to have 1 to 62 extra steps. (In general, we need a scheme to extend an \$n\$-states machine by 1 to \$2^n-2\$ steps).
First, some notation: let's \$S^0\$ and \$S^1\$ be the "half-states" of \$S\$, aka \$S\$ when the current cell is 0 or 1.
Let's look at how many time each half-state is called in an original 6-state counter machine:
                I    B   C1   C2   C3   C4
cur_char = 0    1   11    8    4    2    1
cur_char = 1    0   15    8    4    2    1

Observation 1
The number of times each digit check half-state is called is always a power of 2. Furthermore, the transition afterward is always \$C_i^0 \rightarrow B^x\$ (refer to the state transition diagram above). This means that we can add an extra half-state in between (aka \$C_i^0 \rightarrow X \rightarrow B^x\$). The extra half-state simply wastes a step before transitioning to \$B\$. The number of extra steps gained is equal to the number of times \$C_i^0\$ is called.
By selecting which \$C_i^0\$ are connected to this extra half-state \$X\$, we can add any number of extra steps from 1 to 15 (since \$15=8+4+2+1\$), at the cost of 1 extra half-state.

For example, in the modified counter above, \$C_1^0\$ and \$C_3^0\$ transitions through \$X\$ before reaching \$B\$. Since \$C_1^0\$ is called 8 times and \$C_3^0\$ is called 2 times, \$X\$ is called 10 times in total, adding an extra 10 steps to the machine.
Observation 2:
Both \$B^1\$ and \$I^0\$ transitions to state \$C_1\$. Furthermore, both \$B^1\$ and \$I^0\$ sets the current cell to 1, then moves right. Thus, we can have \$B^1 \rightarrow I^0 \rightarrow C_1^x\$. This gives us an extra 15 steps for free.
Furthermore, for each additional half-state inserted between \$I^0\$ and \$C_1^x\$, the machine runs for 16 extra steps. For example, using 2 extra half-state, we can gain \$15+16+16=47\$ extra steps.
By combining the 2 observations, we can reach any number of extra steps between 1 and 62 inclusive, using at most 3 extra half-states (1 half-state in observation 1, 2 in observation 2, which gives at most \$15 + 47 = 62\$ extra steps).

For example, in the machine above, \$I^0\$ and 2 extra half-states are added between \$B^1\$ and \$C_1^x\$, adding \$15+16+16 = 47\$ extra steps. Another extra half-state is added between the digit checks and \$B\$, adding 10 extra steps. In total, this machine has 57 extra steps compared to the base machine.
This process can be generalized to any \$n\$-state counter machine.
Note that since \$I^1\$ is unused in the base machine, we already start with a free half-state. This means that we only need at most 1 extra state \$E\$ (aka 2 half-states \$E^0\$ and \$E^1\$).
Code explanation
If you want to take a look at the code, the states are ordered as follow:

Initial state \$I\$
Go back state \$B\$
Digit check states from \$C_1\$ to \$C_b\$
Extra state \$E\$ (if needed)

I get the same total number of states, and this does not even time out on TIO, and I also tested some machines to confirm they are correct; this seems valid to me.

I can't wait to see this explanation. I had a go at this but for instance 19996 takes me 28 states instead of 15.

@Neil I have added an explanation, hopefully it makes sense. Feel free to suggest improvements if you think it's still confusing.

Is it possible to use the initial state as the first extra state? (e.g. C1 notices a zero and depending on the "delay" needed it either proceeds to B or sets to 1, proceeds to I, then I sets to 0 and proceeds to B; I'm not sure whether this would work)

@mypronounismonicareinstate That's a great idea! It doesn't work right now since I moves right before calling B, but I will look into some modification.

Aha! It was that sneaky extra state that I couldn't puzzle out. Thanks!

@mypronounismonicareinstate Turn out having $C_i \rightarrow B \rightarrow I \rightarrow C_1$ adds a ton of extra steps for free, which completely eliminate the need for the $2^{nd}$ extra state.

@mypronounismonicareinstate Thanks for the bounty!

Python 2, 265426 255462 states
t = 0
for i in range(1, 20001):
 b = bin(i + 3)[2:]
 if i < 5: t += -~i / 2
 else: t += len(b) - (not int(b[1:])) - (not int(b[1]))
print t
print
n = input()
if n < 5:
 m = -~n / 2
 print m
 for i in range(m): print "S" if i * 2 < n - 1 else "H", 1, i + 1
 for i in range(m): print "S" if i * 2 < n - 2 else "H", 0, -~i % m + 1
else:
 b = bin(n + 3)[2:]
 e1 = int(b[1:]) and 2
 e2 = int(b[1]) and 3
 m = len(b) - (not e1) - (not e2)
 print m
 for i in range(m):
  if i == e2 - 1:
   if int(b[2]): print "S", 1, 3
   else: print "R", 1, 4
  elif i == e1 - 1: print "L", 0, 1
  elif i:
   if int(b[i - m]): print "S", 0, 2
   else: print "L", 0, 1
  elif int(b[1:3]): print "S", 1, 2
  else: print "R", 1, 1 + max(1, e1)
 for i in range(m):
  if i == m - 1: print "H", 0, 1
  elif i == e2 - 1: print "R", 1, 4
  elif i == e1 - 1:
   if e2: print "S", 0, 3
   else: print "R", 1, 3
  elif i: print "R", 0, i + 2
  else: print "L", 1, 1

Try it online! I was trying to come up with a different binary counter that didn't need @SurculoseSputum's initial state, but I then forgot about it, which is why this post is so late. Thanks to his help I was able to remove 9964 states so it's now actually slightly better than his answer. It's based on a basic machine of \$ m \$ states that takes \$ 2 ^ { m + 1 } - 3 \$ steps. The following states are created:

A "go back" state.
An optional state that is divided into two half states:

An extra half state to drop into state 1 more slowly so that up to \$ 2 ^ { m - 1 } - 1 \$ extra steps can be added.
An extra half state before the first digit state which adds \$ 2 ^ { m - 1 } \$ extra steps.

An optional state that is divided into two half states, one or both of which are inserted before the first digit state to add a further \$ 2 ^ { m - 1 } \$ or \$ 2 ^ m \$ extra steps.
A number of bit counter states.

Note: It's technically possible to save a further state for values of the form \$ 3 \left ( 2 ^ m - 1 \right ) \$ but as it only saves 11 states I haven't bothered to code this up yet.

Nice approach! You can get $227,290$ states: The base machine with $n$ states runs in $2^{n+1}-3$ steps. Hooking an extra half-state after the bit counter states (when char = 0) gets us from 0 to $2^{n-1}-1$ extra steps. Hooking a half-state after the go back state, when char = 0 gets us $2^{n-1}$ extra steps. Thus, 1 extra state adds from 0 to $2^n$ extra steps (1 half state after go back, and 1 half state after go back or bit counter states). 2 extra states add $2^n+1$ to $2^{n+1}-1$ steps (2 or 3 half-states after go back, and 1 half-state after the bit counters).

@SurculoseSputum I think I broke something when I added the extra states; I should be able to do 29 steps in 4 states, shouldn't I...

(Correcting the code saved me 46 states.)

@SurculoseSputum I was already toying with the idea of handling $ 0 $ to $ 2 ^ {n - 1} - 1 $ extra steps using half a state, as that would save on the extra state for odd numbers, but it didn't occur to me to adapt it to include for all extra steps like that! I love it, I just need to work out how to code it now.

@SurculoseSputum I've tried to implemented your suggestion, and so far it does now undercut your score slightly, but it's nowhere near your suggestion. Have I missed something?

I was just dumb... forgot to add in the extra states in my calculation :P

C++, score need testing
#include <stdio.h>
#include <thread>
#include <chrono>
#include <random>
#include <bitset>
#include <atomic>
#include <string.h>
#include <map>
// N = space of each buf, D = Amount of threads - 2, TIME = allowed time(ms), W = MaxOut
const int N = 50, D = 16, TIME = 7200 * 999, W=20000;
struct strat {int n, w, m;} mem[D][W+1][N][2];
int res[D][W+1], spl[W+1];
std::atomic_ullong cnt;
volatile bool timeout;

void putStrat(int i, int det=0, int then=-1) { //fprintf (stderr, "%6d%5d%4d%6d\n", i, det, then, spl[i]);
    // printf ()
    if (spl[i] && then<0) { //printf ("(%d=%d+%d)", i, spl[i], i-spl[i]);
        putStrat(spl[i], det, det + res[0][spl[i]]); //fprintf (stderr, "a");
        putStrat(i-spl[i], det + res[0][spl[i]], then); //fprintf (stderr, "b");
        return;
    }
    int n = res[then==-1][i]; //fprintf (stderr, "c");
    strat (*x)[2] = mem[then==-1][i];
    if (n>9999) {
        printf ("Not Found(%d,%d,%d)",i,det,then);
    } else
    for (int i=0; i<n; ++i) {
        int d0 = x[i][0].n<0 ? then : x[i][0].n+det;
        int d1 = x[i][1].n<0 ? then : x[i][1].n+det;
        printf ("[%2d %c %c|%2d %c %c]",
                d0, "01"[x[i][0].w], "LSR"[x[i][0].m],
                d1, "01"[x[i][1].w], "LSR"[x[i][1].m]);
    }
}
int run(strat (*A)[2]) {
    int p = W+4, i=0;
    int cur_state = 0;
    std::bitset<W*2+8> Q;
    for (i=0; ++i<W+1; ) { //fprintf (stderr, "%d %d %d%d%d%d%d%d%d%d\n", cur_state, p, (int)Q[1020], (int)Q[1021], (int)Q[1022], (int)Q[1023], (int)Q[1024], (int)Q[1025], (int)Q[1026], (int)Q[1027], (int)Q[1028]);

        auto& o = A[cur_state][Q[p]];
        cur_state = o.n;
        if (cur_state == -1) break;
        Q[p] = o.w;
        p += o.m-1;
    }
    return i;
}
void fallbackGen(int k, int v) {
    strat A[100][2];
    A[0][0] = {4,1,2};  A[0][1] = {3,1,2};
    A[1][0] = {2,1,0};  A[1][1] = {3,0,2};
    A[2][0] = {-1,0,2}; A[2][1] = {1,1,0};
    A[3][0] = {1,0,0};  A[3][1] = {0,1,2};
    //A[4][0] = {5,1,2};
    //A[5][0] = {6,1,2};
    //A[6][0] = {1,1,2};
    for (int i=4; i<k; ++i) {
        A[i][0] = {i+1, i%2?1:1&(v>>(k-i)/2), 2};
        A[i][1] = {-1,0,2};
    }
    A[k-1][0].n = 1;
    int r = run(A);
    for (int i=3; i<k; ++i) {
        if (r>W) return;
        if (k<res[1][r]) {
            res[1][r] = k;
            memcpy (mem[1][r], A, k*sizeof(*A));
        }
        ++r;
        if (i==3) {
            A[2][0].n = 4;
        } else {
            A[i][1].n = i+1;
        }
    }
    { r+=2;
        if (r>W) return;
        A[k][0] = {-1,0,0};
        A[k][1] = {k-1,0,2};
        ++k;
        if (k<res[0][r]) {
            res[0][r] = k;
            memcpy (mem[0][r], A, k*sizeof(*A));
        }
    }
}
void fallbackGene() {
    mem[0][1][0][0] = {-1,0,0}; res[0][1] = 1;
    mem[0][2][0][0] = {0,1,1}; mem[0][2][0][1] = {-1,0,0}; res[0][2] = 1;
    for (int k=5; k<32; k+=2) {
        for (int v=0; v<std::min(W,1<<(k-1)/2); ++v) {
            fallbackGen(k, v);
        }
    }
}
void f(int d) {
    std::mt19937 R(d);
    for (; !timeout; ++cnt) {
        strat A[N][2];
        static const int Coll[] = {1,2,3,4,4,5,5,5,5,6,6,6,10};
        int n = Coll[(unsigned)R()%13];
        for (int i=0; i<n; ++i) {
            for (int j=0; j<2; ++j) {
                A[i][j].n = (unsigned)R() % n;
                A[i][j].w = (unsigned)R() % 2;
                A[i][j].m = (unsigned)R() % 8 ? (unsigned)R() % 2 * 2 : 1;
            }
        }
        int halt_state = (unsigned)R() % N;
        int halt_bin = (unsigned)R() % 2;
        A[halt_state][halt_bin].n = -1;
        int i = run(A);
        if (i<W+1 && res[d][i]>n) {
            res[d][i] = n;
            memcpy (mem[d][i], A, n * sizeof(*A));
        }
    }
}
int main() {
    freopen ("unBB.txt", "w", stdout);
    memset(res, 1, sizeof(res));
    std::thread A[D];
    A[1] = std::thread(fallbackGene);
    for (int i=2; i<D; ++i) A[i] = std::thread([i](){f(i);});
    std::this_thread::sleep_for(std::chrono::milliseconds(TIME));
    timeout = 1;
    for (int i=1; i<D; ++i) A[i].join();
    printf ("%llu Tries\n", (unsigned long long)cnt);

    int s=0;
    setvbuf (stdout, 0, _IONBF, 0);
    for (int i=1; i<W+1; ++i) {
        int m=0x7fffffff; strat (*x)[2]; //fprintf (stderr, "p");
        for (int j=0; j<D; ++j) {
            if (res[j][i] < m) {
                m = res[j][i];
                x = mem[j][i];
            }
        }//fprintf (stderr, "q");

        if (mem[1][i] != x && m<9999) {
            res[1][i] = m;//fprintf (stderr, "%d", m);
            memcpy (mem[1][i], x, m*sizeof(*x));
        }//fprintf (stderr, "r");
        for (int j=1; j<i; ++j) {
            if (res[0][j] + res[1][i-j] < res[1][i]) {
                res[1][i] = res[0][j] + res[1][i-j];
                spl[i] = j;
            }
        }//fprintf (stderr, "s");
        printf ("%6d %6d ", i, res[1][i], res[0][i]);
        putStrat(i);
        puts("");
    }
    return s;
}

Build with blocks that run some steps leaving the tape empty

From my testing with heavily reduced maximal time, this only finds solutions for some very small numbers (the largest number found is 118 and the second largest is 71, in 2.5 million tries), so I don't think this finds significantly more solutions in the full 2 hours.

In ten times as much time (12 minutes, 31M tries), the largest number found is still less than 200.

@mypronounismonicareinstate Tested running for 2s(but outputting cost more time), score is 1446775

10s, 1318414, actual time 49.768s

Seems to be some bugs when building

Do the bugs affect the score? (asking to determine whether I should start testing)

I don't know, just wait now

@mypronounismonicareinstate Hope this work but you'd better try with small time first

Assuming I am using awk correctly (code: {sum += $2}; END { print sum }), the result is 1067459 with 754153839 tries. Would an additional check that all states in the machine are reachable before running it help?

I think it is also possible to compose the machine by first adding some blocks that leave the tape empty, and then appending one that doesn't necessarily do that.

Python 2, 75012500 states
n = input()
m, l = n / 8, n & 7
print m * 3 + [0, 1, 1, 2, 2, 3, 2, 3][l]
for i in range(m):
 print "L", 1, i * 3 + 2
 print "R", 1, i * 3 + 1
 if l or i + 1 < m:print "R", 0, i * 3 + 4
 else:print "H", 0, i * 3 + 3
if l == 7:
 print "L", 1, m * 3 + 2
 print "R", 1, m * 3 + 1
 print "H", 0, m * 3 + 3
elif l == 6:
 print "L", 1, m * 3 + 2
 print "R", 1, m * 3 + 1
else:
 for i in range(-~l / 2):
   if i * 2 < l - 1: print "S", 1, m * 3 + i + 1
   else: print "H", 1, m * 3 + i + 1
for i in range(m):
 print "R", 1, i * 3 + 2
 print "R", 0, i * 3 + 3
 print "R", 0, i * 3 + 3
if l == 7:
 print "R", 1, m * 3 + 2
 print "R", 0, m * 3 + 3
 print "H", 0, m * 3 + 3
elif l == 6:
 print "R", 1, m * 3 + 2
 print "H", 0, m * 3 + 3
else:
 for i in range(-~l / 2):
   if i * 2 < l - 2: print "S", 0, m * 3 + i + 2
   else: print "H", 0, m * 3 + i + 1

Try it online! Uses a six-step two-state busy beaver for n=6, then anonther state to clear enough tape in two steps to be able to run the busy beaver again. This handles all numbers whose remainder (modulo 8) is 0, 6 or 7; any remaining steps are handled by some probably suboptimal states.

C (gcc), Score 622410 442766 states
Now ported from bash to C so it's much faster! (The program constructs all 20,000 Turing machines on TIO in about 10 seconds total.)
Note that this version of the program always computes all 20,000 Turing machines (saving them in 20,000 separate files).  This is handy if you download the program and run it on your own computer.  (TIO appears to delete all files as soon as the program halts, so the 20,000 files aren't very useful in that environment.)
It also displays one of the Turing machines on stdout (as determined by an argument you pass to it).  This is practical for TIO.

Thanks to Surculose Sputum for pointing out that state t+3 in the original version was superfluous.  Taking it out reduced the total number of states considerably!
Other changes: Reduced the base cases from 6 to 4.  Fixed a few typos in the documentation, and improved the explanation a bit.

This program is based on a recursive construction: the idea is to construct an \$n\$-step Turing machine by taking a previously constructed \$\frac{n}{2}\$-step Turing machine and running it twice (except that this is adjusted a bit to take overhead into account).
I like this construction because it's easy to understand.
The program computes the Turing machines for 1 up to 20000, and it writes each Turing machine to a separate file.
It also accepts an argument \$n,\$ and displays the \$n\$-step Turing machine that was constructed on stdout (the default value for \$n\$ is 20000).
The score is correct for the challenge even if you request one of the smaller Turing machines, since, no matter what you pass as an argument, it always computes all 20,000 Turing machines and prints the correct codegolf challenge score for all 20,000 machines total.
If you run this on your own computer, run it in a directory by itself, because it will create files T1, T2, T3, ..., T20000 in the directory it's run in (one for each Turing machine).
/**********

INTRODUCTION

For each n from 1 to 20000, this program computes a Turing
machine Tn which takes exactly n steps when it runs.

The program writes all the computed Turing machines to
files T1, T2, T3, ..., T20000.

The total number of states for all 20000 machines is then
displayed.  (This is the score for the codegolf challenge.)

Also, one argument n is accepted on the command line; if provided,
it must be a number between 1 and 20000.  Turing machine Tn is
displayed on stdout.

If no argument is provided, the default is 20000.

Note that all 20000 machines are always computed and written
to the files on disk, but only the one you specify is written
to stdout.

Total time taken is about 10 seconds on TIO.

**********/

/**************

HOW TO COMPILE AND RUN

Save this file as tm.c, and compile it with the command

gcc -O3 -o tm tm.c

or, if you prefer,

gcc -O3 -Wall -Werror -W -o tm tm.c

Run it with a command like

./tm

or

./tm 50

This will display the Turing machine requested (T20000 or T50, in
the two examples above).

But you can look at all 20000 Turing machines in any case, since
they're all saved in files T1, T2, T3, ..., T20000.

(On TIO, the system will delete the saved files as soon as the
program finishes running, so they're not very useful in that
environment.)

**************/

/***************

FUNDAMENTAL IDEA

The idea is to compute a Turing machine which takes n steps to
run, by doing something as close as possible to the following:

Recursively take a machine that takes about n/2 steps to halt,
and run it twice.  (The base case for the recursion will be
n <= 4.)

This needs to be adjusted slightly because there are 3 steps
needed for overhead, so we need to use a machine that takes
(n-3)/2 steps to halt, instead of n/2 steps.

Also, if n is even, this leaves us one step short, so we
need to add an extra step in that case.

Since the challenge is to compute a machine for each n up to
20,000, there's no need to implement this using recursion in
the code.  Instead we just run through a loop, computing a
Turing machine for each n in turn.  But each computation
uses the previous results, just as the recursion suggests.

***************/

/***************

PROPERTIES OF THE CONSTRUCTED TURING MACHINES

These Turing machines never move to the left of position 0
  (the starting position of the tape head).

If the all the cells from the starting position to the right
  are initially 0, then Tn will take exactly n steps to run.

Each Turing machine leaves everything exactly as it found it
  (tape cell data and tape head position).

Output format:
  The program will write Turing machine Tn to a file called Tn
     (where n is replaced by the actual number).

During execution, the Turing machine Tn is divided into 3 separate pieces:
     The array element stateCountArray[n]  holds the number of states.
     The file An holds tuples in the form   movement newval newstate  for when
         the tape head is looking at a 0.
     The file Bn holds tuples in the form   movement newval newstate  for when
         the tape head is looking at a 1.

     An and Bn have one tuple for each state, in order from
         state 1 to the number of states.

The eventual machine Tn will consist of stateCountArray[n], An, and Bn, in that order.

***************/

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

#define MAXn (20000)

int stateCountArray[MAXn + 1];
char filenameTemplate[] = "X99999";
int score = 0;

void openTupleFiles(int n, FILE **file0, FILE **file, char *fileMode);
void createOnePrecomputedTuringMachine(int n, int numberOfStates, char *tuplesFor0, char *tuplesFor1);

void adjustStates(int firstUnusedState, FILE *oldFile, FILE *file);
/**********
The routine adjustStates takes a previously computed Turing
machine and makes the changes necessary to incorporate it into the
Turing machine currently being computed.
**********/

void basis(void);

void invalidArgument(void);

int getNumericalArgument(int argc, char **argv);

void openTupleFiles(int n, FILE **file0, FILE **file1, char *fileMode)
/**********
Given n, opens the two files An and Bn, and returns them in the file
descriptors file1 and file2.  The two files are opened in the indicated
mode: "r", "w", ....
**********/
   {
    sprintf(filenameTemplate, "A%d", n);
    *file0 = fopen(filenameTemplate, fileMode);
    *filenameTemplate = 'B';
    *file1 = fopen(filenameTemplate, fileMode);
   }

void createOnePrecomputedTuringMachine(int n, int numberOfStates, char *tuplesFor0, char *tuplesFor1)
/**********
Used by the function basis.

Sets up stateCountArray[n], An, and Bn as specified,
and updates score.
**********/
   {
    FILE *theFile;

    stateCountArray[n] = numberOfStates;

    sprintf(filenameTemplate, "A%d", n);
    theFile = fopen(filenameTemplate, "w");
    fputs(tuplesFor0, theFile);
    fclose(theFile);

    sprintf(filenameTemplate, "B%d", n);
    theFile = fopen(filenameTemplate, "w");
    fputs(tuplesFor1, theFile);
    fclose(theFile);

    score += numberOfStates;
   } // createOnePrecomputedTuringMachine

void adjustStates(int firstUnusedState, FILE *oldFile, FILE *file)
/**********
The routine adjustStates takes a previously computed Turing
machine and makes the changes necessary to incorporate it into the
Turing machine currently being computed.

oldFile should already be open for reading, and file should be open for writing.

Reads tuples from oldFile, writes tuples to file.

All states are shifted up by 1.

Each halting state is changed to a tuple which moves left and changes the state
to firstUnusedState.
**********/
   {
    char movement;
    int newValue;
    int newState;

    while (3 == fscanf(oldFile, "%c%d%d%*c", &movement, &newValue, &newState))
       {
        if ('H' == movement)
          {
           movement = 'L';
           newState = firstUnusedState;
          }
        else
          newState++;

        fprintf(file, "%c %d %d\n", movement, newValue, newState);
       } // while
   } // void adjustStates

void basis(void)
/**********
This handles values of n from 1 through 4, which form the basis of the recursion.

These Turing machines are precomputed.
**********/
   {
    createOnePrecomputedTuringMachine(1, 1, "H 0 1\n", "H 0 1\n");
    createOnePrecomputedTuringMachine(2, 1, "S 1 1\n", "H 0 1\n");
    createOnePrecomputedTuringMachine(3, 2, "S 1 1\nH 0 1\n", "S 1 2\nH 0 1\n");
    createOnePrecomputedTuringMachine(4, 2, "S 1 1\nS 1 2\n", "S 0 2\nH 0 1\n");
   } // basis

void invalidArgument(void)
   {
    printf("Usage: tm\n   or: tm n\nwhere n is a number between 1 and 20000\n(default is 20000).\n");
    exit(1);
   }

int getNumericalArgument(int argc, char **argv)
   {
    char * arg;
    char *p;
    int k = 0;

    if (argc < 2)
      return 20000;

    if (argc > 2)
      invalidArgument();

    arg = argv[1];

    if (0 == *arg)
      return 20000;

    for (p = arg; *p; p++)
      {
       if ((*p < '0') || ('9' < *p))
         invalidArgument();

       k = 10 * k + *p - '0';

       if (k > 20000)
         invalidArgument();
      }

     return k;
    }

#define BUFFERSIZE (4096)

int main(int argc, char **argv)
   {
    int n;
    int m;
    FILE *An;
    FILE *Bn;
    int t;
    FILE *Am;
    FILE *Bm;

    FILE *TuringMachineFile;
    char byteArray[BUFFERSIZE];
    int numberOfBytesRead;
    int argument;

    if (argc > 2)
      invalidArgument();

    argument = getNumericalArgument(argc, argv);

// For each values of n, we compute stateCountArray[n] and the two files An and Bn.

// First take care of the basis, n = 1 through 4.
    basis();

// Now start the main loop for n = 5 and up:
    for (n = 5; n <= MAXn; n++)
       {

// We'll go through 2 runs of the machine Tm that we
// computed earlier, where m = floor((n-3)/2).

// There are 3 steps of overhead, and we add in one
// extra step if n happens to be even, because in that
// case, 2 * floor((n-3)/2) + 3 is n-1, not n.
// This will get us to exactly n steps.

        m = (n - 3)/2;

// Open files An and Bn for writing.
        openTupleFiles(n, &An, &Bn, "w");

// Go through two runs of machine Tm.
// The cell at position 0 will keeep track of which run
// we're on (0 for the first run, 1 for the second).

// At the beginning, position 0 holds a 0, so we
// move right to position 1 and go to state 2.
        fputs("R 0 2\n", An);

// For even n, at the end of the entire run of Tn, we'll
// find ourselves back in state 1 at position 0, but the
// contents of that cell will be 0, and we'll halt.
// (For odd n, the machine will halt without going back
// to state 1.)
        fputs("H 0 1\n", Bn);

// Compute the number of states in the new machine Tn.
// It's two more than the number if states in Tm.
        t = stateCountArray[m] + 2;

// Open files Am and Bm for reading.
        openTupleFiles(m, &Am, &Bm, "r");

// The two calls below to the function adjustStates copy machine Tm
// into the Turing machine that we're building, with the following
// modifications:
//   - Use states 2 through t+1 instead of 1 through t.
//   - Halt tuples (H) get altered to tuples that don't halt
//       but instead move left (L) and change to state t+2.

        adjustStates(t, Am, An);
        fclose(Am);

        adjustStates(t, Bm, Bn);
        fclose(Bm);

// Since we're in state 2 at position 1, we're all set to run
// the altered copy of Tm, so that happens next.

// After running the altered copy of Tm, we're back at position 0,
// since the original Tm would have left us at position 1, but the
// altered version changed every H to an L, causing the tape head
// to move left one position, to position 0.

// If the tape head is looking at 0 in position 0,
// we just finished the first of the two runs of Tm.
// In that case, write a 1 to position 0 to indicate
// that we're on the second run now.
// Move right to position 1 and change to state 2.
// That will start the second run of Tm.

        fputs("R 1 2\n", An);
        fclose(An);

// If the tape head is looking at a 1 in position 0,
// we just finished our second run of Tm.  We're ready
// to halt, except that if n is even, we need to add
// one extra step.
        if (n % 2)
          {  // n is odd, so halt.
           fputs("H 0 1\n", Bn);
          }
        else
          { // n is even, so change to state 1 (which
            // will take the extra step we need).
            // State 1 will then halt because it's
            // looking at a 1.
           fputs("S 1 1\n", Bn);
          }

        fclose(Bn);

// Store the number of states for Tn in stateCountArray,
// and update the score..
        stateCountArray[n] = t;
        score += t;
       } // for n

// Print the codegolf challenge score (the total number of
// states in all 20000 Turing machines).

    printf("Score (up to 20000) = %d\n\n", score);

// Write each Turing machine Tn to the file called Tn (where
// n is the actual number).
// First write stateCountArray[n], then copy file An, and
// after that copy file Bn.

// Also delete the files An and Bn.

    for (n = 1; n <= MAXn; n++)
       {
        openTupleFiles(n, &An, &Bn, "r");

        sprintf(filenameTemplate, "T%d", n);
        TuringMachineFile = fopen(filenameTemplate, "w");

        fprintf(TuringMachineFile, "%d\n", stateCountArray[n]);

        numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, An);
        fwrite(byteArray, sizeof(char), numberOfBytesRead, TuringMachineFile);
        fclose(An);

        numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, Bn);
        fwrite(byteArray, sizeof(char), numberOfBytesRead, TuringMachineFile);
        fclose(Bn);

        fclose(TuringMachineFile);

        *filenameTemplate = 'A';
         unlink(filenameTemplate);

        *filenameTemplate = 'B';
        unlink(filenameTemplate);
       } // for n

// Finally print the requested Turing machine to stdout.

    (void) printf("Turing machine which halts after exactly %d steps:\n", argument);
    sprintf(filenameTemplate, "T%d", argument);
    TuringMachineFile = fopen(filenameTemplate, "r");
    numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, TuringMachineFile);
    fwrite(byteArray, sizeof(char), numberOfBytesRead, stdout);
    fclose(TuringMachineFile);

    exit(0);
   } // main

Try it online!

I think the ideas of the C++ answer can be used to compute more/better base cases (I'm not sure how much exactly that will help). Is the current first step necessary? (I think it can be avoided by relabeling states).

@mypronounismonicareinstate  Thanks, I'll take a look at the C++ answer (I haven't really looked at the other answers, except to see Surculose Sputum's impressive score).  More base cases would certainly help; the difficulty with that is that the method seems to require machines which leave everything the same at the end as at the beginning, so I couldn't simply use most machines I'd find elsewhere.  (I looked a bit at using known Busy Beaver champions as base cases, but they didn't seem to be directly applicable for that reason.)

@mypronounismonicareinstate As for relabeling states, it could be that there's some way to do it.  I tried a version where I used the cell in position -1 to keep track of which of the two runs it was on.  The idea was that I could then run the smaller Turing machine in its original place, getting the overhead down from 5 steps to 3 steps.  But this doesn't work because each recursive call needs to have its own copy of the run-counter (like a stack frame in traditional function calls). .... (continued)

...(continued)  The working version solves that by essentially shifting every recursive call one step to the right.  I didn't pursue the other approach because I thought that handling this issue would probably take more than the 2 steps I was saving.  (One could use a bunch of cells on the negative side to keep track of the various run counters, but I think that would add far too many steps to be useful.)

I think you can get rid of state $t+3$ with the following modification: (1) states 1 moves to position 1 to start $T_m$: R 0 2 (2) The halt state of $T_m$ moves back to position 0 and call state $t+2$: L 0 t+2 (3) State $t+2$ sees a zero, and thus calls $T_m$ again, and sets position 0 to one: R 1 2 (4) $T_m$ goes another round, then calls $t+2$ at position 0 (5) State $t+2$ sees a one, and thus halts. (5b) In the wrong parity case, state $t+2$ sees a one, and calls state 1: S 1 1 (6b) state 1 halts.

@SurculoseSputum Thanks -- I'll check it out.  I like the idea of altering H states to L instead of S, to save a state.

@SurculoseSputum It turned out that state t+3 was just an extra state.  All I had to do was alter H to L instead of S, and change the recursion to use $(n-3)/2$ instead of $(n-5)/2.$  (I was also able to reduce the number of base cases, but that's just for nicer code -- it doesn't affect the score at all.)  I'll upload the new version now.

Nice! I'm thinking about optimizing the unused half of state 1, when $n$ is odd. If $T_m$ is also odd, aka half of state 2 is unused, I wonder if we can combine the unused half-state to eliminate another state.

Yes, that's a possibility.  I just fixed the documentation in the program so that it correctly describes the halting half of state 1 as used for the case when n is even.  As you mentioned, it's not used when n is odd (but that wasn't clear from the original documentation).

Are you sure it is a good idea to use files for everything, now that you're using C? (the code seems extremely weird to me right now)

@mypronounismonicareinstate I was curious to see how much of a speed improvement I would get just by switching from bash to C, and I at least wanted to get it to run all the way to 20,000 without timing out on TIO.  Just switching languages got it down from 3 1/2 minutes to about 10 seconds.  If I have time today, I may re-do it using internal data structures instead of files.  But this direct port gave me the bulk of the possible improvement (something like a 95% reduction in running time).

Python 2, 100010000 states
n = input()
m = -~n / 2
print m
for i in range(m): print "S" if i * 2 < n - 1 else "H", 1, i + 1
for i in range(m): print "S" if i * 2 < n - 2 else "H", 0, -~i % m + 1

Try it online! Just to get the ball rolling.

Because of issues mentioned in the comments of the main post, I had to increase the upper bound on N. Could you update your score accordingly?

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Remove loops from a walk
I've been playing around with a robot on the coordinate plane. This robot is able to tell me if it goes left, right, up, or down by reporting back a string consisting of the letters L, R, U, and D, such as DLURRDLURDLLLRRLRLDURRU. Each character represents a movement of one unit. However, it seems that the robot is going in loops on the plane, returning to coordinates that it has already visited. I don't want the robot to do that. I'd like the robot to tell me about the path it takes without any loops included - these loops should be removed from left to right in the string. Every step in the string it reports should represent movement to a cell that it has not yet visited before. If the robot ends where it starts, then it should report back an empty string.
Test cases

ULRURU -> UURU
URDLDRU -> DRU
LLLLRRRL -> LL
LLLULRRRL -> LLLUR
UURDDRULDL -> {empty string}
DLURRDLURDLLLRRLRLDURRU -> R
URULLLDLUULDDLDRDDLLLLLDLLUUULLURU -> URULLLDLUULDDLDRDDLLLLLDLLUUULLURU

This is a standard code golf challenge, where the shortest answer wins. Standard rules apply.

What's the correct output for URDLDRU: URD, R, DRU, or something else?

How flexible are input and output? Can we take other characters? Or numbers?

@LuisMendo As the challenge states, the input is a string, and the output is also a string.

A string containing those characters necessarily? Or can we consistently use 4 other letters of our choice?

Whoops, I forgot to remove my vote to close after OP's (almost complete) clarification. I just voted to reopen

Regardless of what it reports, is your robot actually going in loops, or not?
Why might returning to coordinates already visited matter?
Why would you want the robot to tell you about the path it took, without loops?
How could a robot to tell you about paths without loops, unless you specifically programmed it to first identify and then eliminate loops?

Is there a maximum input-length, or should it (in theory) work for any input-length?

Would DRU be a valid output for the second test case (URDLDRU) as well, not just DRU? Because you remove the loop LDRU at the end.

What's the correct output for URDLDRUUU? Here, the robot makes a loop URDL which is removed, but then later returns to points within that loop. Do those points not count as visited?

Jelly, 20 bytes
O2ȷ:ı*S
ẆÇÐḟḢ⁸œṣFµÐL

Try it online! Or see the test-suite.
How?
O2ȷ:ı*S - Link 1, distance travelled: list of UDLR characters
O       - ordinals -> U:85 D:68 L:76 R:82
 2ȷ     - 2000
   :    - integer division -> U:23 D:29 L:26 R:24 (Note mod 4 these are 3 1 2 0)
    ı   - square root of -1  - i.e. (0+1j)
     *  - exponentiate -> U:(0-1j) D:(0+1j) L:(-1+0j) R:(1+0j)
      S - sum - 0 iff the path is a loop

ẆÇÐḟḢ⁸œṣFµÐL - Main Link: list of UDLR characters
         µÐL - loop until no change occurs:
Ẇ            -   all sublists
  Ðḟ         -   filter discard those which are truthy (non-zero) under:
 Ç           -     call last Link (1) as a monad
    Ḣ        -   head - X = first, shortest loop (if none this yields 0)
     ⁸       -   chain's left argument
      œṣ     -   split at sublists equal to X
        F    -   flatten

J, 51 39 bytes
([,~i.~{.])/@|.&.([:+/\0,0j1^'ULDR'&i.)

Try it online!
-12 bytes thanks to Bubbler! For the idea of combining "Under"s into a single train, and skipping an unnecessary increment of the indexes
The idea

Convert the letters to their indexes within the ULDR
Convert those indexes to complex vectors: Think U = i, L = -1, D = -i R = 1
In fact, because of rotational symmetry, we don't actually care which direction is "up" as long the relative order of the directions is preserved.
Scan sum those vectors to get the path positions (still as complex numbers)
Reduce the path into a loop free version: Any time we arrive at a point we've seen, remove all history up to and including that old point.
Invert steps 1 to 3, in reverse order.

The fun thing is that step 5 is accomplished with J's Under conjunction, which allows you to perform a transformation, do stuff, and then have the inverse transformation automatically applied.  Here, J is smart enough to know how to invert the entire train comprising steps 1 through 3 in reverse order:
                             Elementwise
reduce to       Scan sum     index within
remove loops    of...        'ULDR'
     |             |             |
vvvvvvvvvvvvv     vvvvv      vvvvvvvv
([,~i.~{.])/@|.&.([:+/\0,0j1^'ULDR'&i.)
               ^^      ^^^^^^
               |         |
             Under     0 prepended to
                       i raised to...

You can collect the &.-phrases into a single train phrase (it's actually interesting that J does accept certain trains for inverting). Also you don't need >: there since UD and LR have opposite directions anyway. TL;DR: 39 bytes.

Fantastic, didn't know that was possible, ty!

I didn't know it was possible either. I just guessed from your original code having &.(0,0j1^>:) that Agh-fork is invertible (which is reasonable since (A g h) is equivalent to A&g@:h; J can't invert fgh-forks in general).

JavaScript (Node.js),  101 ... 91  90 bytes
f=s=>s&&[s[Buffer(s).every(c=>p+=[w=s.length,~!++i,1,-w][c%5],i=p=0)-1]]+f(s.slice(p?1:i))

Try it online!
How?
Method
For each index \$n\$ in the input string, we initialize our position to \$(0,0)\$ and run a simulation of the walk starting from the \$n\$-th character. If there's some move at \$n+i-1,i>0\$ that brings us back to \$(0,0)\$, it means that we have identified a loop: we skip the entire segment and restart at \$n+i\$.
   n  n+i-1
   v    v
...LLURRD...
         ^
        n+i

Otherwise, we append the current move to the output (L in the above example) and advance to \$n+1\$.
Implementation

Instead of relying on an explicit counter \$n\$, we use recursive calls to our main function where the leading characters of the input string are gradually removed.

Instead of using a pair \$(x,y)\$ to keep track of our position, we actually use a scalar value \$p=x+y\cdot w\$, where \$w\$ is the remaining number of characters in the string. This is safe because we can't have more than \$w\$ moves in the same direction from this point.

To convert a character move into a direction, we take its ASCII code modulo \$5\$. The ASCII codes of \$(D,L,R,U)\$ are \$(68,76,82,85)\$, which are conveniently turned into \$(3,1,2,0)\$.

Commented
f = s =>                   // f is a recursive function taking a string s
  s &&                     // if s is empty, stop recursion
  [                        // wrapper to turn undefined into an empty string:
    s[                     //   get either s[0] (next char.) or s[-1] (undefined):
      Buffer(s).every(c => //     for each ASCII code c in s:
        p += [             //       add to p:
          w = s.length,    //         +s.length for up ('U' -> 85 -> 85 % 5 = 0)
          ~!++i,           //         -1 for left ('L' -> 76 -> 76 % 5 = 1)
                           //         (increment i)
          1,               //         +1 for right ('R' -> 82 -> 82 % 5 = 2)
          -w               //         -s.length for down ('D' -> 68 -> 68 % 5 = 3)
        ][c % 5],          //       using c modulo 5
                           //       stop if p = 0, meaning that we're back to our
                           //       starting point
        i = p = 0          //       start with i = p = 0
      ) - 1                //     end of every(), subtract 1
    ]                      //   end of s[] lookup
  ] +                      // end of wrapper
  f(                       // recursive call with either:
    s.slice(p ? 1 : i)     //   s.slice(1) (no loop)
  )                        //   or s.slice(i) (skipping the loop)

Just curious, what happens when c%5 === 4? How is the presumable undefined handled?

Oh, I guess it locks x into being NaN with !NaN === true?

@JonathanFrech c is one of 68, 76, 82 or 85 (the ASCII codes of DLRU) and none of them is congruent to 4 modulo 5.

MATL, 26 bytes
t"0J&y15\^hYs&=XR&fq&:[]w(

Try it online! Or verify all test cases.
Explanation
t        % Implicit input. Duplicate
"        % For each
  0      %   Push 0
  J      %   Push j (imaginary unit)
  &y     %   Duplicate third-topmost element from the stack: current string
  15\    %   ASCII code of each character, modulo 15. This gives 10, 7, 8, 1
         %   for 'U', 'R', 'L', 'D' respectively
  ^      %   Element-wise power. This gives j^10=-1, j^7=-j, j^8=1, j^1=j for
         %   'U', 'R', 'L', 'D'. These are the steps followed by the robot in
         %   the complex plane (rotated and reflected, but no matter)
  h      %   Concatenate. This prepends the 0, as starting point of the path
  Ys     %   Cumulative sum. This computes the path traced by the robot
  &=     %   Matrix of pair-wise equality comparisons for robot positions
  XR     %   Upper triangular part, without diagonal
  &f     %   Row and column indices of nonzeros. This will be non-empty if
         %   there is a loop in the path
  q      %   Subtract 1
  &:     %   Two-input range. This uses the first element from each input,
         %   that is, the first loop found
  []w(   %   Push [], swap, assignment index: this removes the characters that
         %   caused the loop
         %   string
         % End (implicit). The loop is run as many times as the input length,
         % which is an upper bound to the number of loops
         % Display (implicit)

T-SQL, 236 bytes
First time I ever use PI() in sql
I am using table as input
WHILE @@rowcount>0WITH C
as(SELECT*,sum(ascii(a)/12-6+3/(ascii(a)-79)*pi())over(order
by b)x FROM @)DELETE C
FROM C,(SELECT top 1max(b)i,min(b)j
FROM C GROUP BY x HAVING SUM(1)>1or x=0ORDER BY 2)z
WHERE(i=j or j<b)and i>=b
SELECT*FROM @

Try it online

C (gcc),  119 ... 111  110 bytes
Outputs by modifying the input string.
p;f(char*s){for(char*r,*q=s;*q;p?*s++=*q++:(q=r))for(r=q,p=0;*r?p+=(*r%17?strlen(q):1)*~-(*r++%5&2):0;);*s=0;}

Try it online!
How?
The algorithm is the same used in my JS answer with a few differences:

We use a for loop instead of a recursive approach.
We overwrite the input string with the output. This is safe because what is written is at most as long as what is read, and the meaningful information is always ahead of both the read and the write pointers (q and s respectively).
Given the ASCII code c of the move character, we use c % 17 to find out if it's a vertical or horizontal move, and c % 5 & 2 to distinguish between down and up or between left and right.
         | 'D' (68) | 'L' (76) | 'R' (82) | 'U' (85)
---------+----------+----------+----------+----------
 % 17    |     0    |     8    |    14    |     0
 % 5 & 2 |     2    |     0    |     2    |     0

Java (JDK), 229 bytes
s->{var l=new java.util.Stack();int x=0,y=0,i;for(var c:(s+"").getBytes()){l.add(x+","+y);i="DLUR".indexOf(c);x+=~i%2*~-i;y+=i%2*(i-2);i=l.indexOf(x+","+y);if(i>=0){var z=l.subList(i,l.size());s.delete(i,i+z.size());z.clear();}}}

Try it online!
Credits

5 bytes saved thanks to ceilingcat
22 bytes saved thanks to Kevin Cruijssen

229 bytes

perl -nF/(?{s-.*(??{!($&=~y&R&&c==$&=~y&L&&c&&$&=~y&U&&c==$&=~y&D&&c)})--g;print})(*COMMIT)/, 62 12 5 0 bytes

Try it online!
Finds substrings with the same amount of Ls and Rs, and the same amount of Us and Ds, and removes them. Prints the result.

Fun fact, you can use that regex in -F for a 12 byte solution!

Or just 5 bytes

The size of your command line switches get measured when you do that, no?

@Riking We don't count the size of command line switches, but there's a good case to be made it should, as I brought the program size down to 0 bytes, by effectively lifting the entire program to a command line switch.

@Abigail congrats, you found the exact reason why we used to count them. Please don't do this.

Sorry you got downvoted for my contribution, I actually found this really interesting - I don't think I've ever seen (*COMMIT) before this (or if I had, I'd forgotten about it)!

Java (OpenJDK 8), 253 252 243 bytes
static String r(String s){String e=s;int l=s.length();for(int i=0;i<l;i++)for(int j=i+1;j<l;j++){int u=0;for(int k=i;k<=j;k++)u+=(9*(e.charAt(k)%6/3)+1)*2*(5.5-(e.charAt(k)-12)/11);if(u==0)return r(e.replace(e.substring(i,j+1),""));}return e;}

Try it online!
This uses a recursion method, so I'm not entirely sure if it's being scored correctly.
It has a limit of going off 9 tiles in a given loop, but that can be increased to any amount as needed.
Ungolfed:

public static String remove(String str) {
    String removed = str;
    int l = str.length();
    for (int i = 0; i < l - 1; i++) //-1 optional
        for (int j = i + 1; j < l; j++) {
            int upDownLeftRight = 0;
            for (int k = i; k <= j; k++)
                upDownLeftRight +=(9*(e.charAt(k)%6/3)+1)*2*(5.5-(e.charAt(k)-12)/11);
            if (upDownLeftRight == 0)
                return remove(removed.replace(removed.substring(i, j + 1), ""));
        }
    return removed;
}

A few seconds before I was going to submit this the post closed, a few days ago. Just realized it was opened back up.

Ah, those are some really good optimizations @ceilingcat, I learned something

221 bytes

You don't have to count the static, so it can be moved to the header (or you can remove it and change your r("...") calls to new Main().r("...")). Also, by switching to JDK 10+ you can change the String e=s; to var e=s;.

Python 2, 94 93 bytes
-1 byte thanks to @dingledooper!

r=""
x,=l=[0]
for c in input():x+=1j**(ord(c)%15);r+=c;l[len(r):]=x,;r=r[:l.index(x)]
print r

Try it online!
A minor improvement over @xnor's solution using slice assignment. Be sure to check out and upvote his answer!
The current position x is stored as a complex number. For each movement, the program checks the list of visited positions l, and truncates the redundant moves appropriately.

93 bytes

@dingledooper Thanks! I forgot why I expanded that part out...

Ohh, because originally it was a tuple, which throws error during the slice assignment.

Your improvement is not at all minor! The new strategy for updating the list l of visited positions is very nice and well worthy of the bounty.

Charcoal, 40 bytes
⊞υ⟦ⅈⅉ⟧ＦＳ«Ｍ✳ι⊞υι⊞υ⟦ⅈⅉ⟧≔…υ⊕⌕υ§υ±¹υ»⎚↑Φυ﹪κ²

Try it online! Link is to verbose version of code. Explanation:
⊞υ⟦ⅈⅉ⟧

Save the current coordinates to the predefined empty list.
ＦＳ«

Loop through each character of the input string.
Ｍ✳ι

Move the cursor in that direction.
⊞υι⊞υ⟦ⅈⅉ⟧

Save the direction and the new position.
≔…υ⊕⌕υ§υ±¹υ

Truncate the list to the original appearance of the position.
»⎚

Reset the cursor (possibly due to a bug in Charcoal).
↑Φυ﹪κ²

Output the directions which didn't get truncated.

Python 3.8 (pre-release), 168 164 163 126 125  bytes
l=[p:=0]
n=""
for s in input():
 if(p:=p+1j**(ord(s)%15))in l:x=l.index(p);l=l[:x+1];n=n[:x];p=l[x]
 else:l+=[p];n+=s
exit(n)

Try it online!
Assigns a complex number to go up, down, left right on the complex plane. Then iterates over the given path S and either adds the new point to the path in the list of points l and the result string n or if it detected a loop from a previous index up until the current character, it slices the characters and points that created the loops out of the lists.
-35 thanks to @JonathanAllan!

You could get rid of u and use p:=p+1j**(ord(s)%15)).

Also some spaces can be removed and we can print to STDERR with exit TIO - there's probably a slightly terser way of doing this program (possibly as a recursive function) too...

Thanks! Yeah it's been a while I've been playing. I counted tab as 1 character forgetting that I auto insert 4 spaces instead... Also nice catch using powers of i of unicode%15. How'd you come up with that one?

I came up with it when building my Jelly answer by just trying a few (although I then realised 2000 integer divided by ord(s) was a byte shorter in Jelly due to the problem that O%15ı is parsed as ord(s)%(15+j)).

You still have four redundant spaces in there. if(p:=p+1j**(ord(s)%15)) in l: l= -> if(p:=p+1j**(ord(s)%15))in l: l= and else: l+= -> else:l+=

Also the walrus for x costs a byte over if(p:=p+1j**(ord(s)%15))in l:x=l.index(p);l=l[:x+1];n=n[:x];p=l[-1]. Another save is p=l[-1] -> p=l[x]

One more - first two lines can become l=[p:=0].

oof, it really has been a while since I last golfed. lost the eye for those details it seems.

heres 153 bytes with useless spaces removed Try it online!

yeah, I got a bit rusty, thanks to nasty stuff like PEP8 etc xD we are down to 119 by now though :)

You need to take in S via input() or a function argument rather than hardcoding it in.

@xnor fixed it!

Python 3, 178 bytes
x=y=0;c=[[0,0]];a='';t='UDLR';u=['y-=1','y+=1','x-=1','x+=1']
for i in input():
 exec(u[t.index(i)])
 if[x,y]in c:f=c.index([x,y]);a=a[:f];c=c[:f]
 else:a+=i
 c+=[[x,y]]
print(a)

Try it online!
Keeps track of visited coordinates and removes letters between duplicate coords.

Replace t='UDLR';u=['y-=1','y+=1','x-=1','x+=1'] and exec(u[t.index(i)]) with j=ord(i);exec('y x'[j%17%6]+'-+'[j//6%2]+'=1') to save 14 bytes.

R, 208 205 bytes
u=function(a){s=function(x)unlist(strsplit(x,''))
m=match
d=s(a)
l=length(d)
for(i in 1:l)for(j in i:l)if(l&!sum(m(d[k<-i:j],s("L R"),2)-2)&!sum(m(d[k],s("D U"),2)-2))return(u(d[-k]))
paste(d,collapse='')}

Try it online!
Recursive function: starting at each position in the string, check whether there are equal numbers of L+R and of U+D in the range up to each subsequent position.  If so, then this is the first left-to-right loop, so delete this and call the function using the result.  Otherwise, there are no loops, so output whatever is left.
Frustratingly, R is not particularly golfy at string-handling (at least with my ability), and one-third of the code is wasted used splitting strings into characters... so:
R+stringr, 155 bytes (or R 172 bytes)
u=function(d,l=nchar(d),s=substring){
for(i in 1:l)for(j in i:l)if(l&all(!diff(str_count(e<-s(d,i,j),s("UDLR",1:4,1:4)))[-2]))return(u(str_remove(d,e)))
d}

Try it online!
Exactly the same approach, but using stringr library to work directly on the string instead of splitting into characters.

Python 2, 98 bytes
r=""
x,=l=0,
for c in input():x+=1j**(ord(c)%15);l+=x,;r+=c;n=l.index(x);l=l[:n+1];r=r[:n]
print r

Try it online!
Instead of branching on whether the current position x has appeared before, we just look for where it first appeared and truncate to right after that. If it never appeared before, we find the current appearance, so nothing gets cut off. The ord(c)%15 is from a suggestion by Jonathan Allan.

I got 95 bytes by never truncating l, but replacing append with insert at the appropriate index.

94 bytes

@SurculoseSputum Nice solution! I think you should post it yourself. It's definitely worthy of an outgolfing bounty

Thanks! I didn't want to make a new solution because it was too similar to yours, but if you insist. :)

If you use input on Py2 don't that mean your input need pair of "" besides?

@l4m2 Yes, that's right

Wolfram Language, 101 100 bytes
StringJoin[Characters@#/.(r={"L"->-"R","U"->-"D"})//.{a___,x__,b___}/;Tr@{x}==0->{a,b}/.Reverse/@r]&

Try it online!
With some fancier formatting and comments:
StringJoin[                                       (*reconvert to input format*)
  Characters@#                                    (*split into characters*)
  /. (r = {"L" -> -"R", "U" -> -"D"})             (*map L to -R and U to -D*)
  //. {a___, x__, b___} /; Tr@{x} == 0 -> {a, b}  (*delete runs that sum to 0*)
  /. Reverse /@ r                                 (*convert -R and -D back to L and U*)
]&

This takes a similar method to some of the others, deleting runs that sum to zero, but this one does it by replacing L and U with negative R and negative D respectively.
Another 100 byte solution that uses a similar but distinct technique, using SequenceReplace:
StringJoin@SequenceReplace[Characters@#/.(r={"L"->-"R","U"->-"D"}),{__}?(Tr@#==0&)->{}]/.Reverse/@r&

Try it online!

05AB1E, 44 bytes
gU0ˆÇ5%v1X‚Â(ìyè¯θ+ˆ¯¤kÐV¯gα<‚Xª£ιнJ¯Y>£´vyˆ

Ugh.. This can definitely be golfed substantially, but it works..
Inspired by both @Arnauld's JavaScript answer and @OlivierGrégoire's Java answer, so make sure to upvote them!
Try it online or verify all test cases.
Explanation:
g                # Get the length of the (implicit) input-string
 U               # Pop and store it in variable `X`
0ˆ               # Add 0 to the global array
Ç                # Convert the (implicit) input-string to an integer-list of codepoints
 5%              # Take modulo-5 on each
   v             # Loop over each integer `y`:
    1X‚          #  Pair 1 with the length `X`: [1,length]
       Â         #  Bifurcate it (short for Duplicate & Reverse copy)
        (        #  Negate the values: [-length,-1]
         ì       #  Prepend the lists together: [-length,-1,1,length]
          yè     #  Index `y` into this quadruplet
            ¯θ+  #  Add the last item of the global array to it
               ˆ #  And pop and add it to the global array
    ¯            #  Push the global array
     ¤           #  Push its last item (without popping)
      k          #  Get the first index of this last item in the global array
       Ð         #  Triplicate this index
        V        #  Pop and store one copy in variable `Y`
         ¯g      #  Push the length of the global array
           α     #  Take the absolute difference with the index
            <    #  Decrease it by 1
             ‚   #  Pair it with the index
              Xª #  And append length `X`
    £            #  Split the string into parts of that size
                 #  (which uses the implicit input-string in the very first iteration)
     ι           #  Uninterleave it
      н          #  Only leave the first part of two strings, removing the middle part
       J         #  Join this pair together
    ¯            #  Push the global array again
     Y>          #  Push `Y` + 1
       £         #  Only leave the first `Y`+1 values of the global array
        ´        #  Empty the global array
         v       #  Loop over the `Y`+1 values of the global array:
          yˆ     #   And add each of them back the global array

PowerShell, 126 120 bytes
$x=$y=0
switch -r(,'-'+$args){U{$y++}D{$y--}R{$x++}L{$x--}.{$g="$g$_$x-$y"-replace"(?<=($x-$y)).*\1$"}}
$g-replace'\d|-'

Try it online!
The script:

injects $x-$y to input string like -0-0U0-1U0-2R1-2U1-3
removes substrings between same coordinates
removes digits and minus chars

Less golfed:
$x=$y=0
switch -regex (,'-'+$args){
    U {$y++}
    D {$y--}
    R {$x++}
    L {$x--}
    . {$g="$g$_$x-$y"-replace"(?<=($x-$y)).*\1$"}
}
$g-replace'\d|-'

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/