Skip to main content
Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Authoritative reference needed by TROLLHUNTER
Bounty Started worth 50 reputation by TROLLHUNTER
added 74 characters in body
Source Link

I am looking to get a definite answer to title question.

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (ie the simplest game) that is needed for a chess-like game to be turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations).

Is there any piece we can add to the game to prove it turing complete?

I am looking to get a definite answer to title question.

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (ie the simplest game) that is needed for a chess-like game to be turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations)

I am looking to get a definite answer to title question.

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (ie the simplest game) that is needed for a chess-like game to be turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations).

Is there any piece we can add to the game to prove it turing complete?

Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
edited tags
Link
Tweeted twitter.com/#!/StackCSTheory/status/124652747223080961
Notice added Authoritative reference needed by TROLLHUNTER
Bounty Started worth 100 reputation by TROLLHUNTER
edited tags
Source Link

I am looking to get a definite answer to title question.

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (ie the simplest game) that is needed for a chess-like game to be turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations)

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (ie the simplest game) that is needed for a chess-like game to be turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations)

I am looking to get a definite answer to title question.

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (ie the simplest game) that is needed for a chess-like game to be turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations)

Post Reopened by Suresh Venkat
added 47 characters in body
Source Link
Loading
edited tags
Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185
Loading
Post Closed as "off topic" by Suresh Venkat
Source Link
Loading