Skip to main content
5 of 5
added explanation
Jo King
  • 48.1k
  • 6
  • 131
  • 187

Perl 6, 46 43 36 bytes

{$_.=rotate(.[0]*=-1)xx 2**$_;!.[0]} 

Try it online!

Represents halt by 0 and returns true if the machine halts. This repeats the logic 2**(length n) times, where if the pointer ends up on the halt cell, it stays there, otherwise it will be on a non-halt cell. This works because there are only 2**n possible states (ignoring halt cells) for the Foo machine to be in, since each non-halt cell has only two states. Okay yes, there are states than that, but due to the limited possible transitions between pointers (and therefore states) there will be less than 2**$_ states... I think

Explanation

{ } # Anonymous codeblock xx 2**$_ # Repeat 2**len(n) times .[0]*=-1 # Negate the first element $_.=rotate( ) # Rotate the list by that value ;!.[0] # Return if the first element is 0 
Jo King
  • 48.1k
  • 6
  • 131
  • 187