[Math] Constructing a non-halting turing machine

logicturing-machines

I'm wondering if constructing a non-halting turing machine is as simple as I think it is. It seems like all that's required is one loop.

Is the flow-chart machine attached accurately non-halting? Basically, you pass over all marks in the alphabet (moving in some arbitrary direction) and then switch states whenever you get to a blank, so that you just keep switching back and forth in a blank stretch of tape. This seems like it wouldn't halt but I fear I'm critically misunderstanding something. enter image description here

Best Answer

As mentioned in the comments, this seems to be a perfectly reasonable description of a non-halting Turing Machine. Do you have a particular reason to think that the description of a non-halting Turing Machine would be complicated?

One reason people tend to think that non-halting Turing Machines would be complicated is due to the halting problem, but that's a fundamental misunderstanding. Figuring out if a particular TM halts is often quite easy: any TM that computes addition, or multiplication, or any other total function clearly halts on every input. The difficulty arises when you try to determine the set of all halting TMs.

Related Question